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