秦九韶算法

概述秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法（Horner algorithm或Horner scheme），是以英国数学家威廉·乔治·霍纳命名的.

把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：

f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]

=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]

=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]

=......

=(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].

求多项式的值时，首先计算最内层括号内一次多项式的值，即

v[1]=a[n]x+a[n-1]

然后由内向外逐层计算一次多项式的值，即

v[2]=v[1]x+a[n-2]

v[3]=v[2]x+a[n-3]

......

v[n]=v[n-1]x+a[0]

这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。

（注：中括号里的数表示下标）

结论：对于一个n次多项式，至多做n次乘法和n次加法。

意义该算法看似简单，其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，对于计算机来说，做一次乘法运算所用的时间比作一次加法运算要长得多，所以此算法极大地缩短了CPU运算时间。

（附：计算机程序）

INPUT “n=”；n

INPUT “an=”；a

INPUT “x=”；x

v=a

i=n-1

WHILE i＞=0

PRINT “i=”；i

INPUT “ai=”；a

v=v*x+a

i=i-1

WEND

PRINT v

END

PASCAL算法实现

v[1]:=a[n]*k+a[n-1]；

for i:=2 to n do

v[i]:=v[i-1]*k+a[n-i]；

writeln(v[n])；