Задача 32.
Вычислить значение полинома
f(x)=ax4+bx3+cx2+dx+e
для x=1, ..., 10000, используя не более 51000 операций *,+.
|
Решение задачи 32.
Пусть f(x)=ax4+bx3+cx2+dx+e. Выразим f(x+1) через f(x):
f(x+1)=f(x)+(4ax3+(6a+3b)x2+(4a+3b+2c)x+(a+b+c+d)=f(x)+g(x),
где
g(x)=Ax3+Bx2+Cx+D.
Поступим аналогично и с g(x): g(x+1)=g(x)+(3Ax2+(3A+2B)x+(A+B+C))=g(x)+h(x), где h(x)=A'x2+B'x+C'.
Далее:
h(x+1)=h(x)+(2A'x+(A'+B'))=h(x)+p(x),
где
p(x)=A"x+B". p(x+1)=p(x)+A".
Имеем:
f(x+4)=f(x+3)+g(x+3)
g(x+3)=g(x+2)+h(x+2)
h(x+2)=h(x+1)+p(x+1)
p(x+1)=p(x)+A".
Отсюда получаем фрагмент программы:
< BLOCK 1 >
x:=5;
repeat
P:=P+A2;
H:=H+P;
G:=G+H;
F:=F+G;
writeln(x,F);
x:=x+1;
until x=10001;
Итак, на каждое значение, начиная с 5, тратится 5 операций сложения. Остается около 1000 операций на вычисление f(1), f(2), f(3), f(4), для инициализации
P:=p(1); H:=h(2); G:=g(3); (F:=f(4));
и на вычисление A2:=A". Ясно, что 1000 операций хватит на все эти вычисления.
|
