浅谈秦九韶算法

本篇随笔简单讲解一下高中数学必修三信息学奥林匹克竞赛中的秦九韶算法。

秦九韶算法的应用

求下式在\(x\)为定值时的值：
\[ f(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n \]
一开始面对这个东西，我们最早想到的可能是暴力算法：直接带进去乘法求值。

那还要秦九韶发明这个算法干什么

那么就隆重介绍秦九韶算法。

简单来讲就是提公因式。

原式可以变形成为：
\[ f(x)=a_0+x(a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1}) \]

继续提：
\[ f(x)=a_0+x(a_1+x(a_2+a_3x+\cdots+a_nx^{n-2})) \]
以此类推...

最后提完之后就成为了这样的式子：
\[ f(x)=(\cdots(a_nx+a_{n-1})x+a_{n-2})x+\cdots+a_1)x+a_0 \]
乍一看很复杂，其实很简单（能入选高中课本的算法怎么可能难）

那么它比暴力算法优秀在哪呢？

想一下，以一个这样的式子为例：

计算下式的值：
\[ f(x)=x^5+x^4+x^3+x^2+x+1\quad (x=5) \]
暴力算法就可以一个一个进行乘法和加法。

那么：

我们可以发现，进行了10次乘法（暴力计算\(x^n\)需要\(n-1\)次乘法运算），和5次加法。

而秦九韶算法并没有改变加法的运算量（因为加号是无论如何消除不掉的），但是乘法呢？我们仔细观察一下就可以发现，最后提出来了4个5，也就是说仅仅需要进行4次的乘法运算。这种效率显然是更优的，而且最高此项的次数越大，效率优化越高。

秦九韶算法的代码实现：

秦九韶算法的实现只是一个模拟算法的过程。假设\(a[i]\)数组输入了从多项式在次数为\(i\)那项的系数，那么秦九韶算法的核心代码块就是：

void qinjiushao()
{
    for(int i=n-1;i>=1;i--)
        ans*=x,ans+=a[i];
}