秦九韶算法公式详解

- 1 - 

秦九韶算法公式详解

秦九韶算法是一种多项式求值的高效算法，

可以大大提高多项式

求值的速度。本文将详细介绍秦九韶算法的原理、流程和应用。

一、算法原理

秦九韶算法是一种递推算法，

其基本思想是将多项式分解为一个

个单项式，然后通过递推的方式依次求值。具体来说，对于一个

n

次

多项式

f(x)

，我们可以将其表示为：

    $f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_{0}$ 

然后，我们可以先计算出

a_n

和

a_{n-1}

的值，然后利用递推公

式：

    $b_{i}=a_{i}+xtimes b_{i+1}$ 

求出

$b_{n-1}$

，再利用递推公式：

    $c_{i}=b_{i}+xtimes c_{i+1}$ 

求出

$c_{n-2}$

，以此类推，直到求出

$c_{1}$

，最后再加上

$a_{0}$

即可得到多项式的值。

二、算法流程

    1.

输入多项式的系数和

x

的值；

    2.

初始化

b_{n-1}=a_{n}

和

c_{n-2}=a_{n}x+a_{n-1}

；

    3.

从

n-2

到

0

依次计算

$b_{i}$

和

$c_{i}$

，直到

$i=0$

为止；

    4.

输出

$c_{0}$

，即为多项式在

x

处的值。

三、算法应用

秦九韶算法可以用于多项式求值、多项式插值、多项式拟合、多