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_n(x₀)的值共需要________________次运算.

下面给出一种减少运算次数的算法:P₀(x)=a₀,P_k+1(x)=xP_k(x)+a_k+1(k=0,1,2,…,n-1).利用该算法,计算P₃(x₀)的值共需要6次运算,计算P_n(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次,

    另外还有3次加法,共9次.

    由此产生规律:

    当计算P_n(x₀)时有

    P_n(x₀)=a₀x₀ⁿ+a₁x₀^n-1+…+a_n.

    计算次数为+n=+n=n(n+3)次.

    第2个空中需注意

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

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

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

    显然P₀(x₀)为常数不需计算.

    ∴计算为每次一个乘运算、一个加运算共3×2=6次.

    由此运用不完全归纳法知

    P_n(x₀)=x·P_n-1(x₀)+a_n,

    P_n-1(x₀)=x·P_n-2(x₀)+a_n-1,

    …,

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

    其中共有n×2=2n个运算过程.

    答案:n(n+3)  2n