问题及解答

考虑下述算法(称为 Horner 法则)， 用于计算 $f(x)=\sum\limits_{i=0}^{n}a_i x^i$ 的值.

poly = 0;
for( i=n; i>=0; i--)
	poly = x * poly + a[i];

a) 对于多项式 $f(x)=4x^4+8x^3+x+2$, 求 $x=3$. 指出该算法的各步是如何进行的.

b) 解释该算法为什么能够解决这个问题.

c) 该算法的运行时间是多少?

请编写程序并完成上面的问题.

References:

Mark Allen Weiss 著, 张怀勇等译, 《数据结构与算法分析 C++ 描述》, 人民邮电出版社, 2012. 6. 【Exer 2.14】

#include <iostream>
#include <vector>

using namespace std;

double f(double x,const vector & a)
{
    double poly=0;

    //注意下面的条件 i>0 不要改成 i>=0, 会导致无限循环的, 可能是 unsigned int 的问题.
    for(unsigned int i=a.size()-1; i > 0; i--)
    {
        poly=x*poly+a[i];
    }
    poly=x*poly+a[0];
    return poly;
}

int main()
{
    cout << \"计算多项式的值\" << endl;
    double b[]={2,1,0,8,4}; //4x^4+8x^3+0x^2+x+2
    vector<double> a(b,b+5);
    cout << \"多项式f(x)是\" << endl;

    for(unsigned int i=0; i<a.size()-1; i++)
    {
        cout << a[i] << \"x^\" << a.size()-i << \" + \";
    }
    cout << a.back() << endl;
    cout << \"该多项式当 x= 3 时的值为: \" << endl;

    cout << \"f(3,a)=\" << f(3.0,a) << endl;
    return 0;
}