Schemat Hornera w Pythonie

powrót

Szczegóły działania algorytmu schematu Hornera opisane zostały w tym miejscu.

Zastosowanie

Schemat Hornera wykorzystujemy w sytuacji, gdy chcemy zamienić liczbę naturalną zapisaną w systemie o podstawie p na liczbę zapisaną w systemie dziesiętnym. Załóżmy, że mamy następującą liczbę binarną: $$(110010)_2$$Możemy ją zapisać w postaci wielomianu:$$W(x)=1\cdot x^5+1\cdot x^4+0\cdot x^3+0\cdot x^2+1\cdot x^1+0\cdot x^0$$Ponieważ podstawą systemu dwójkowego jest liczba 2, zatem podstawiamy$$x=2$$$$W(2)=1\cdot 2^5+1\cdot2^4+0\cdot2^3+0\cdot2^2+1\cdot2^1+0\cdot2^0=50$$otrzymując wartość dziesiętną liczby $$(110010)_2=50$$Szczegóły działania algorytmu omówię na zajęciach szkola-fraktal.pl

Schemat Hornera, wersja iteracyjna

#**********algorytm.edu.pl***************
# algorytm realizujący schemat Hornera
def horner(wsp, x):
    wynik = 0
    for i in wsp:
        wynik = wynik*x + i
    return wynik

# główna część programu

wsp = input("Podaj współczynniki wielomianu: ").split()

# rzutujemy listę napisów na listę liczb całkowitych
for i in range(len(wsp)):
    wsp[i] = int(wsp[i])

x = int(input("Podaj wartość wielomianu: "))

print(f"Wartość wielomianu o współczynnikach {wsp} w punkcie {x} wynosi", horner(wsp, x))

Wersja rekurencyjna

#**********algorytm.edu.pl***************
# algorytm realizujący schemat Hornera
def horner(lista_wspolczynnikow, nr, x): # współczynniki, nr współczynnika, wartość
    if nr == 0:
        return lista_wspolczynnikow[0]
    return x*horner(lista_wspolczynnikow, nr - 1, x) + lista_wspolczynnikow[nr]

# główna część programu

wsp = input("Podaj współczynniki wielomianu: ").split()

# rzutujemy listę napisów na listę liczb całkowitych
for i in range(len(wsp)):
    wsp[i] = int(wsp[i])

x = int(input("Podaj wartość wielomianu: "))

print(f"Wartość wielomianu o współczynnikach {wsp} w punkcie {x} wynosi", horner(wsp, len(wsp) - 1, x))