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.