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 ₀）的值共需要_______次運算.

下面給出一種減少運算次數(shù)的算法：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的結(jié)果對于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次加法運算總共進行了+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₀.

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

答案: n(n+3)  2n