Tanky WooRSS

霍纳法则(Horner Rule)

09 Nov 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

霍纳法则(Horner Rule),是一个比较常用的法则,但是网上关于这个的相关资料不是很多,我主要找到了两个。 1.http://blog.csdn.net/lwj1396/archive/2008/07/18/2669993.aspx

2.http://flynoi.blog.hexun.com/31272178_d.html 在第二篇文章里讲到了霍纳法则出现的原因:为多项式求值提供了一个高效的方法。 “对于多项式求值问题,我们最容易想到的算法是求出每一项的值然后把所求的值累加起来,这种算法的时间和空间效率都不高,对于数据规模不大的题目来说由于其直观、简单很容易被大家采纳,可一旦数据规模过大时,这种算法就显得无能为力了”

这个算是比较详细的霍纳法则概念了: 假设有n+2个实数a0,a1,…,an,和x的序列,要对多项式Pn(x)= anxn +an-1xn-1+…+a1x+a0求值,直接方法是对每一项分别求值,并把每一项求的值累加起来,这种方法十分低效,它需要进行n+(n-1)+…+1=n(n+1)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法,即Pn(x)= anxn +an-1xn-1+…+a1x+a0=((…(((anx +an-1)x+an-2)x+ an-3)…)x+a1)x+a0,这种求值的安排我们称为霍纳法则。

在这里我写了一个霍纳法则的小程序:

// Author: Tanky Woo
// blog: www.WuTianQi.com
#include 
using namespace std;

// Calculate the value of an*x^n + an-1*x^(n-1) + ... a2*x^2 + a1*x + a0
double HornerRule(double a[], int n, double x);

int main()
{
    double *a;
    int n;
    double x;

    cout << "Input the n (a0, a1, a2...an): ";
    cin >> n;

    a = new double[n+1];
    cout << "Input the a0, a1, a2, ..., an (n+1 numbers): ";
    for(int i=0; i<=n; ++i)
        cin >> a[i];

    cout << "Input the x: ";
    cin >> x;

    for(int i=n; i>=0; --i)
    {
        if(i != n)
            cout << " + ";
        cout << a[i] << "*x^" << i;
    }
    cout << " = " << HornerRule(a, n, x) << endl;

    return 0;
}


double HornerRule(double a[], int n, double x)
{
    double res = 0.0;

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

    return res;
}