Implementacja algorytmu (wersja iteracyjna) - PYI_R_W14_M30 Schemat Hornera - efektywna metoda obliczania wartości wielomianów

R1GFQ6NNTMUDK

Implementacja schematu Hornera - wersja iteracyjna

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

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)} = 6 x^{3} + 8 x^{2} - 2 x + 23$

Dla x = 2 jego wartość wynosi:

$W_{(X = 2)} = 6 \cdot 2^{3} + 8 \cdot 2^{2} - 2 \cdot 2 + 23 = 48 + 32 - 4 + 23 = 99$

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

$W_{(X = 2)} = 6 \cdot 2 \cdot 2 \cdot 2 + 8 \cdot 2 \cdot 2 - 2 \cdot 2 + 23 = 48 + 32 - 4 + 23 = 99$

Przykład 1

Zapiszemy algorytm tradycyjny, dzięki któremu będziemy mogli obliczyć wartość takiego wielomianu. W liście, która jest jednym z parametrów funkcji, współczynniki przy niewystępujących potęgach w wielomianie uzupełniamy zerami.

Zdefiniujmy funkcję, która wykorzystując ten algorytm obliczy wartość wielomianu.

def wielomian_iter(stopien, lista_wsp, argument):
	wynik = 0

	for i in range(stopien + 1):
		wynik += lista_wsp[i] * (argument ** (stopien - i))

	return f"Wynikiem dla argumentu {argument} jest wartość {wynik}"

# przykład wykonania
print(wielomian_iter(3, [6, 8, -2, 23], 7))
#Wynikiem dla argumentu 7 jest wartość 2459

Przykład 2

Zmodyfikujmy zapisaną funkcję w taki sposób, by obliczyć, ile operacji podstawowych było niezbędnych podczas wyznaczania wartości wielomianu.

def wielomian_iter_licz(stopien, lista_wsp, argument):
	wynik = lista_wsp[0]
	ile_oblicz = 0

	for _stopien in range(1, stopien + 1):
		wynik += lista_wsp[_stopien] * (argument ** _stopien)
		ile_oblicz += _stopien # liczba mnożeń
        ile_oblicz += 1 # liczba dodawań
            
	return f"Aby obliczyć wartość wielomianu konieczne jest {ile_oblicz} operacji podstawowych."	

# przykład wykonania
print(wielomian_iter_licz(3, [6, 8, -2, 23], 7))
#Aby obliczyć wielomian konieczne jest 9 operacji podstawowych.

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}) = (\dots ((a_{0} x + a_{1}) x + a_{2}) x + \dots + a_{n - 1}) x + a_{n}$

Kolejne współczynniki:

$a_{0} \dots a_{n}$

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)} = (\dots ((a_{0} x + a_{1}) x + a_{2}) x + \dots + a_{n - 1}) x + a_{n}$

Przykład 3

Zapiszemy algorytm obliczania wartości wielomianu za pomocą wersji iteracyjnej schematu Hornera.

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.

def horner_iter(wsp, x):
    stopien = len(wsp) - 1
    wynik = wsp[0]
    i = 0

    while i < stopien:
	    i += 1
	    wynik = wynik * x + wsp[i]

    return wynik

# przykładowe wykonanie
print(horner_iter([6,8, -2, 23], 7))
#2459

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

def horner_iter(wsp, x):
    zlicz = 0
    stopien = len(wsp) - 1
    wynik = wsp[0]
    i = 0

    while i < stopien:
	    i += 1
	    wynik = wynik * x + wsp[i]
		zlicz += 2

    return wynik, zlicz

# przykładowe wykonanie
print(horner_iter([6,8, -2, 23], 7))
#2459, 6

Słownik

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

wyrażenie algebraiczne będące sumą jednomianów, czyli wyrażeń postaci <math $a_{n} x^{n}$

stopień wielomianu

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

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

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, dla którego funkcja rekurencyjna nie wywołuje samej siebie, a zamiast tego zwraca z góry określoną wartość

wykonanie elementarne w rekurencji

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

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

(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

Animacja: jak działa iteracyjny schemat Hornera

Schemat Hornera krok po kroku - wersja rekurencyjna

Implementacja schematu Hornera - wersja iteracyjna

Obliczanie wartości wielomianu z zastosowaniem schematu Hornera

Słownik