Рассмотрим задачу вычисления значения полинома
`P(х) =a_n x^n+a_{n-1} x^{n-1}+...+ a_1 x+a_0`
в заданной точке `x`. Для вычисления `i`-го слагаемого требуется `i` умножений.
Схема Горнера — один из старых, но очень элегантных и эффективных алгоритмов для вычисления полиномов.
Этот алгоритм является хорошим примером использования метода изменения
представления, поскольку он основан на представлении при помощи формулы,
которая получается путем последовательного вынесения `x` за скобки с образованием полиномов с уменьшающимися
степенями:
`P(x) = (... (a_n x + a_{n-1}) x + ...)x + a_0`.
--
Алгоритм Horner (`P,x`)
// Входные данные: Массив `Р[0...n]` коэффициентов полинома
// степени `n` (хранятся от младшего к старшему) и число `х`
// Выходные данные: Значение полинома в точке `x`
`r larr P[n]`
**for** `i in [n-1...0]` **do**
`quad r larr x * r + P[i]`
**return** `r`
Количество умножений в алгоритме определяется формулой:
`M(n)=sum_{i=0}^{n-1} 1=n`
Начало
Учебные материалы
Метод преобразования