Schemat Hornera

Schemat Hornera jest algorytmem obliczania wartości wielomianu w punkcie.

Każdy wielomian stopnia n jest funkcją postaci:
W(x)=a(n)x^n+a(n-1)x^+a(n-2)x^n+...+a(1)x+a(0), gdzie a(n)<>0

Funkcję tą można również zapisać nieco inaczej, np

dla wielomianu stopnia 2:

zamiast: W(x) = a(2)x^2+a(1)x+a(0) tak:  W(x) = x[a(2)x+a(1)]+a(0)

Ta druga postać o minimalnej ilości obliczeń (dwa mnożenia dwa dodawania zamiast 3 mnożeń 2 dodawań) nosi nazwę postaci Hornera i znakomicie nadaje się do implementacji w programach komputerowych. Stosowanie schematu Hornera umożliwia zmniejszenie liczby działań oraz również zwiększenie dokładności otrzymywanego wyniku.

Przykład realizacji:

program Schemat_Hornera;

uses crt;
const
    stopien=3;
type
    tab_wsp=array [0..stopien] of integer;
var
    wpr_wps:tab_wsp;
    x:real;

procedure wspolczynniki(var wsp:tab_wsp);
var
    i:integer;
begin
    for i:=stopien downto 0 do
    begin
        write('Podaj wspolczynnikiynnik nr ',i,': ');
        readln(wsp[i]);
    end;
end;

procedure pokazwielomian(var wsp:tab_wsp);
var
    i:integer;
begin
    for i:=stopien downto 1 do
        if wsp[i]<>0 then
            write(wsp[i],'*x^',i,' + ');
    writeln(wsp[0]);
end;

function schemat_hornera(var wsp:tab_wsp; n:integer; x:real):real;
var
    wynik:real;
begin
    if n=stopien then
        schemat_hornera:=wsp[stopien]
    else
        schemat_hornera:=wsp[n]+x*schemat_hornera(wsp,n+1,x);
end;

function wartosc(var wsp:tab_wsp; x:real):real;
begin
    wartosc:=schemat_hornera(wsp,0,x);
end;

begin
    clrscr;
    wspolczynniki(wpr_wps);
    pokazwielomian(wpr_wps);
    writeln('Podaj wartosc x: ');
    readln(x);
    writeln('Wartosc wielomianu=',wartosc(wpr_wps,x));
    repeat until keypressed;
end.
Ocena: 5.0

Komentarze