Question

【题目】已知n次多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an,如果在一种算法中,计算(k=2,3,4,…,n)的值需要k-1次乘法,

(1)计算P3(x0)的值需要9次运算(6次乘法,3次加法),则计算Pn(x0)的值需要多少次运算?

(2)若采取秦九韶算法:P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1),计算P3(x0)的值只需6次运算,则计算Pn(x0)的值共需要多少次运算?

(3)若采取秦九韶算法,设ai=i+1,i=0,1,…,n,求P5(2)(写出采取秦九韶算法的计算过程).

Answer 1

【答案】(1), (2)2n, (3)120

【解析】试题分析：（1）若用普通的算法计算，计算乘法需要次，需要加法n次，从而得到答案；（2）若用秦九韶算法计算上式，则需要乘法n次，加法n次；（3）由P0(x)=a0,

Pk+1(x)=xPk(x)+ak+1,逐步计算即可.

试题解析：

直接法中乘法运算的次数最多可达到,加法最多n次.秦九韶算法通过转化把乘法运算的次数减少到最多n次,加法最多n次.

(1).

(2)2n.

(3)因为P0(x)=a0,

Pk+1(x)=xPk(x)+ak+1,

所以P0(2)=1,P1(2)=2P0(2)+2=4,

P2(2)=2P1(2)+3=11,

P3(2)=2P2(2)+4=26,

P4(2)=2P3(2)+5=57,

P5(2)=2P4(2)+6=120.