Форум программистов, компьютерный форум CyberForum.ru

Найти коэффициенты k-ого многочлена Чебышева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.67
SecretSilent
 Аватар для SecretSilent
76 / 77 / 2
Регистрация: 16.02.2010
Сообщений: 578
09.03.2010, 11:23     Найти коэффициенты k-ого многочлена Чебышева #1
Посмотрела по форуму - не нашла такой темы.
Помогите, пожалуйста, с программой на С. Что-то никак не пойму, как делать...
Заранее благодарю!

Дано целое k от 2 до 20. Найти коэффициенты k-ого многочлена Чебышева (Замечание: многочлены Чебышева опpеделяются фоpмулами T0(x)=1; T1(x)=x; Tn(x)=2x*Tn-1(x)-Tn-2(x), n=2,3,4,5,....).

Добавлено через 1 час 2 минуты
как вообще коэффициенты выделить, подскажите, пожалуйста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.03.2010, 11:23     Найти коэффициенты k-ого многочлена Чебышева
Посмотрите здесь:

Ввести n и числа a1, a2,...,an Вычислить и вывести коэффициенты многочлена p(x) = (x+a1)*(x+a1*a2)*...*(x+a1*a2*...*an) C++
как создать многочлен н-ой степени где коэффициенты многочлена выводятся через массив C++
C++ Найти сумму и произведение элементов k-ого столбца матрицы
Найти коэффициенты произведения многочленов C++
C++ Многочлен степени n задан массивом своих коэффициентов. Подсчитать коэффициенты производной многочлена.
Найти степень многочлена C++
Найти значение многочлена при заданном аргументе, производной от многочлена C++
C++ Найти значение многочлена

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vorona
Peace 2 all shining faces
 Аватар для Vorona
660 / 522 / 44
Регистрация: 05.03.2010
Сообщений: 1,256
09.03.2010, 12:42     Найти коэффициенты k-ого многочлена Чебышева #2
Не разбираюсь в Паскале, но думаю, что этот код может помочь, осталось на Си перевести нужную его часть
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
uses crt;
 
const
  maxOrder = 20;
type
  coeffType = array[0 .. maxOrder] of integer;
 
{ Это только для контроля результатов }
procedure print_coeffs(var coeffs: coeffType);
const
  sign: array[boolean] of string[3] =
    (' - ', ' + ');
var
  before: boolean;
  i: integer;
begin
  before := false;
  for i := maxOrder downto 0 do begin
    if coeffs[i] <> 0 then begin
      if before then write(sign[coeffs[i] > 0])
      else before := true;
      write('x^', i, '*', abs(coeffs[i]));
    end;
  end;
end;
 
{ Дополнительные процедуры }
procedure mult_2x(var res: coeffType;
          const cf: coeffType);
var i: integer;
begin
  move(cf[0], res[1], pred(maxOrder)*sizeof(integer));
  res[0] := 0;
  for i := 0 to maxOrder do res[i] := res[i]*2;
end;
procedure minus(var From: coeffType;
          const What: coeffType);
var i: integer;
begin
  for i := 0 to maxOrder do
    from[i] := from[i] - what[i];
end;
 
{ Процедура, находящая коэффициенты полинома Чебышева степени N }
procedure get_poly(var coeffs: coeffType; n: integer);
var
  i: integer;
  cf_zero, cf_one, cf_curr: coeffType;
begin
  fillchar(cf_curr, sizeof(coeffType), 0);
  fillchar(cf_zero, sizeof(coeffType), 0);
  fillchar(cf_one, sizeof(coeffType), 0);
 
  cf_zero[0] := 1; cf_one[1] := 1;
 
  for i := 2 to n do begin
    mult_2x(cf_curr, cf_one);
    minus(cf_curr, cf_zero);
 
    cf_zero := cf_one;
    cf_one := cf_curr;
  end;
  coeffs := cf_curr;
end;
 
var
  coeffs: coeffType;
 
begin
  clrscr;
  get_poly(coeffs, 2);
 
  { это - только для проверки }
  print_coeffs(coeffs);
 
  { Здесь - решай уравнение, заданное коэффициентами }
end.
Sanych.by
 Аватар для Sanych.by
