Схема Горнера
Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена p(x) по убыванию степеней:
p(x) = a0xn +a 1xn-1 + ... + an
Нужно вычислить значение многочлена в точке x = t. Алгоритм, основанный на просмотре последовательности коэффициентов в направлении от старшего к младшему, называется схемой Горнера. Проиллюстрируем его идею на примере многочлена третьей степени:
p(x) = ax3+bx2+cx+d
Его можно представить в виде
p(x) = ((ax+b)x+c)x+d
Для вычисления значения многочлена достаточно трех умножений и трех сложений. В общем случае, многочлен представляется в следующем виде:
p(x) = (...((a0x+a1)x+a2)x+...+an-1)x+an.
Обозначим через pk(x) многочлен k-ой степени, вычисленный по коэффициентам a0, a1, ..., ak:
pk(x) = a0xk + a1xk-1 + ... + ak.
Тогда
pk+1(x) = pk(x)x + ak+1
т.е. при считывании нового коэффициента многочлена надо старое значение многочлена умножить на значение x, а затем прибавить к нему новый коэффициент.
Выпишем алгоритм:
вещ алгоритм схема Горнера(вх: цел n, вещ a[n+1], вещ t) | дано: n -- степень многочлена | a[n+1] -- массив коэффициентов многочлена по | убыванию степеней | надо: вычислить значение многочлена в точке t начало алгоритма | вещ p; цел i; | p := 0.0; // Инициализация значения многочлена | i := 0; | цикл пока i <= n | | p := p * t + a[i]; // Вычисление нового значения по | | // старому значению и добавленному коэффициенту | | i := i + 1; | конец цикла | ответ := p; конец алгоритма
