Метод преобразования

Рассмотрим задачу вычисления значения полинома
`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`