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.

Komentarze


link Silnią liczby naturalnej n nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie symboliczne n! (czytaj: n silnia) wprowadził w 1808 roku francuski matematyk Christian Kramp. Zgo


link Ciąg Fibonacciego to ciąg liczb naturalnych zwanych liczbami Fibonacciego określony rekurencyjnie w sposób następujący:F0 = 0F1 = 1Fn = Fn-1 + Fn-2, dla n ≥ 2Początkowe wartości tego ciągu to:


link Sito Eratostenesa jest sposobem wyznaczania liczb pierwszych zaproponowanym przez greckiego matematyka Eratostenesa. Metoda sita (w założeniu eliminacja) polega na odrzucaniu liczb naturalnych będących wielokrotnościami liczb pie


link program kwadratowe;uses crt;var x1,x2,x,r1,r2,delta,pierwiastek:real;    a,b,c,yw,x0:real;    kla:char;beginrepeat  clrscr;  writeln('Ten program rozwiazuje rownania kwadratowe axx+by+c');  w