3 / 3 / 1
Регистрация: 01.03.2010
Сообщений: 3
11.03.2010, 15:47     Найти коэффициенты k-ого многочлена Чебышева #3
Идея решения:
Для нахождения многочлена следующего порядка необходимо иметь текущий и предыдущий.
Они будут хранится в массиве. Многочлен хранится в массиве в следующем виде:
коэффициенты хранятся в порядке возрастания степени (индекс элемента соответствует степени переменной). Например, массив [1, -2, 1, 0, ..., 0] является представлением многочлена x^2-2x+1.

Для вычисления многочлена следующей степени сохраняется массив текущего многочлена (для последующей записи его в массив предыдущего многочлена). После этого текущий массив умножаем на 2х. Умножение на х является повышением степени многочлена на 1, так как в массиве, которым представлен многочлен, коэффициенты хранятся в порядке возрастания степени, то для повышения степени необхожимо все элементы сдвинуть "вправо" на 1 (T[j] = T[j-1]). После этого массив поэлементно умножается на 2. Следующий шаг - вычитание предыдущего многочлена. Выполняется поэлементным вычитанием из уже умноженного массива, массива, представляющего предыдущий многочлен. После этого предыдущим многочленом становится текущий на момент начала цикла, значение которого было предварительно сохранено в начале цикла.

Повторяется k раз, где k - степень многочлена.

Реализация:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <stdlib.h>
#define MaxLength   20
int main()
{
    int k, i, j, NotBegin = 0;
    int Tcurr[MaxLength+1], Tprev[MaxLength+1];
    printf("Enter number k: ");
    scanf("%d", &k);
    /*
    Начальная инициализация массивов коэфф. многочлена.
    Коэфф. в массиве хранятся по возрастанию степени:
    элемент с нулевым индексом - свободный член,
    элемент с первым индексом - первая степень X и так далее
    То есть, индекс массива = степень X.
    */
    for(i = 0; i <= MaxLength; i++)
    {
        Tprev[i] = Tcurr[i] = 0;
    }
    Tprev[0] = 1; // T[0] = 1.
    Tcurr[1] = 1; // Т[1] = X.
    for(i = 2; i <= k; i++)
    {
        int buffer[MaxLength+1]; //Буфферный массив для сохранения предыдущего элемента.
    //Сохранение текущего многочлена, так как он станет T[n-1]
        for(j = 0; j <= MaxLength; j++)
        {
            buffer[j] = Tcurr[j];
        }
    //Умножение на 2*X.
        /*
        Умножением на Х - повышение степени многочлена на 1.
        Так как в массиве коэфф. хранятся по возврастанию,
        достаточно сдвинуть элементы "вправо", а нулевому элементу
        который является свободным членом присвоить нулевое значение.
        Старший элемент теряется.
        */
        for(j = MaxLength; j > 0; j--)
        {
            Tcurr[j] = Tcurr[j-1]*2;
            /*Более наглядно было бы написать так:
            Tcurr[j-1] *= 2;        //Умножение на 2.
            Tcurr[j] = Tcurr[j-1];  //Умножение на Х.
            */
        }
    //Вычитание
        Tcurr[0] = 0;
        /*
        Следующий шаг - вычитание T[n-2] многочлена,
        который представлен массивом Tprev.
        Это производится поэлементным вычитанием массивов.
        */
        for(j = 0; j <= MaxLength; j++)
        {
            Tcurr[j] -= Tprev[j];
        }
    /*
    Теперь Tcurr вычислен, а Tprev необходимо присвоить значение
    Tcurr на начало цикла, которое было сохранено в buffer.
    */
        for(j = 0; j <= MaxLength; j++)
        {
            Tprev[j] = buffer[j];
        }
    }
    //Вывод результата в виде строки.
    for(i = MaxLength; i >= 0; i--)
    {
        if(Tcurr[i])
        {
            if(Tcurr[i] > 0 && NotBegin)
                printf("+");
            printf("%d", Tcurr[i]);
            if(i)
                printf("x^%d", i);
            NotBegin = 1;
        }
    }
    return 0;
}
Yandex
Объявления
11.03.2010, 15:47     Найти коэффициенты k-ого многочлена Чебышева
Ответ Создать тему
Опции темы

Текущее время: 18:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru