Jak już wiemy, schemat HorneraWilliam George HornerHornera jest wykorzystywany do obliczania wartości wielomianówwielomianwielomianów. Wykorzystamy tę metodę w czasie bieżącej lekcji.

Za przykład posłuży nam wielomian trzeciego stopnia. Obliczymy jego wartość dla wybranych argumentów. Zrobimy to na dwa sposoby: najpierw metodą tradycyjną wykonamy wszystkie operacje, a następnie skorzystamy ze schematu Hornera. Ostatecznie porównamy ilości wykonywanych operacji.

Ogólna postać wielomianu trzeciego stopnia to:

W(x)=a0x3+a1x2+a2x+a3

Możemy zapisać równanie obliczające jego wartość za pomocą wzoru:

Ważne!

Wielomian, którego stopień jest równy n, składa się z n + 1 składników.

A oto przykładowy wielomian trzeciego stopnia:

W(X)=6x3+8x22x+23

Dla x = 2 jego wartość wynosi:

W(X=2)=623+82222+23=48+324+23=99

Aby obliczyć wynik, trzeba sześć razy wykonać operację mnożenia oraz trzykrotnie operacje dodawania:

W(X=2)=6222+82222+23=48+324+23=99
1
Przykład 1

Zapiszemy algorytm tradycyjny, dzięki któremu będziemy mogli obliczyć wartość takiego wielomianu. Ponieważ użyjemy pętli for x in range(n+1), której wartość zmiennej sterującej x zwiększa się od 0 do n, więc współczynniki podamy jako listę elementów w kolejności od najmniejszego do największego wykładnika potęgi (od aIndeks dolny 3 do aIndeks dolny 0).

Linia 1. wielomian podkreślnik tradycyjnie otwórz nawias okrągły stopien przecinek wspolczynniki przecinek argument zamknij nawias okrągły. Linia 2. wynik przypisz 0. Linia 3. aktualny podkreślnik stopien przypisz 0. Linia 5. wykonaj stopien plus 1 razy. Linia 6. do wynik dodaj wspolczynniki otwórz nawias kwadratowy aktualny podkreślnik stopien zamknij nawias kwadratowy asterysk otwórz nawias okrągły argument podniesiony do potegi aktualny podkreślnik stopien zamknij nawias okrągły. Linia 7. zwiększ aktualny podkreślnik stopien o 1. Linia 9. wypisz wynik.

Zdefiniujmy funkcję, która wykorzystując ten algorytm obliczy wartość wielomianu. Współczynniki towarzyszące poszczególnym jednomianom (czyli czynniki aIndeks dolny n w wyrażeniach aIndeks dolny nxIndeks górny n) podamy w kolejności od najmniejszego do największego wykładnika potęgi (od aIndeks dolny 3 do aIndeks dolny 0):

Linia 1. def wielomian podkreślnik iter otwórz nawias okrągły stopien przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły dwukropek. Linia 2. wynik znak równości 0. Linia 4. for podkreślnik stopien in range otwórz nawias okrągły stopien plus 1 zamknij nawias okrągły dwukropek. Linia 5. wynik plus znak równości lista podkreślnik wsp otwórz nawias kwadratowy podkreślnik stopien zamknij nawias kwadratowy asterysk otwórz nawias okrągły argument asterysk asterysk podkreślnik stopien zamknij nawias okrągły. Linia 7. return f cudzysłów Wynikiem dla argumentu otwórz nawias klamrowy argument zamknij nawias klamrowy jest wartość otwórz nawias klamrowy wynik zamknij nawias klamrowy cudzysłów. Linia 9. kratka przykład wykonania. Linia 10. print otwórz nawias okrągły wielomian podkreślnik iter otwórz nawias okrągły 3 przecinek otwórz nawias kwadratowy 23 przecinek minus 2 przecinek 8 przecinek 6 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły zamknij nawias okrągły. Linia 11. Wynikiem dla argumentu 7 jest wartość 2459.
1
Przykład 2

Zmodyfikujmy zapisaną funkcję w taki sposób, by obliczyć, ile operacji podstawowych było niezbędnych podczas wyznaczania wartości wielomianu. Sprawdźmy, czy uzyskany wynik zgadza się z wartością obliczoną na początku lekcji (powinien on wynosić 9).

