一道谷歌(Google)2011年校园招聘编程题

题目描述：编程实现多项式求值。f(n)=a0 + a1*x^1 + a2*x^2 +…+ an*x^n

函数声明如下：double foo(double* pArray, int len, double x)

乍一看这个题，应该很简单。可以直接入手。代码如下：

double foo(double* pArray, int len, double x)
{
    int i;
    double sum = pArray[0];
    for(i=1; i<=len; i++)
    {
        sum += pArray[i]*pow(x, i);
    }

    return sum;
}

这是最直接的做法，但是，这个算法却要需要（n+1）n/2次乘法和n次加法运算，显然不是最高效的。

其实我们可以将函数f(n)做一下归纳，如下：
f(n)=a0 + a1*x^1 + a2*x^2 +…+ an*x^n
    =a0 + x*(a1 + x*(...(an-2 + x*(an-1 + x*an))...))
这样，就可以得到如下代码：

double foo(double* pArray, int len, double x)
{
    int i;
    double sum = pArray[len];
    for(i=1; i<=len; i++)
    {
        sum = sum*x + pArray[len-i];
    }

    return sum;
}

这样，该算法仅需要n次乘法和n次加法。