题目内容
已知n次多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an.如果在一种算法中,计算x0k(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算P10(x0)的值共需要_______________次运算.下面给出一种减少运算次数的算法:
P0(x)=a0,Pk+1(x)=xP1(x)+ak+1(k=0,1,2,…,n-1),利用该算法,计算P3(x0)的值共需要6次运算,计算P10(x0)的值共需要____________次运算.
解析：计算P3(x0)时为P3(x0)=a0x03+a1x02+a2x0+a3,其中x0k需k-1次乘法,
∴ an-k ·x0k共需k次乘法.
上式中运算为3+2+1=6次,另外还有三次加法,共有9次.由此产生的规律:
当计算P10(x0)时有P10(x0)=a0x010+a1x09+…+a10
计算次数为
+10=65(次).
第二问中需注意:
P3(x)=x·P2(x0)+a3,
P2(x)=x·P1(x0)+a2,
P1(x)=x·P0(x0)+a1.
显然P0(x0)为常数不需要计算.
所以计算为每次一个乘运算一个加运算共3×2=6(次).
P10(x0)=x·P9(x0)+x10,
P9(x0)=x·P8(x0)+a9,
……
P1(x0)=x·P0(x0)+a1.
其中共有10×2=20(个)运算过程.
答案：65 20
练习册系列答案
名校课堂系列答案
相关题目