Schemat Hornera
Schemat Hornera
Schemat Hornera
Schemat Hornera
Wykorzystanie schematu
Wykorzystanie schematu
Hornera
Hornera
Jest algorytmem klasycznym służącym do:
•
szybkiego obliczania wartości wielomianu,
•
przeliczania na postać dziesiętną liczb zapisanych w innym
systemie liczbowym
•
szybkiego podnoszenia do potęgi.
Analiza liczby działań (+, *) wykonanych
Analiza liczby działań (+, *) wykonanych
podczas obliczania wartości wielomianu
podczas obliczania wartości wielomianu
Stopie
Stopie
ń
ń
wielo
wielo
m.
m.
Postać wielomianu
Postać wielomianu
Liczba działań
Liczba działań
+
+
*
*
2
2
y=a
y=a
0
0
x
x
2
2
+a
+a
1
1
x+a
x+a
2
2
2
2
3
3
y=( a
y=( a
0
0
x + a
x + a
1
1
)x+ a
)x+ a
2
2
2
2
2
2
3
3
y=a
y=a
0
0
x
x
3
3
+a
+a
1
1
x
x
2
2
+a
+a
2
2
x+ a
x+ a
3
3
3
3
6
6
y=(( a
y=(( a
0
0
x + a
x + a
1
1
)x+ a
)x+ a
2
2
)x+ a
)x+ a
3
3
3
3
3
3
4
4
y=a
y=a
0
0
x
x
4
4
+a
+a
1
1
x
x
3
3
+a
+a
2
2
x
x
2
2
+ a
+ a
3
3
x + a
x + a
4
4
4
4
10
10
y=((( a
y=((( a
0
0
x + a
x + a
1
1
)x+ a
)x+ a
2
2
)x+ a
)x+ a
3
3
) x
) x
+ a
+ a
4
4
4
4
4
4
n
n
y=a
y=a
0
0
x
x
n
n
+a
+a
1
1
x
x
n-1
n-1
+…+a
+…+a
n-2
n-2
x
x
2
2
+ a
+ a
n-1
n-1
x + a
x + a
n
n
n
n
n(n+1)
n(n+1)
/2
/2
y=((…( a
y=((…( a
0
0
x + a
x + a
1
1
)x+…+ a
)x+…+ a
n-2
n-2
)x+ a
)x+ a
n-1
n-1
) x
) x
+
+
a
a
n
n
n
n
n
n
Zasada postępowania podczas obliczania
Zasada postępowania podczas obliczania
wartości wielomianu z zastosowaniem
wartości wielomianu z zastosowaniem
schematu Hornera
schematu Hornera
W celu obliczenia jego wartości, za początkową wartość wielomianu
należy przyjąć wartość współczynnika
a
0
, przy najwyższej potędze
zmiennej. Za każdym razem należy aktualną wartość wielomianu
pomnożyć przez
x
i dodać kolejny współczynnik.
Algorytm ten, zwany
schematem Hornera
, można zapisać
następująco:
y:= a
0
wartość początkowa wielomianu
y:= y*x+a
i
dla
i
=1,2,3,4,...,
n
– czynnik powtarzający się
(iteracja)
Schemat Hornera -lista kroków
Schemat Hornera -lista kroków
Specyfikacja
Dane
:
n
- nieujemna liczba całkowita (stopień wielomianu)
a
0
, a
1
, a2, ..., a
n
n+1 współczynników wielomianu
x
- wartość argumentu
Wynik
: Wartość wielomianu stopnia
n
dla wartości argumentu
x
Krok1
.
Za początkową wartość wielomianu przyjmij współczynnik
wielomianu przy zmiennej o najwyższej potędze.
y :=a
0
{y- zmienna pomocnicza}
Krok2
.
n
razy oblicz wartość dwumianu
y:=y*x+a
i
kolejnych
współczynników wielomianu, czyli dla
i
=1,2,...,n
Schemat blokowy
Schemat blokowy
START
Wprowadź (n, x, a
i
, gdzie
i=0..n)
STOP
n=3, x=1, a={1,2,3,4}
y=1, i=1
KROK I
1>3
Nie
y=1*1+2; i=1+1
KROK II
2>3
Nie
Y=3*1+3; i=2+1
KROK III
3>3
Nie
y=6*1+4; i=3+1
KROK IV
4>3
Tak
Wypr
10
y :=y*x+a
i
i:=i+1
NIE
y := a
0
i:=1
i>n
TA
K
Wypr (y)
Zadania
Zadania
Zadanie1
Rozpisz wielomian 5 stopnia tak, aby można było obliczyć jego wartość
z zastosowaniem schematu Hornera.
Zadanie2
Oblicz, ile należy wykonać działań mnożenia i dodawania dla obliczenia
wartości wielomianu W(x) metodą klasyczną i za pomocą schematu
Hornera:
• 5 stopnia
• n-tego stopnia
Zadanie3
Wykonaj program obliczający wartość wielomianu stopnia
n
-tego za pomocą
schematu Hornera.
Współczynniki wielomianu:
a) wprowadź z klawiatury
b) generuj losowo
c) ustaw jako wartości stałe