Задача 29. Вычисление значения полинома

Условие задачи. Для заданного x вычислить значение полинома  по схеме Горнера.

В общем случае полином степени n представляет собой многочлен P (x) = a ₀ xⁿ + a ₁ x^{n -1} + a ₂ x^{n -2} + … + a_kx^{n - k} + … + a_{n -2} x ² + a_{n -1} x ¹ + a_{n .} Для вычисления его значения при заданном х по схеме Горнера предварительно выполняется деление исходного полинома с остатком на x, в результате чего он приводится к виду:

P(x) = ((…(…(((a₀ ) x + a₁) x+ a₂ ) x + … +a_k )x + …+ a_n-3 )x + a_n-2) x + a_n-1) x + a_n

При такой форме представления полинома для вычисления его значения при конкретном значении x можно, начав с самой внутренней пары скобок, задать

p ₀ = a ₀,

а далее в результате повторения однотипных действий последовательно вычислять

p ₁ = p ₀ x  + a ₁

p ₂ = p ₁ x  + a ₂

…

p_k = p_k-1x  + a_k

…

p_n = p_{n -1} x  + a_n

Значение p_n будет значением полинома при конкретном значении x. Такой прием позволяет избежать трудоемких операций по возведению х в разные степени.В общем виде такой вычислительный процесс можно записать как рекуррентную зависимость:

p ₀ = a ₀ 

p_k = p_k-1x  + a_k,  k = 1,2, …, n

Тогда для задания и хранения коэффициентов полинома удобно использовать массив (указывая 0 для коэффициентов при отсутствующих степенях, например, при степени 1 в условии данной задачи), причем удобнее, если его элементы будут иметь индексы от 0 до n, если это позволяет язык программирования, на котором реализуется алгоритм. Для полинома, заданного в условии данной задачи, , степеньполинома n=4, а коэффициенты имеют значения 2, 3, -1, 0 и 5, следовательно, элементы массива а от a[0] до a [4] должны иметь перечисленные значения. Для вычисления собственно значения полинома можно использовать единственную переменную p, так как вычисляемое на каждом шаге значение p_k зависит только от предыдущего значения p_{k -1}, очередного коэффициента полинома a_k и заданного значения x.

Структурированная запись алгоритма 29

1. n = 4

2. Создать массив коэффициентов полинома a из n + 1 элементов, проиндексированный от 0 до n, и инициализировать его значениями согласно заданию.

3. Ввести значение x

4. p = a[0]

5. Повторить для k от 1 до n:

5.1.  p = p * x + a[k]

6. Вывести сообщение «Значение полинома при заданном x равно:» и значение p

Схема алгоритма

Текст программы на языке Си

#include <stdio.h>

#include <stdlib.h>

#define n 4

double a[n+1]={2.0, 3, -1.0, 0, 5.0};

int main(int argc, char *argv[])

{

int k;

double p, x;

printf("Введите значение параметра x: ");

scanf("%lf",&x);

p=a[0];

for(k=1;k<=n;k++)

p = p*x + a[k]);

printf("Значение полинома P(%lg) = %lg ",x,p);

system("pause");  

return 0;

}

Текст программы на языке Паскаль

Program Pr_29;

Const

n = 4;

a: array [0..n] of real = (2, 3, -1, 0, 5);

Var

x, p: real;

k: integer;

begin

writeln(ʹВведите х’);

readln(x);

p:=a[0];

for k:=1 to n do

p:=p*x+a[k];

writeln(ʹЗначение полинома = ’, p:5:2)

end.