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

R1GFQ6NNTMUDK

Implementacja schematu Hornera - wersja rekurencyjna

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.

Przykład 1

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

$W_{n} = {\begin{array}{lc} a_{0} & dla n = 0 \\ W_{n - 1} (x) \cdot x + a_{n} & dla n \geq 1 \end{array}$

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

rek_horner(stopien, lista_wspolczynnikow, wartosc_argumentu)
	jesli stopien jest równy 0, zwróć lista_wspolczynnikow[0]
	w przeciwnym przypadku 
		zwróć (wartosc_argumentu 
		* rek_horner(stopien - 1, lista_wspolczynnikow, wartosc_argumentu) 
		+ lista_wspolczynnikow[stopien])

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 $a_{n} x^{n}$ ) podamy w kolejności od największego do najmniejszego wykładnika potęgi (od $a_{0}$ do $a_{3}$ ):

def rek_horner(stopien, lista_wsp, argument):
	if stopien == 0:
		return lista_wsp[stopien]
	else:
		return argument * rek_horner(stopien - 1, lista_wsp, argument) + lista_wsp[stopien]
    
# przykład wywołania
print(rek_horner(3, [6, 8, -2, 23], 7))
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 nazw poza funkcją. Do tego celu użyjemy zmiennej typu integer, który jest typem niezmiennym. 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 niezmienna.

Przykład 2

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

def rek_horner_licz(stopien, lista_wsp, argument):
	global zlicz

	if stopien == 0:
		return lista_wsp[stopien]
	else:
		zlicz += 2 # jedno wywołanie funkcji to 2 operacje podstawowe
		return argument * rek_horner_licz(stopien - 1, lista_wsp, argument) + lista_wsp[stopien]

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:

# inicjujemy zmienną, w której będziemy zliczać ilości wykonania
zlicz = 0

# uruchamiamy właściwą funkcję
rek_horner_licz(3, [6, 8, -2, 23], 7)

# sprawdzamy wartość zmiennej
print(zlicz)
6

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.

Schemat Hornera krok po kroku - wersja rekurencyjna

Misja: Ćwicz i zwyciężaj