Question

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

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

Answer 1

思路解析：由題意知道x₀^k的值需要k-1次運算,即進行k-1次x₀的乘法運算可得到x₀^k的結果.

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

a₁x₀²=a₁×x₀×x₀進行了2次運算,a₂x₀進行1次運算,最后a₀x₀³,a₁x₀²,a₂x₀,a₃之間的加法

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

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

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

由改進算法可知：

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₀.

運算次數從后往前算和為：2+2+…+2=2n次.

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

答案：65  20