题目内容
已知n次项式Pn(x)=a0xn+a1xn-1+…+an-1x+an.如果在一种算法中，计算x0 k(k=2,3,4,…,n)的值需要k－1次乘法，计算P3（x0）的值共需要9次运算（6次乘法，3次加法），那么计算P10（x 0）的值共需要_______次运算.下面给出一种减少运算次数的算法：P 0（x）=a 0，P k+1（x）=xP k（x）+a k+1（k=0，1，2，…，n－1）.利用该算法，计算P 3（x 0）的值共需要6次运算，计算P10（x 0）的值共需要________次运算.
解析:由题意知道x0 k的值需要k-1次运算,即进行k-1次x0的乘法运算可得到x0 k的结果对于P3(x0)=a0x03+a1x02+a2x0+a3这里a0x03=a0×x0×x0×x0进行了3次运算,a1x02=a1×x0×x0进行了2次运算,a2x0进行1次运算,最后a0x03,a1x02,a2x0,a3之间的加法运算进行了3次这样P3(x0)总共进行了3+2+1+3=9次运算.
对于Pn(x0)=a0x0n+a1x0 n-1+…+an总共进行了n+n-1+n-2+…+1=
次.
乘法运算及n次加法运算总共进行了
+n=
次.
由改进算法可知：
Pn(x0)=x0Pn-1(x0)+an,P n-1(x0)=x0P n-2(x0)+a n-1,…,P1(x0)=P0(x0)+a1,P0(x0)=a0.
运算次数从后往前算和为：2+2+…+2=2n次.
答案: 
n(n+3) 2n
练习册系列答案
相关题目
(k＝2，3，4，…，n)的值需要k－1次乘法，计算P3(x0)的值共需要9次运算(6次乘法，3次加法)，那么计算P10(x0)的值共需要_________次运算．