Schematu Hornera używamy do obliczania wartości wielomianu. Ten sposób działania zmniejsza liczbę potrzebnych mnożeń, dzięki czemu jest on wydajniejszy niż obliczanie wartości wielomianu w sposób standardowy. Jest to możliwe, ponieważ komputer nie zużywa czasu na zbędne mnożenia. Obliczając wartość wielomianu w sposób tradycyjny, musimy wykonać mnożeń oraz dodawań. Natomiast przy wykorzystaniu schematu Hornera wystarczy mnożeń oraz dodawań.
Wprowadzenie do algorytmu
W celu zrozumienia działania algorytmu obliczającego wartość wielomianu z wykorzystaniem schematu Hornera, wyjaśnijmy kilka pojęć:
stopień wielomianu – najwyższa potęga, do jakiej podnosimy ,
– liczba, dla której obliczamy wartość wielomianu,
współczynniki – liczby, przez które mnożymy kolejne składniki wielomianu.
Zadaniem algorytmu wykorzystującego schemat Hornera jest jak największe zredukowanie liczby mnożeń potrzebnych do obliczenia wartości wielomianu.
Postać ogólna wielomianu -tego stopnia wygląda następująco:
Zwróć uwagę na ostatni składnik. Omawianą formułę można zapisać również następująco:
W tej postaci mamy do czynienia z operacją potęgowania, która okazuje się zbędna, jeżeli za pomocą schematu Hornera przekształcimy wielomian. Zacznijmy od wyłączenia przed nawias, nie obejmując wyrazu wolnego:
Wewnątrz nawiasu powstał wielomian o stopniu . Możemy go również przekształcić przez wyłączanie przed nawias:
Proces powtarzamy do momentu, w którym w najbardziej wewnętrznym nawiasie znajdzie się wielomian stopnia 1.
Chcąc wyznaczyć liczbę mnożeń, możemy zaobserwować, w jaki sposób obliczamy wartość powyższego wyrażenia dla danej wartości . Zaczynamy od najbardziej zagnieżdżonego nawiasu. Wykonujemy jedno mnożenie oraz jedno dodawanie. Obliczyliśmy wartość wielomianu pierwszego stopnia. Następnie wynik mnożymy przez oraz dodajemy kolejny współczynnik. Obliczyliśmy wartość wielomianu stopnia drugiego. Czynności powtarzamy, aż do obliczenia wartości wielomianu stopnia , czyli razy. W każdej czynności wykonujemy jedno mnożenie oraz jedno dodawanie. Wyznaczona liczba mnożeń wynosi zatem .
Przykład
Przeanalizujmy przekształcenie wielomianu:
na formę odpowiadającą schematowi Hornera.
Zgodnie z postacią ogólną nasz wielomian będzie wyglądał następująco:
Stopień tego wielomianu jest równy najwyższej potędze, do której jest podnoszona liczba . Zatem w omawianym wypadku jest on równy 3. Współczynniki tego wielomianu to liczby, przez które są mnożone kolejne potęgi liczby . W tym wypadku wynoszą one: 5, 3, -1, 4.
Obliczając wartość tego wielomianu metodą standardową, wykonalibyśmy następującą liczbę mnożeń:
Trzy mnożenia, gdyż mnożymy 5 razy do potęgi 3, dwa mnożenia, by obliczyć 3 razy do kwadratu oraz mnożenie razy -1.
Przekształćmy teraz wyrażenie według zaprezentowanego algorytmu. Wyciągnijmy liczbę przed nawias:
Jak możemy zauważyć, liczba występuje zarówno przy 5, jak i przy 3, zatem ponownie wyciągnijmy ją przed nawias:
Policzmy, ile mnożeń wykonamy, chcąc obliczyć wartość tego wielomianu za pomocą schematu Hornera. Odpowiedź to 3.
Zmniejszenie liczby mnożeń wynika z tego, że wyciągnęliśmy liczbę przed nawias dwa razy.
Algorytm zapisany w sposób iteracyjny
Wzór iteracyjny algorytmu:
wynik = wspolczynnik[0]
wynik = wynik * x + wspolczynnik[i] dla i=1, 2,..., n
Specyfikacja:
Dane:
StopienWielomianu – zmienna określająca stopień wielomianu, który mamy obliczyć
wspolczynniki[] – tablica przechowująca współczynniki, przez które mnożymy daną potęgę liczby, dla której wartość wielomianu obliczamy
x – liczba, dla której obliczamy wartość wielomianu
Dane wyjściowe:
wynik – liczba, która określa obliczoną wartość wielomianu dla argumentu x.
Krok 1
Wczytaj dane.
Linia 1. wypisz cudzysłów Podaj stopień wczytywanego wielomianu dwukropek cudzysłów.
Linia 2. stopienWielomianu znak równości wprowadź liczbę całkowitą.
Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. wypisz cudzysłów Podaj współczynnik cudzysłów.
Linia 5. wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wprowadź liczbę.
Linia 6. wypisz cudzysłów Podaj argument przecinek dla którego chcesz obliczyć wielomian dwukropek cudzysłów.
Linia 7. x znak równości wprowadź liczbę.
wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0, 1, 2 ... stopienWielomianu wykonuj:
wypisz "Podaj współczynnik"
wspolczynniki[i] = wprowadź liczbę
wypisz "Podaj argument, dla którego chcesz obliczyć wielomian:"
x = wprowadź liczbę
Ważne!
Przy wczytywaniu współczynników wielomianu nie zapominajmy o wyrazie wolnym. Leży on przy wartości zmiennej x podniesionej do potęgi 0. Dlatego współczynników jest o jeden więcej niż wynosi wartość stopnia wielomianu.
Krok 2
Do zmiennej wynik przypisz wartość zmiennej zapisanej w tablicy wspolczynniki pod indeksem 0.
Linia 1. wypisz cudzysłów Podaj stopień wczytywanego wielomianu dwukropek cudzysłów.
Linia 2. stopienWielomianu znak równości wprowadź liczbę całkowitą.
Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. wypisz cudzysłów Podaj współczynnik cudzysłów.
Linia 5. wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wprowadź liczbę.
Linia 6. wypisz cudzysłów Podaj argument przecinek dla którego chcesz obliczyć wielomian dwukropek cudzysłów.
Linia 7. x znak równości wprowadź liczbę.
Linia 8. wynik znak równości wspolczynniki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0, 1, 2 ... stopienWielomianu wykonuj:
wypisz "Podaj współczynnik"
wspolczynniki[i] = wprowadź liczbę
wypisz "Podaj argument, dla którego chcesz obliczyć wielomian:"
x = wprowadź liczbę
wynik = wspolczynniki[0]
Krok 3
Do zmiennej wynik przypisz wartość: wynik * x + wspolczynniki[i].
Linia 1. wypisz cudzysłów Podaj stopień wczytywanego wielomianu dwukropek cudzysłów.
Linia 2. stopienWielomianu znak równości wprowadź liczbę całkowitą.
Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. wypisz cudzysłów Podaj współczynnik cudzysłów.
Linia 5. wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wprowadź liczbę.
Linia 6. wypisz cudzysłów Podaj argument przecinek dla którego chcesz obliczyć wielomian dwukropek cudzysłów.
Linia 7. x znak równości wprowadź liczbę.
Linia 8. wynik znak równości wspolczynniki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 9. dla i znak równości 1 przecinek 2 przecinek 3 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 10. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0, 1, 2 ... stopienWielomianu wykonuj:
wypisz "Podaj współczynnik"
wspolczynniki[i] = wprowadź liczbę
wypisz "Podaj argument, dla którego chcesz obliczyć wielomian:"
x = wprowadź liczbę
wynik = wspolczynniki[0]
dla i = 1,2,3... stopienWielomianu wykonuj:
wynik = wynik * x + wspolczynniki[i]
Krok 4
Wypisz „Wartość wielomianu dla argumentu x = wynik”.
Linia 1. wypisz cudzysłów Podaj stopień wczytywanego wielomianu dwukropek cudzysłów.
Linia 2. stopienWielomianu znak równości wprowadź liczbę całkowitą.
Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. wypisz cudzysłów Podaj współczynnik cudzysłów.
Linia 5. wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wprowadź liczbę.
Linia 6. wypisz cudzysłów Podaj argument przecinek dla którego chcesz obliczyć wielomian dwukropek cudzysłów.
Linia 7. x znak równości wprowadź liczbę.
Linia 8. wynik znak równości wspolczynniki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 9. dla i znak równości 1 przecinek 2 przecinek 3 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 10. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 11. wypisz cudzysłów Wartość wielomianu dla argumentu x znak równości cudzysłów.
Linia 12. wypisz wynik.
wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0, 1, 2 ... stopienWielomianu wykonuj:
wypisz "Podaj współczynnik"
wspolczynniki[i] = wprowadź liczbę
wypisz "Podaj argument, dla którego chcesz obliczyć wielomian:"
x = wprowadź liczbę
wynik = wspolczynniki[0]
dla i = 1,2,3... stopienWielomianu wykonuj:
wynik = wynik * x + wspolczynniki[i]
wypisz "Wartość wielomianu dla argumentu x = "
wypisz wynik
Przykładowe wykonanie algorytmu iteracyjnego
Oblicz wartość wielomianu, wykorzystując schemat Hornera:
Współczynnik zapisany pod indeksem 2 ma wartość zero, ponieważ w omawianym wielomianie nie ma zapisanego xIndeks górny 22.
Krok 1
wynik = 1
Krok 2
Linia 1. Wewnątrz pętli dwukropek.
Linia 2. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. gdy i znak równości 1 dwukropek.
Linia 6. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:
gdy i = 1:
wynik = wynik * x + wspolczynniki[i]
Po tym kroku wynik wynosi:
Krok 3
Linia 1. Wewnątrz pętli dwukropek.
Linia 2. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. gdy i znak równości 2 dwukropek.
Linia 6. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:
gdy i = 2:
wynik = wynik * x + wspolczynniki[i]
Aktualnie wynik równa się:
Krok 4
Linia 1. Wewnątrz pętli dwukropek.
Linia 2. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. gdy i znak równości 3 dwukropek.
Linia 6. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:
gdy i = 3:
wynik = wynik * x + wspolczynniki[i]
Po tym kroku wynik to:
Krok 5
Linia 1. Wewnątrz pętli dwukropek.
Linia 2. dla i znak równości 1 przecinek 2 przecinek kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. gdy i znak równości 4 dwukropek.
Linia 6. wynik znak równości wynik asterysk x plus wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:
gdy i = 4:
wynik = wynik * x + wspolczynniki[i]
W tym momencie wynik wynosi:
Tak obliczyliśmy wartość wielomianu metodą iteracyjnąiteracjaiteracyjną.
Algorytm zapisany w sposób rekurencyjny
W kolejnych krokach zaprezentujemy algorytm obliczania schematu Hornera zapisany metodą rekurencyjnąrekurencjametodą rekurencyjną.
Definicja rekurencyjna tego algorytmu:
aIndeks dolny 00 = wspolczynniki[0]
aIndeks dolny nn = x * aIndeks dolny n‑1n‑1 + wspolczynniki[n] dla n>0
Krok 1
Wczytaj dane w taki sposób, jak w algorytmie iteracyjnym.
Krok 2
Wywołaj funkcję Horner(), podając jako argumenty: wspolczynniki, stopienWielomianu, x.
W funkcji Horner() sprawdź, czy stopienWielomianu jest równy zero.
Linia 1. funkcja Horner otwórz nawias okrągły wspolczynniki otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek stopienWielomianu przecinek x zamknij nawias okrągły.
Linia 2. jeżeli stopienWielomianu znak równości znak równości 0 wykonaj dwukropek.
funkcja Horner(wspolczynniki[], stopienWielomianu, x)
jeżeli stopienWielomianu == 0 wykonaj:
Krok 4
Jeśli tak jest, zwróć wspolczynniki[0]. Jest to wykonanie elementarnewykonanie elementarne w rekurencjiwykonanie elementarne w naszej funkcji rekurencyjnej.
Linia 1. funkcja Horner otwórz nawias okrągły wspolczynniki otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek stopienWielomianu przecinek x zamknij nawias okrągły.
Linia 2. jeżeli stopienWielomianu znak równości znak równości 0 dwukropek.
Linia 3. zwróć wspolczynniki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
funkcja Horner(wspolczynniki[], stopienWielomianu, x)
jeżeli stopienWielomianu == 0:
zwróć wspolczynniki[0]
Krok 5
Jeśli tak nie jest, zwróć:
Linia 1. x asterysk Horner otwórz nawias okrągły wspolczynniki przecinek stopienWielomianu minus 1 przecinek x zamknij nawias okrągły plus wspolczynniki otwórz nawias kwadratowy stopienWielomianu zamknij nawias kwadratowy.
x * Horner(wspolczynniki,stopienWielomianu-1,x) + wspolczynniki[stopienWielomianu]
Oto gotowa funkcja:
Linia 1. wypisz cudzysłów Podaj stopień wczytywanego wielomianu dwukropek cudzysłów.
Linia 2. stopienWielomianu znak równości wprowadź liczbę całkowitą.
Linia 3. dla i znak równości 0 przecinek 1 przecinek 2 kropka kropka kropka stopienWielomianu wykonuj dwukropek.
Linia 4. wypisz cudzysłów Podaj cudzysłów.
Linia 5. wypisz i.
Linia 6. wypisz cudzysłów współczynnik cudzysłów.
Linia 7. wspolczynniki otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości wczytaj liczbę.
Linia 8. Wyswietl cudzysłów Podaj argument przecinek dla którego chcesz obliczyć wielomian dwukropek cudzysłów.
Linia 9. x znak równości wczytaj liczbę.
Linia 10. wynik znak równości Horner otwórz nawias okrągły wspolczynniki przecinek stopienWielomianu przecinek x zamknij nawias okrągły.
Linia 11. wypisz cudzysłów Wynik znak równości cudzysłów.
Linia 12. wypisz x.
Linia 14. funkcja Horner otwórz nawias okrągły wspolczynniki otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek stopienWielomianu przecinek x zamknij nawias okrągły.
Linia 15. jeżeli stopienWielomianu znak równości znak równości 0 wykonaj.
Linia 16. zwróć wspolczynniki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 17. w przeciwnym razie wykonaj dwukropek.
Linia 18. zwróć x asterysk Horner otwórz nawias okrągły wspolczynniki przecinek stopienWielomianu ‑ 1 przecinek x zamknij nawias okrągły plus wspolczynniki otwórz nawias kwadratowy stopienWielomianu zamknij nawias kwadratowy.
wypisz "Podaj stopień wczytywanego wielomianu: "
stopienWielomianu = wprowadź liczbę całkowitą
dla i = 0,1,2... stopienWielomianu wykonuj:
wypisz "Podaj "
wypisz i
wypisz " współczynnik"
wspolczynniki[i] = wczytaj liczbę
Wyswietl "Podaj argument, dla którego chcesz obliczyć wielomian:"
x = wczytaj liczbę
wynik = Horner(wspolczynniki, stopienWielomianu, x)
wypisz "Wynik = "
wypisz x
funkcja Horner(wspolczynniki[], stopienWielomianu, x)
jeżeli stopienWielomianu == 0 wykonaj
zwróć wspolczynniki[0]
w przeciwnym razie wykonaj:
zwróć x * Horner(wspolczynniki,stopienWielomianu ‑ 1,x) + wspolczynniki[stopienWielomianu]
Przykładowe wykonanie algorytmu rekurencyjnego
Oblicz wartość wielomianu, wykorzystując schemat Hornera:
Współczynnik zapisany pod indeksem 2 ma wartość zero, ponieważ w naszym wielomianie nie ma zapisanego xIndeks górny 22.
Krok 1
Wywołaj funkcję Horner(wspolczynniki, stopienWielomianu, x).
Krok 2
Sprawdź, czy stopienWielomianu jest równy 0.
Krok 3
W tym przypadku tak nie jest, zwróć:
x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]
Krok 4
Sprawdź, czy stopienWielomianu jest równy 0.
Krok 5
W tym przypadku tak nie jest, ponieważ stopienWielomianu = 3. Zwróć:
x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]
Krok 6
Sprawdź, czy stopienWielomianu jest równy 0.
Krok 7
W tym przypadku tak nie jest, ponieważ stopienWielomianu = 2. Zwróć:
x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]
Krok 8
Sprawdź, czy stopienWielomianu jest równy 0.
Krok 9
W tym przypadku tak nie jest, ponieważ stopienWielomianu = 1. Zwróć:
x * Horner(wspolczynniki,stopienWielomianu - 1,x) + wspolczynniki[stopienWielomianu]
Krok 10
Sprawdź, czy stopienWielomianu jest równy 0.
Krok 11
W tym przypadku tak jest. Zwróć wspolczynniki[0] równe 1.
Krok 12
Powróć do kroku 9.
x = 4
Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość wspolczynniki[0], co jest równe 1. Natomiast wspolczynniki[stopienWielomianu] jest równe 2.
Zatem:
Krok 13
Powróć do kroku 7.
x = 4
Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość obliczoną w kroku 12., co jest równe 6. Natomiast wspolczynniki[stopienWielomianu] jest równe 0.
Zatem:
Krok 14
Powróć do kroku 5.
x = 4
Funkcja Horner(wspolczynniki, stopienWielomianu - 1, x) zwróciła wartość obliczoną w kroku 13., co jest równe 24. Natomiast wspolczynniki[stopienWielomianu] jest równe 1.
Zatem:
Krok 15
Powróć do kroku 3.
x = 4
Funkcja Horner(wspolczynniki,stopienWielomianu - 1,x) zwróciła wartość obliczoną w kroku 13., co jest równe 97. Natomiast wspolczynniki[stopienWielomianu] jest równe -15.
Słownik
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
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ść
rekurencja
rekurencja
technika programowania polegająca na odwoływaniu się procedur lub funkcji do samych siebie, aż do momentu spełnienia warunku podstawowego
stopień wielomianu
stopień wielomianu
najwyższa potęga przy zmiennej, która nie jest równa zero
wielomian
wielomian
wyrażenie algebraiczne będące sumą jednomianów, czyli wyrażeń postaci aIndeks dolny nnxIndeks górny nn
William GeorgeHorner
William GeorgeHorner
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
wykonanie elementarne w rekurencji
wykonanie elementarne w rekurencji
moment, gdy funkcja rekurencyjna zwraca konkretną wartość zamiast kolejnego wywołania rekurencyjnego