1907967352

< 10 >

Informatyka +

najpierw wyłączamxz pierwszych trzech wyrazów, a następnie wyłączamyxz dwóch pierwszych wyrazów w nawiasie:

v(x) - ox³ + bx² *cx + d- v(x) - v(x) = (ax‘ + bx + c)x + d = ([a-x + b)-x + c)-x + d.

Widać z tego ostatniego wzoru, że wartość wielomiany stopnia 3 można obliczyć za pomocą 3 mnożeń i 3 dodawań.

Rozważmy teraz wielomian stopnia n:

w,0d - v"⁺ <V^fM+... + a_Mx * a_t    (1)

i zastosujmy grupowanie wyrazów podobnie, jak w wielomianie stopnia 3 - najpierw wyłączamy x ze wszystkich wyrazów z wyjątkiem ostatniego, a następnie stosujmy ten sam krok wielokrotnie do wyrazów, które będą pojawiały się w najgłębszych nawiasach, aż pozostanie jednomian:

w_o(x) = ajc + a_tx"-' *... + a_Mx + o„ = (o/"'¹ + d₁x*-²+... + o_M)x + a_n

-    ((a₀x"-» + a,x"-^J +... + a_n_)x* a_njx + a„ =

- (...((ryr + o,)x₊ a)x *... * ajx* a_n_)x * o„    (2)

Ćwiczenie 4. Przedstaw w postaci (2) następujące wielomiany: w(x) = 3x* - x³ + 5x^J + 7x - 2 w(x) =x^s -x³ + 4x³ + 3x-1

Zapiszmy teraz specyfikację, czyli dokładny opis rozważanego tutaj problemu:

Problem. Obliczanie wartości wielomianu

Dane:    n - nieujemna liczba całkowita - stopień wielomianu;

a₀, a_x,... o_n - n+1 współczynników wielomianu; z - wartość argumentu.

Wynik: Wartość wielomianu (2) stopnia n dla wartości argumentu x = z.

Aby obliczyć ze wzoru (2) wartość wielomianu dla wartości argumentu z, należy postępować następująco

(y oznacza pomocniczą zmienną):

V-o o y:=yz + a, y:=yz*o₇

Schemat Homera został podany przez jego autora w 1819 roku, chociaż znacznie wcześniej Isaac Newton stosował podobną metodę obliczania wartości wielomianów w swoich rachunkach fizycznych. W1971 roku, A. Borodin udowodnił, że schemat Homera jest optymalnym, pod względem liczby wykonywanych działań, algorytmem obliczania wartości wielomianu.

Wszystkie wiersze, z wyjątkiem pierwszego można zapisać w jednolity sposób - otrzymujemy wtedy:

(3)

y~o₀

y: = yz*a. dla/= 1,2.....n.

Ten sposób obliczania wartości wielomianu nazywa się schematem Homera.

Uwaga. W opisie algorytmu występuje instrukcja przypisania³, wcześniej już użyta, np. y := a₀, w której symbol := jest złożony z dwóch znaków: dwukropka i równości. Przypisanie oznacza nadanie wielkości (zmien-

Polecenie przypisania jest czasem nazywane niepoprawnie podstawieniem.