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

3
, a
2
, a
1
и a
0
, 
мы можем посчитать его значение с помощью 
n 
операций умножения и n операций сложения, а это значит, что для вычисления требуется порядка 
2n 
операций и алгоритм имеет линейную асимптотическую сложность O(n), что демонстрирует оче-
видное преимущество перед предыдущим решением. 
Посмотрим, как может выглядеть цикл, в котором вычисляется значение многочлена в точке. 
Для этого немного изменим представление в виде схемы Горнера, не меняя при этом значения мно-
гочлена: (((0x + a
3
)x + a
2
)x + a
1
)x + a
0
. 
Теперь нам требуется n + 1 операций, однако заведя переменную res для накопления резуль-
тата, которая перед входом в цикл будет равна 0, мы можем, вводя коэффициенты a
3
, a
2
, a
1
и a
0
, 
посчитать значение многочлена в одном цикле: 
res := 0; 
for i := 1 to n + 1 do begin 
read(a); 
res := res * x + a 
end; 
Примечание: оператор read нужен нам для того, чтобы можно было вводить коэффициенты 
через пробел, а не через Enter. 
Теперь разберем сам цикл. На первом шаге мы получаем в res значение выражения 0x + a
3
= 
a
3
, 
на втором – a
3
x + a
2
, 
на третьем – (a
3
x + a
2
)x + a
1
, 
на четвертом – ((a
3
x + a
2
)x + a
1
)x + a
0
. 
Как видно, 
формула полностью восстановилась, причем вычисление идет от наиболее вложенных скобок к 
верхним уровням. 
Код: 
1.
program ValueOfPolynomial; 
2.
3.
var 
4.
i, n: byte; 
5.
x, a, res: real; 
6.
7.
begin 
8.
readln(n, x); 
9.
res := 0; 
10.
for i := 1 to n + 1 do begin 
11.
read(a); 
12.
res := res * x + a 
13.
end; 
14.
writeln(res:4:2) 

---