Решение 50 типовых задач по программированию на языке Pascal Дата размещения сборника в сети

Задача № 27. Вычислить значение многочлена в точке 
Формулировка. Дано натуральное число n, вещественное число x и набор вещественных чи-
сел a
n
, a
n-1
, ..., a
0
. 
Вычислить значение многочлена n-ной степени с коэффициентами a
n
, a
n-1
, ..., a
0
от одной переменной в точке x. 
Примечание: многочленом n-ной степени от одной переменной x называется выражение вида 
a
n
x
n
+ a
n-1
x
n-1
+ ... + a
1
x + a
0
, 
где a
n
, a
n-1
, ..., a
0
– 
коэффициенты. 

---

Данил Душистов: «Решение 50 типовых задач по программированию на языке Pascal» 
32 
Решение. Собственно, в этой задаче требуется возведение переменной x (точнее, конкретного 
ее значения) в некоторую степень n – 1 раз, а также n операций умножения и n операций сложения. 
В принципе, для полноценного решения она не требует одновременного знания более чем одного 
коэффициента, так как мы можем в цикле ввести коэффициент a
n
в переменную a, умножить его на 
x
n
и прибавить полученное число к переменной результата res (которой перед входом в цикл должно 
быть присвоено значение 0) и повторить этот шаг для всех коэффициентов. Тогда количество опе-
раций: (1 + 2 + ... + n + 2n), что примерно соответствует асимптотической сложности O(n
2
). 
Не занимаясь реализацией этого алгоритма, давайте оптимизируем его. Например, пусть нам 
дан многочлен третьей степени a
3
x
3
+ a
2
x
2
+ a
1
x + a
0
. 
Вынесем за скобки общий множитель x при 
слагаемых, в которых это возможно. Получим: (a
3
x
2
+ a
2
x + a
1
)x + a
0
. 
Вынесем за скобки x также и в 
полученном выражении со скобками, в итоге получим: ((a
3
x + a
2
)x + a
1
)x + a
0
. 
Полученную форму записи называют схемой Горнера. Очевидно, что она существует для мно-
гочлена любой степени. 
Итак, имея n = 3 и коэффициенты a