Linia 1. def wielomian podkreślnik iter podkreślnik licz otwórz nawias okrągły stopien przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły dwukropek. Linia 2. wynik znak równości lista podkreślnik wsp otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 3. ile podkreślnik oblicz znak równości 0. Linia 5. for podkreślnik stopien in range otwórz nawias okrągły 1 przecinek stopien plus 1 zamknij nawias okrągły dwukropek. Linia 6. wynik plus znak równości lista podkreślnik wsp otwórz nawias kwadratowy podkreślnik stopien zamknij nawias kwadratowy asterysk otwórz nawias okrągły argument asterysk asterysk podkreślnik stopien zamknij nawias okrągły. Linia 7. ile podkreślnik oblicz plus znak równości podkreślnik stopien kratka liczba mnożeń. Linia 9. ile podkreślnik oblicz plus znak równości 1 kratka liczba dodawań. Linia 11. return f cudzysłów Aby obliczyć wielomian konieczne jest otwórz nawias klamrowy ile podkreślnik oblicz zamknij nawias klamrowy operacji podstawowych kropka cudzysłów. Linia 13. kratka przykład wykonania. Linia 14. print otwórz nawias okrągły wielomian podkreślnik iter podkreślnik licz otwórz nawias okrągły 3 przecinek otwórz nawias kwadratowy 23 przecinek minus 2 przecinek 8 przecinek 6 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły zamknij nawias okrągły. Linia 15. Aby obliczyć wielomian konieczne jest 9 operacji podstawowych kropka.

Obliczanie wartości wielomianu z zastosowaniem schematu Hornera

Schemat Hornera optymalizuje ilość operacji arytmetycznych niezbędnych do obliczenia wartości wielomianu.

Wykorzystując go otrzymujemy wzór:

W(X)=(((a0x+a1)x+a2)x++an1)x+an

Kolejne współczynniki:

a0an

są mnożnikami potęg zmiennej x, zapisanymi od lewej do prawej strony wielomianu. Poszczególne wyrazy wielomianu (jednomiany) są zapisane od najwyższej potęgi zmiennej x do najniższej.

Po przekształceniu przykładowego wielomianu z wykorzystaniem schematu Hornera okazuje się, że w celu wyznaczenia wartości całego wyrażenia konieczne jest wykonanie trzech operacji mnożenia i trzech operacji dodawania:

W(X)=((6x+8)x2)x+23
1
Przykład 3

Zapiszemy algorytm obliczania wartości wielomianu za pomocą wersji iteracyjnej schematu Hornera. W liście, która jest jednym z parametrów funkcji, współczynniki podajemy w kolejności od najmniejszego stopnia do największego, a przy niewystępujących potęgach w wielomianie uzupełniamy zerami.

Linia 1. wielomian podkreślnik horner podkreślnik iteracyjnie otwórz nawias okrągły stopien przecinek wspolczynniki przecinek argument zamknij nawias okrągły. Linia 2. wynik przypisz wspolczynniki otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 4. wykonuj dopóki stopien zamknij nawias ostrokątny 0. Linia 5. zmniejsz stopien o 1. Linia 6. wynik przypisz wynik asterysk argument plus wspolczynniki otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 8. zwróć wynik.

Zdefiniujmy funkcję, która wykorzystując ten algorytm pozwoli nam obliczyć wartość wielomianu. Stopień wielomianu to najwyższa potęga x'a w tym wielomianie. W liście, która jest jednym z parametrów, współczynniki przy niewystępujących potęgach w wielomianie uzupełniamy zerami. Wówczas możemy pominąć podawanie stopnia jako parametru funkcji, gdyż będziemy mogli obliczyć go ze wzoru stopien = liczba współczynników -1.

Linia 1. def horner podkreślnik iter otwórz nawias okrągły wsp przecinek x zamknij nawias okrągły dwukropek. Linia 2. cudzysłów cudzysłów cudzysłów Wersja iteracyjna algorytmu Hornera kropka Współczynniki w liście wsp podajemy od końca cudzysłów cudzysłów cudzysłów. Linia 3. stopien znak równości len otwórz nawias okrągły wsp zamknij nawias okrągły minus 1. Linia 4. wynik znak równości wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 6. while stopien zamknij nawias ostrokątny 0 dwukropek. Linia 7. stopien znak równości stopien minus 1. Linia 8. wynik znak równości wynik asterysk x plus wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 10. return wynik. Linia 12. kratka przykładowe wykonanie. Linia 13. print otwórz nawias okrągły horner podkreślnik iter otwórz nawias okrągły otwórz nawias kwadratowy 23 przecinek minus 2 przecinek 8 przecinek 6 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły zamknij nawias okrągły. Linia 14. 2459.

