Schemat Hornera - teoria

Schemat Hornera to efektywna metoda obliczania wartości wielomianu w zadanym punkcie. Dzięki redukcji liczby mnożeń i dodawań pozwala na szybsze i bardziej precyzyjne obliczenia w porównaniu do standardowego sposobu.

• Jednomian jest iloczynem liczb i liter (zmiennych).

• Jednomian stopnia n (wielomian) - to funkcja postaci: y = ax^n

Schemat Hornera jest algorytmem służącym do bardzo szybkiego obliczania wartości wielomianu. Redukuje on ilość mnożeń do minimum. Przeanalizujmy następujący wielomian:

• W(x) = 3x³ + 3x² - 2x + 11

Do wyznaczenia wartości wielomianu tradycyjnym sposobem należy wykonać 6 mnożeń:

• W(x) = 3 * x * x * x + 3 * x * x - 2 * x + 11

Schematem Hornera tych mnożeń należy wykonać tylko 3:

• W(x) = 3 * x³ + 3x² -2x + 11 = x * (3 * x² + 3x - 2) + 11 = x * ( x * (3 * x + 3) - 2) + 11

a więc mamy:

• W(x) = x * (x * (3 * x + 3) - 2) + 11

Danymi wejściowymi będą współczynniki wielomianu oraz jego stopień. Następnie podamy argument, dla jakiego chcemy wyznaczyć wartość wielomianu. Zauważmy, że wielomian, którego stopień jest równy n ma n + 1 czynników.

Pseudokod - Schemat Hornera

W każdym kroku algorytmu wynik jest sukcesywnie obliczany poprzez przemnażanie dotychczasowej wartości przez zmienną x i dodawanie kolejnych współczynników wielomianu. Dzięki temu eliminowana jest konieczność osobnego potęgowania, co znacząco poprawia wydajność obliczeń.

Algorytm obliczania wartości wielomianu

Lista kroków:

K2:   stopien, argument   (deklaracja zmiennych stopnia oraz argumentu)
K3:   pobranie stopnia wielomianu   (pobranie od użytkownika wartości)
K4:   *wspolczynnik ← new int [stopien+1]   (deklaracja dynamicznej tablicy)
k5:   dopóki i < stopien   (wczytanie współczynników)
      wykonuj krok K6
K6:   wprowadź wspolczynnik[i]
K7:   pobranie argumentu   (pobranie od użytkownika argumentu wielomianu)
K8:   wywołaj funkcję   (wywołanie funkcji Horner)
K9:   usunięcie tablicy wspolczynniki

Funkcja Hornera rekurencyjnie

Wejście

• wsp[] - tablica z współczynnikami

• st - stopień wielomianu

• x - argument

Lista kroków:

K1:   jeżeli st=0   wykonuj krok K2
K2:     zwróć wsp[0]
K3:   zwróć x * funkcja(wsp, st-1, x) + wsp[st]

Wynik działania programu:

Podaj stopien wielomianu: 3
Podaj wspolczynnik stojacy przy potedze 3: 3
Podaj wspolczynnik stojacy przy potedze 2: 3
Podaj wspolczynnik stojacy przy potedze 1: -2
Podaj wspolczynnik stojacy przy potedze 0: 11
Podaj argument: 1
W( 1 ) = 15