W charakterze przykładu rozważymy schemat blokowy programu sortowania bąbelkowego ciągu n liczb: Porządkowanie liczb za pomocą tej metody wykonywane jest w krokach o takiej samej organizacji logicznej. W kroku pierwszym przeglądane są kolejne pary: i w przypadku odwrotnego ustawienia liczb w parze są zamieniane miejscami - w ten sposób liczba najwyższa znajduje się na ostatniej pozycji ciągu. W kolejnych krokach j = 2, ..., największe liczby z coraz to krótszych ciągów: są przesuwane na ich końce. Schemat blokowy całego algorytmu jest przedstawiony na rysunku 1.1.

1.4. Schemat Hornera

Schemat Hornera jest najczęściej wykorzystywanym algorytmem obliczania wartości wielomianu

(1.9)

ze znanymi współczynnikami rzeczywistymi
Wyznaczanie wartości wielomianu dla x = ξ bezpośrednio ze wzoru (1.9) wymaga wykonania mnożeń i n dodawań. Stosując natomiast schemat Hornera:

(1.10)

odpowiadający obliczeniu wyrażenia

wartość wielomianu

(1.11)

otrzymujemy wykonując tylko n mnożeń i taką samą liczbę dodawań.

Liczby (1.10) są współczynnikami wielomianu

, (1.12)

będącego ilorazem uzyskanym przy dzieleniu danego wielomianu przez dwumian co wynika bezpośrednio z twierdzenia Bezouta [4]

(1.13)

Wstawiając bowiem wielomian (1.12) do wzoru (1.13), po uporządkowaniu wyrazów mamy

i następnie przez porównanie współczynników tego wielomianu ze współczynnika-mi wielomianu (1.9) dostajemy zależności (1.10) i (1.11).

{Program 1.1}

uses

Crt;

var

k,n: Integer;

ksi,P: Real;

a,b: array[0..20] of Real;

zn: Char;

label powt;

begin

powt:

ClrScr;

Writeln('PROGRAM 1.1');

Writeln('Schemat Hornera.');

Writeln;

Write('Stopien wielomianu - n = '); Read(n);

Writeln('Wspolczynniki wielomianu Pn(x):');

for k:=n downto 0 do begin

Write(' a[',k:2,'] = ');

Read(a[k]);

end;

Write('Argument - ksi = '); Readln(ksi);

P:=a[n]; b[0]:=P;

for k:=1 to n do begin

P:=P*ksi+a[n-k];

b[k]:=P;

end;

Writeln;

Writeln('Pn(ksi) = ',P:13);

Writeln('Wspolczynniki wielomianu Qn-1(x):');

14 1. Wprowadzenie do metod numerycznych

1.4. Schemat Hornera 15