题目内容
已知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)时为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=65次.
第2个空中需注意,
P3(x0)=xP2(x0)+a3,
P2(x)=xP1(x0)+a2,
P1(x)=xP0(x0)+a1.
显然P0(x0)为常数不需计算.
∴计算为每次一个乘运算和一个加运算共3×2=6次.
由此可推得
P10(x0)=xP9(x0)+a10,
P9(x0)=xP8(x0)+a9,
……
P1(x)=xP0(x0)+a1.
答案:65 20
练习册系列答案
相关题目