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=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共需k次乘法.上式運算中乘法為3+2+1=6次,另外還有3次加法,共9次.由此產生規律:當計算P₁₀(x₀)時有P₁₀(x₀)=a₀x₀¹⁰+a₁x₀⁹+…+a₁₀,計算次數為10+9+8+…+1+10=65次.

    填第二個空需注意:P₃(x₀)=xP₂(x₀)+a₃,P₂(x₀)=xP₁(x₀)+a₂,P₁(x₀)=xP₀(x₀)+a₁,顯然P₀(x₀)為常數不需要計算.∴計算為每次一個乘法運算一個加法運算共3×2=6次.由此運用歸納知:

    P₁₀(x₀)=xP₉(x₀)+a₁₀,P₉(x₀)=xP₈(x₀)+a₉,……,P₁(x₀)=xP₀(x₀)+a₁.

其中運算共有10×2=20次.

答案：65  20