Możemy również sprawdzić, ile operacji podstawowych wykonujemy w tej funkcji:

Linia 1. def horner podkreślnik iter podkreślnik ilosc podkreślnik oper otwórz nawias okrągły wsp przecinek x zamknij nawias okrągły dwukropek. Linia 2. cudzysłów cudzysłów cudzysłów Wersja iteracyjna algorytmu Hornera kropka Współczynniki w liście wsp podajemy od końca cudzysłów cudzysłów cudzysłów. Linia 3. stopien znak równości len otwórz nawias okrągły wsp zamknij nawias okrągły minus 1. Linia 4. wynik znak równości wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 5. zlicz znak równości 0. Linia 7. while stopien zamknij nawias ostrokątny 0 dwukropek. Linia 8. stopien znak równości stopien minus 1. Linia 9. wynik znak równości wynik asterysk x plus wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 10. zlicz plus znak równości 2 kratka 2 operacje podstawowe. Linia 12. return wynik przecinek zlicz. Linia 14. kratka przykładowe wykonanie. Linia 15. print otwórz nawias okrągły horner podkreślnik iter otwórz nawias okrągły otwórz nawias kwadratowy 23 przecinek minus 2 przecinek 8 przecinek 6 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły zamknij nawias okrągły. Linia 16. otwórz nawias okrągły 2459 przecinek 6 zamknij nawias okrągły.

Definiując funkcję rekurencyjną, będziemy musieli podać następujące dane wejściowe:

  • stopień wielomianu,

  • współczynniki kolejnych wyrazów wielomianu,

  • argument, dla którego obliczamy wartość wielomian.

1
Przykład 4

Wzór rekurencyjny obliczania wartości wielomianu za pomocą schematu Hornera możemy zapisać w następujący sposób:

