Schemat Hornera krok po kroku - wersja iteracyjna - I_R_W14_M30_C++ Schemat Hornera - efektywna metoda obliczania wartości wielomianów

R1ZTXA71T59C7

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. Tę postać 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:

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. Wyłączmy $x$ przed nawias:

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

Jak możemy zauważyć, $x$ występuje zarówno przy 5, jak i przy 3, zatem ponownie wyłączmy $x$ 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 wyłączyliśmy $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ć wartość wielomianu:"
x = wprowadź liczbę

Ważne!

Przy wczytywaniu współczynników wielomianu nie zapominajmy o wyrazie wolnym, który znajduje się 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ć wartość wielomianu:"
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ć wartość wielomianu:"
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ć wartość wielomianu:"
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ą.

Słownik

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

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 (bazowy)

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

rekurencja

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

stopień wielomianu

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

wielomian

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

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

przypadek bazowy w rekurencji

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

Na dobry początek

Animacja: jak działa iteracyjny schemat Hornera

Schemat Hornera – do czego służy?

Wprowadzenie do algorytmu

Algorytm zapisany w sposób iteracyjny

Krok 1

Krok 2

Krok 3

Krok 4

Przykładowe wykonanie algorytmu iteracyjnego

Krok 1

Krok 2

Krok 3

Krok 4

Krok 5

Słownik