浅谈秦九韶算法

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

秦九韶算法的应用

求下式在(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+1quad (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];
}