Основы программирования

Схема Горнера


Рассмотрим еще один важный пример функции на последовательности. Пусть дана последовательность коэффициентов многочлена 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; конец алгоритма



Содержание раздела