题目内容
已知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)=xPk(x)+ak+1(k=0,1,2,…,n-1),利用该算法,计算P3(x0)的值共需要6次运算,计算P10(x0)的值共需要______________________次运算.
解析：计算P3(x0)=a0x03+a1x02+a2x0+a3,
其中x0k需k-1次乘法,
∴an-k·x0k共需k次乘法.
上式中运算为3+2+1=6次,另外还有3次加法,共9次.
由此产生规律：当计算P10(x0)时,有P10(x0)=a0x010+a1x09+…+a10
计算次数为10+9+8+…+1+10=
+10=65次.
第2问中需注意
P3(x0)=x·P2(x0)+a3,
P2(x0)=x·P1(x0)+a2,
P1(x0)=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
练习册系列答案
相关题目