Решение полиномов схемой Горнера

        На главную

 

       Общий вид многочлена:

 

f (x) = xn + a1xn–1 + a2xn–2 + ... + an–1x + an

(1)

 

Общепринятый сейчас способ вычисления многочленов восходит к Ньютону и называется схемой Горнера. Эта универсальная (то есть применимая к любому многочлену) схема предельно проста и изящна. Она получается из формулы (1) вынесением за скобки x всюду, где это возможно:

f (x) = (...(((x + a1)·x + a2)·x + a3)...)·x + an.

(2)

 

Порядок действии при вычислении  f (x) определяется скобками в (2): сначала сложение внутри самой внутренней пары скобок (его результат обозначим через p₁), затем умножение и сложение внутри следующей пары скобок (результат p₂) и т.д.:

ì  p1 = x + a1; ï  p2 = p1x + a2; í  p3 = p2x + a3; ï  · · · · · · · · · · · · · · · · · · î  pn = pn–1x + an,     f (x) = pn;

(3)

Привожу образец программы на паскале:

 

program polynom;

type poli = array[0..100]of real;

var a,p:poli;

    i,n:integer;

    x:real;

 begin

    Writeln ('Введите степень');

    readln(n);

 

    Writeln ('Введите X');                         {Ввод данных}

    readln(x);

 

    writeln ('Введите коэффиценты');

    for i:=1 to n do

    readln(a[i]);

 

    p[0]:=1;

    for i:=1 to n do

    p[i]:=p[i-1]*x + a[i];                    {Реализация схемы}

 

    writeln(p[n]:3:3);             {Вывод значения}

  readln;

end.

На главную