Jakub Piskorowski on 24/10/2023 wersja: 1.0
Przedstawienie działania algorytmu do szybkiego obliczania wartości wielomianu.
Kod źródłowy: schemat-hornera.cpp
📕 Poziom 3
Powrót do Algorytmika
Jednomian jest iloczynem liczb i liter (zmiennych).
Jednomian stopnia n - 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:
Do wyznaczenia wartości wielomianu tradycyjnym sposobem należy wykonać 6 mnożeń:
Schematem Hornera tych mnożeń należy wykonać tylko 3:
a więc mamy:
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.
K1: *wspolczynnik wskaźnik współczynnikó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ę wywyłanie funkcji Horner
K9: usunięcie tablicy wspolczynniki
Wejście
wsp[] - tablica z współczynnikami
st - stopień wielomianu
x - argument
Lista kroków:
K1: jeżeli st=0 wykonuj krok K2
zwróć wsp[0]
K2: 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
Kod źródłowy: schemat-hornera.cpp