Przeczytaj

Schemat Hornera – do czego służy?

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ć $\frac{n (n + 1)}{2}$ mnożeń oraz $n$ dodawań. Natomiast przy wykorzystaniu schematu Hornera wystarczy $n$ mnożeń oraz $n$ 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 $x$ ,
$x$ – 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 $n$ -tego stopnia wygląda następująco:

a_{0} \cdot x^{n} + a_{1} \cdot x^{n - 1} + a_{2} \cdot x^{n - 2} + . . . + a_{n - 1} \cdot x^{1} + a_{n} x^{0}

Zwróć uwagę na ostatni składnik. Omawianą formułę można zapisać również następująco:

a_{0} \cdot x^{n} + a_{1} \cdot x^{n - 1} + a_{2} \cdot x^{n - 2} + . . . + a_{n - 1} \cdot x + a_{n}

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 $x$ przed nawias, nie obejmując wyrazu wolnego:

x \cdot (a_{0} \cdot x^{n - 1} + a_{1} \cdot x^{n - 2} + a_{2} \cdot x^{n - 3} + . . . + a_{n - 1}) + a_{n}

Wewnątrz nawiasu powstał wielomian o stopniu $n - 1$ . Możemy go również przekształcić przez wyłączanie $x$ przed nawias:

x \cdot (x \cdot (a_{0} \cdot x^{n - 2} + a_{1} \cdot x^{n - 3} + a_{2} \cdot x^{n - 4} + . . . + a_{n - 2}) + a_{n - 1}) + a_{n}

Proces powtarzamy do momentu, w którym w najbardziej wewnętrznym nawiasie znajdzie się wielomian stopnia 1.

x \cdot (x \cdot (. . . x \cdot (a_{1} \cdot x + a_{2}) + . . .) + a_{n - 1}) + a_{n}

Chcąc wyznaczyć liczbę mnożeń, możemy zaobserwować, w jaki sposób obliczamy wartość powyższego wyrażenia dla danej wartości $x$ . 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 $x$ oraz dodajemy kolejny współczynnik. Obliczyliśmy wartość wielomianu stopnia drugiego. Czynności powtarzamy, aż do obliczenia wartości wielomianu stopnia $n$ , czyli $n$ razy. W każdej czynności wykonujemy jedno mnożenie oraz jedno dodawanie. Wyznaczona liczba mnożeń wynosi zatem $n$ .

Przykład

Przeanalizujmy przekształcenie wielomianu:

w (x) = 5 \cdot x^{3} + 3 \cdot x^{2} - x + 4

na formę odpowiadającą schematowi Hornera.

Zgodnie z postacią ogólną nasz wielomian będzie wyglądał następująco:

w (x) = 5 \cdot x^{3} + 3 \cdot x^{2} + (- 1) \cdot x^{1} + 4 \cdot x^{0}

Stopień tego wielomianu jest równy najwyższej potędze, do której jest podnoszona liczba $x$ . 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 $x$ . W tym wypadku wynoszą one: 5, 3, -1, 4.

Obliczając wartość tego wielomianu metodą standardową, wykonalibyśmy następującą liczbę mnożeń:

5 \cdot x \cdot x \cdot x + 3 \cdot x \cdot x + (- 1) \cdot x + 4

Trzy mnożenia, gdyż mnożymy 5 razy $x$ do potęgi 3, dwa mnożenia, by obliczyć 3 razy $x$ do kwadratu oraz mnożenie $x$ razy -1.

3 + 2 + 1 = 6

Przekształćmy teraz wyrażenie według zaprezentowanego algorytmu. Wyciągnijmy liczbę $x$ przed nawias:

x \cdot (5 \cdot x \cdot x + 3 \cdot x - 1) + 4

Jak możemy zauważyć, liczba $x$ występuje zarówno przy 5, jak i przy 3, zatem ponownie wyciągnijmy ją przed nawias:

x \cdot (x \cdot (5 \cdot x + 3) - 1) + 4

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ę $x$ 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.

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.

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].

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”.

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:

x^{4} + 2 \cdot x^{3} + x - 15

dla argumentu x = 4.

Dane po wczytaniu:

stopienWielomianu = 4
x = 4
wspolczynniki = {1, 2, 0, 1, -15}

Współczynnik zapisany pod indeksem 2 ma wartość zero, ponieważ w omawianym wielomianie nie ma zapisanego xIndeks górny 2.

Krok 1

wynik = 1

Krok 2

Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:

gdy i = 1:

wynik = wynik * x + wspolczynniki[i]

Po tym kroku wynik wynosi:

1 \cdot 4 + 2 = 6

Krok 3

Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:

gdy i = 2:

wynik = wynik * x + wspolczynniki[i]

Aktualnie wynik równa się:

6 \cdot 4 + 0 = 24

Krok 4

Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:

gdy i = 3:

wynik = wynik * x + wspolczynniki[i]

Po tym kroku wynik to:

24 \cdot 4 + 1 = 97

Krok 5

Wewnątrz pętli:
dla i = 1, 2, ... stopienWielomianu wykonuj:

gdy i = 4:

wynik = wynik * x + wspolczynniki[i]

W tym momencie wynik wynosi:

97 \cdot 4 + (- 15) = 373

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 0₀ = wspolczynniki[0]
aIndeks dolny n_n = x * aIndeks dolny n‑1_n‑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.

funkcja Horner(wspolczynniki[], stopienWielomianu, x)

Krok 3

W funkcji Horner() sprawdź, czy stopienWielomianu jest równy zero.

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.

funkcja Horner(wspolczynniki[], stopienWielomianu, x)
	jeżeli stopienWielomianu == 0:
    	zwróć wspolczynniki[0]

Krok 5

Jeśli tak nie jest, zwróć:

x * Horner(wspolczynniki,stopienWielomianu-1,x) + wspolczynniki[stopienWielomianu]

Oto gotowa funkcja:

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:

x^{4} + 2 \cdot x^{3} + x - 15

dla argumentu x = 4.

Dane po wczytaniu:

stopienWielomianu = 4
x = 4
wspolczynniki = {1, 2, 0, 1, -15}

Współczynnik zapisany pod indeksem 2 ma wartość zero, ponieważ w naszym wielomianie nie ma zapisanego xIndeks górny 2.