霍纳法则

来自计算思维百科
跳转至: 导航搜索
霍纳法则1.png

霍纳法则是一个古老的计算多项式的算法,但却十分优雅和高效。

基本概念

计算机科学中,有一些关于多项式求值的问题。对于多项式求值问题,我们最容易想到的算法是求出每一项的值然后把所求的值累加起来,这种算法的时间和空间效率都不高,对于数据规模不大的题目来说由于其直观、简单很容易被大家采纳,可一旦数据规模过大时,这种算法就显得无能为力了,而霍纳法则可以高效地计算多项式的值。霍纳法则是以英国数学家W.G.Horner的名字命名的,在中国,也被称为秦九韶算法。霍纳在19世纪就发表了这个算法。

例如:当x=3时,计算p(x)=2x4 - x3+ 3x2 + x - 5

霍纳法则计算过程可以用如下表来表示,第一行为该多项式每项系数值,第二行除了第一个单元用来存储第一个系数值,其他单元都用来存储计算的中间结果,最后一个单元为最终结果。

霍纳法则2.png

我们知道p(x)= 2x4 - x3+3 x2 + x – 5

       = x(2x3 – x2+3 x + 1) – 5

       = x(x(2x2 – x+3 ) + 1) – 5

       = x(x(x(2x – 1)+3 ) + 1) – 5

根据表格容易看出,3*2-1=5是2x-1在x=3时的值,3*5+3=18是x(2x – 1)+3在x=3时的值,3*18+1=55是x(x(2x – 1)+3 ) + 1 在x=3时的值,最后,3*55-5=160是 p(x)=x(x(x(2x – 1)+3 ) + 1) – 5在x=3时的值。

霍纳法则还有一些副产品。对于上述例子来说,p(x)=2x4 - x3+3 x2 + x – 5除以x-3的商和余数分别为2x3 +5 x2+18 x + 55和160。这种被称为综合除法的除法算法要比“长除法”更方便,但是它只能用于除数是x-c的除法中,c为常数。

应用范围

霍纳法则多运用在多项式求值运算中,充分体现算法的高效性和优雅性。

使用方法及步骤

步骤一:找出多项式每项系数;

步骤二:对每项系数,计算出 x*前一个单元格的值+当前系数  的值;

步骤三:最后一个单元格计算得到的值就是对应多项式的值。

应用案例

应用1-计算公司盈利

案例:有一个公司,自2011年以来每年的盈利(万元)可以用下面的多项式表达,其中2011年时x=1,2012年时x=2,以此类推,请确定该公司2015年的盈利。对这个问题就是要求解当x=5时,p(x)=x4 - x3+3 x2 -x 的值。

解决方式:

步骤一:找出每项系数为

系数

1

-1

3

-1

0

 

 

 

 

 

 

步骤二:对每项系数,计算出 x*前一个单元格的值+当前系数 的值;

系数

1

-1

3

-1

0

X=5

1

5*1-1=4

5*4+3=23

5*23-1=108

5*108+0=540

步骤三:当x=5时, p(x)=x4 - x3+3 x2 -4 x =540

可以体现的计算思维

求解多项式的值中,把需要多次进行的乘法运算转化成加法运算。“转化”体现的就是由难化易,由繁化简。在实际生活中,遇到的问题肯定会更加复杂,我们要学会“转化”,将问题简单化。霍纳法则体现计算思维中的“转化”特点。