Question

已知n次多項(xiàng)式P_n(x)=a₀xⁿ+a₁x^n-1+…+a_n-1x+a_n,如果在一種算法中，計(jì)算x₀^k（k=2，3，4，…，n）的值需要k-1次乘法，計(jì)算P₃(x₀)的值共需要9次運(yùn)算（6次乘法，3次加法），那么計(jì)算P₁₀(x₀)的值共需要___________次運(yùn)算．

下面給出一種減少運(yùn)算次數(shù)的算法：P₀(x)=a₀,P_k+1(x)=xP_k(x)+a_k+1（k=0， 1，2，…，n-1）．利用該算法，計(jì)算P₃(x₀)的值共需要6次運(yùn)算，計(jì)算P₁₀(x₀)的值共需要______________次運(yùn)算.

Answer 1

思路解析：由題意知道x₀^k的值需要k-1次運(yùn)算,即進(jìn)行k-1次x₀的乘法運(yùn)算可得到x₀^k的結(jié)果.

對于P₃(x₀)=a₀x₀³+a₁x₀²+a₂x₀+a₃,這里a₀x₀³=a₀×x₀×x₀×x₀進(jìn)行了3次運(yùn)算,

a₁x₀²=a₁×x₀×x₀進(jìn)行了2次運(yùn)算,a₂x₀進(jìn)行1次運(yùn)算,最后a₀x₀³,a₁x₀²,a₂x₀,a₃之間的加法

運(yùn)算進(jìn)行了3次,這樣P₃(x₀)總共進(jìn)行了3+2+1+3=9次運(yùn)算.

對于P_n(x₀)=a₀x₀ⁿ+a₁x₀^n-1+…+a_n總共進(jìn)行了n+n-1+n-2+…+1=次乘法運(yùn)算及n次加法運(yùn)算,總共進(jìn)行了次,

因此P₁₀(x₀)需要進(jìn)行=65次.

由改進(jìn)算法可知：

P_n(x₀)=x₀P_n-1(x₀)+a_n,P_n-1(x₀)=x₀P_n-2(x₀)+a_n-1…P₁(x₀)=P₀(x₀)+a₁,P₀(x₀)=a₀.

運(yùn)算次數(shù)從后往前算和為：2+2+…+2=2n次.

因此P₁₀(x₀)共需要20次運(yùn)算.

答案：65  20