Wn={a0dlan=0Wn1(x)x+andlan1

Zapiszemy algorytm rekurencyjny, który pozwala obliczyć wartość wielomianu z zastosowaniem schematu Hornera:

Linia 1. rek podkreślnik horner otwórz nawias okrągły stopien przecinek lista podkreślnik wspolczynnikow przecinek wartosc podkreślnik argumentu zamknij nawias okrągły. Linia 2. jesli stopien jest równy 0 przecinek zwróć lista podkreślnik wspolczynnikow otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 3. w przeciwnym przypadku. Linia 4. zwróć otwórz nawias okrągły wartosc podkreślnik argumentu. Linia 5. asterysk rek podkreślnik horner otwórz nawias okrągły stopien minus 1 przecinek lista podkreślnik wspolczynnikow przecinek wartosc podkreślnik argumentu zamknij nawias okrągły. Linia 6. plus lista podkreślnik wspolczynnikow otwórz nawias kwadratowy stopien zamknij nawias kwadratowy zamknij nawias okrągły.

Zdefiniujmy funkcję, która wykorzystując algorytm rekurencyjny obliczy wartość wielomianu. Współczynniki towarzyszące poszczególnym jednomianom (czyli czynniki aIndeks dolny n w wyrażeniach aIndeks dolny nxIndeks górny n) podamy w kolejności od największego do najmniejszego wykładnika potęgi (od aIndeks dolny 0 do aIndeks dolny 3):

Linia 1. def rek podkreślnik horner otwórz nawias okrągły stopien przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły dwukropek. Linia 2. if stopien znak równości znak równości 0 dwukropek. Linia 3. return lista podkreślnik wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 4. else dwukropek. Linia 5. return argument asterysk rek podkreślnik horner otwórz nawias okrągły stopien minus 1 przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły plus lista podkreślnik wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 7. kratka przykład wywołania. Linia 8. print otwórz nawias okrągły rek podkreślnik horner otwórz nawias okrągły 3 przecinek otwórz nawias kwadratowy 6 przecinek 8 przecinek minus 2 przecinek 23 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły zamknij nawias okrągły. Linia 9. 2459.

Sprawdźmy, ile operacji podstawowych trzeba wykonać w celu obliczenia wartości wielomianu z zastosowaniem metody rekurencyjnej.

Ważne!

Funkcja rekurencyjna wywołuje wielokrotnie siebie samą; w celu sprawdzenia liczby wykonywanych przez nią operacji musimy posłużyć się zmienną, która istnieje w przestrzeni nazwprzestrzeń nazwprzestrzeni nazw poza funkcją. Do tego celu użyjemy  zmiennej typu integer, który jest typem niezmiennymniezmiennaniezmiennym. Aby zmieniać wartość takiej zmiennej z wnętrza funkcji, musimy zadeklarować dostęp do niej za pomocą słowa kluczowego global. Dzięki temu będziemy mogli zmieniać wartość zmiennej, która istnieje „poza” funkcją, a jest niezmiennaniezmiennaniezmienna.

1
Przykład 5

Zdefiniujemy funkcję, która poda liczbę wykonanych operacji arytmetycznych podczas wyznaczania wartości wielomianu z zastosowaniem metody rekurencyjnej:

Linia 1. def rek podkreślnik horner podkreślnik licz otwórz nawias okrągły stopien przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły dwukropek. Linia 2. global zlicz. Linia 4. if stopien znak równości znak równości 0 dwukropek. Linia 5. return lista podkreślnik wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy. Linia 6. else dwukropek. Linia 7. zlicz plus znak równości 2 kratka jedno wywołanie funkcji to 2 operacje podstawowe. Linia 8. return argument asterysk rek podkreślnik horner podkreślnik licz otwórz nawias okrągły stopien minus 1 przecinek lista podkreślnik wsp przecinek argument zamknij nawias okrągły plus lista podkreślnik wsp otwórz nawias kwadratowy stopien zamknij nawias kwadratowy.

Spróbujmy uruchomić funkcję; pamiętajmy o wcześniejszym zadeklarowaniu zmiennej zlicz oraz o wyświetleniu jej wartości po zakończeniu działania funkcji:

Linia 1. kratka inicjujemy zmienną przecinek w której będziemy zliczać ilości wykonania. Linia 2. zlicz znak równości 0. Linia 4. kratka uruchamiamy właściwą funkcję. Linia 5. rek podkreślnik horner podkreślnik licz otwórz nawias okrągły 3 przecinek otwórz nawias kwadratowy 6 przecinek 8 przecinek minus 2 przecinek 23 zamknij nawias kwadratowy przecinek 7 zamknij nawias okrągły. Linia 7. kratka sprawdzamy wartość zmiennej. Linia 8. print otwórz nawias okrągły zlicz zamknij nawias okrągły. Linia 9. 6.
1
Polecenie 1

Bazując na postaci rekurencyjnej funkcji obliczającej wartość wielomianu, spróbujmy zapisać ją używając wyrażenia trójargumentowego.

Dla zainteresowanych

Dla języka Python opracowano moduł o nazwie SymPy – pozwala on na zapisywanie wyrażeń algebraicznych i obliczanie ich wartości.

Słownik

William George Horner
William George Horner

brytyjski matematyk żyjący w latach 1786–1837; w wieku 14 lat został asystentem nauczyciela w szkole w Bristolu, a w 1809 roku założył własną szkołę w Bath; podał sposób wyznaczania wartości wielomianu z wykorzystaniem minimalnej liczby operacji możenia

wielomian
wielomian

wyrażenie algebraiczne będące sumą jednomianów, czyli wyrażeń postaci aIndeks dolny nxIndeks górny n

stopień wielomianu
stopień wielomianu

najwyższa potęga przy zmiennej, która nie jest równa zero

algorytm
algorytm

przepis postępowania prowadzący do rozwiązania ustalonego problemu, określający ciąg czynności elementarnych, które należy w tym celu wykonać

iteracja
iteracja

technika programowania polegająca na powtarzaniu tych samych operacji w pętli określoną liczbę razy lub do momentu, aż zostanie spełniony zadany warunek

rekurencja
rekurencja

technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego

przypadek podstawowy
przypadek podstawowy

przypadek, dla którego funkcja rekurencyjna nie wywołuje samej siebie, a zamiast tego zwraca z góry określoną wartość

wykonanie elementarne w rekurencji
wykonanie elementarne w rekurencji

moment, gdy funkcja rekurencyjna zwraca konkretną wartość zamiast kolejnego wywołania rekurencyjnego

przestrzeń nazw
przestrzeń nazw

(ang. namespace) - miejsce w pamięci operacyjnej, w której przechowywana jest dana zmienna; najczęściej przestrzeń nazw związana jest z funkcją, a zmienne używane w niej są widoczne tylko w obrębie tej przestrzeni - jest to „zakres obowiązywania” tych zmiennych

niezmienna
niezmienna

(ang. immutable) sekwencja lub zmienna, która jest niemodyfikowalna „w miejscu”, a więc nie można zmienić żadnego z jej elementów wewnątrz, trzeba stworzyć nowy obiekt, który zawiera zmienione elementy