HODNOTA POLYNOMU
PROBLÉM
Vypočítat hodnotu polynomu A.N*X**N+...+A.1*X+A.0 v bodě V.
ALGORITMUS
Efektivní algoritmus snižující na minimum počet násobení je známý jako Hornerovo schéma. Polynom stupně N tak může být vyhodnocen jen užitím N-1 operací násobení a N operací sčítání. Následující funkce předpokládá, že polynom je v paměti počítače reprezentován polem koeficientů.
IMPLEMENTACE
Jednotka: vnitřní funkce
Globální proměnné: vektor A.0,A.1,...,A.N reálných koeficientů
Parametry: přirozené číslo N - stupeň polynomu, reálné číslo V
Vrací: Hodnotu polynomu A. v bodě V
HORNER: procedure expose A.
parse arg N, V
P = A.N
do J = N - 1 to 0 by -1
P = P * V + A.J
end
return P
|
PŘÍKLAD
Hodnotou polynomu třetího stupně (N=3) 5*X**3+4*X-10 v bodě V=8 je 2582. Vit následující fragment programu
N = 3
A. = 0
A.3 = 5; A.1 = 4; A.0 = -10
V = 8
say HORNER(N, V)
exit
...
|
SOUVISLOSTI
Literatura
Sedgewick R. Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
