霍纳法则(Horner Rule)

霍纳法则(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,这种求值的安排我们称为霍纳法则。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Author: Tanky Woo
// blog: www.WuTianQi.com
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《霍纳法则(Horner Rule)》有7个想法

  1. 貌似博主也关注python。Horner Rule 用python的reduce函数来写,从代码的可读性上看,更突出Rule中的关键点。
    [code]
    p=lambda x:lambda a1,a0:a1*x+a0
    reduce(p(10),[1,2,3,4]) #x^3+2x^2+3x^3+4 ,x=10
    [/code]

发表评论

电子邮件地址不会被公开。 必填项已用*标注