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₁(x)+a_k+1(k=0,1,2,…,n-1),利用該算法,計算P₃(x₀)的值共需要6次運算,計算P₁₀(x₀)的值共需要____________次運算.

Answer 1

解析：計算P₃(x₀)時為P₃(x₀)=a₀x₀³+a₁x₀²+a₂x₀+a₃,其中x₀^k需k-1次乘法,

∴ a_n-k ·x₀^k共需k次乘法.

上式中運算為3+2+1=6次,另外還有三次加法,共有9次.由此產生的規律:

當計算P₁₀(x₀)時有P₁₀(x₀)=a₀x₀¹⁰+a₁x₀⁹+…+a₁₀

計算次數為+10=65(次).

第二問中需注意:

P₃(x)=x·P₂(x₀)+a₃,

P₂(x)=x·P₁(x₀)+a₂,

P₁(x)=x·P₀(x₀)+a₁.

顯然P₀(x₀)為常數不需要計算.

所以計算為每次一個乘運算一個加運算共3×2=6(次).

P₁₀(x₀)=x·P₉(x₀)+x₁₀,

P₉(x₀)=x·P₈(x₀)+a₉,

……

P₁(x₀)=x·P₀(x₀)+a₁.

其中共有10×2=20(個)運算過程.

答案：65  20