引言

秦九韶（1208年-1261年），字道古，中国南宋数学家，其传世佳作 《数书九章》 是中国宋元数学的巅峰之作， 代表了世界中世纪数学发展的最高水平，是继 《九章数学》之后又一部具有创造性成就的数学经典。

以上是秦九韶的个人简介。emmmm……. ， 只能说也是大佬中的大佬，在数学界的创作延续八百年形象至今，秦九韶算法在求多项式的值方面仍然是最强最优秀的，在大数取模也用到了秦九韶思想。

介绍

一般地朴素的讲，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法

而秦九韶算法只需要n次乘法和n次加法。

其核心思想在于将一元n次多项式转换为n个一次式

意义

其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。

在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；

对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少CPU运算时间。

抛出问题

f\left ( x \right ) = a_{3}x^{3}+ a_{2}x^{2}+ a_{1}x^{1}+ a_{0}x^{0}

如果是朴素的算法：x\times x\times x \times a_{3} 需要 3 次乘法 ， x\times x \times a_{2} 需要 2 次乘法，

x \times a_{1} 需要 1 次乘法 ，共需要 6 次乘法，3 次加法

但若使用秦九韶算法进行简化：

f\left ( x \right ) = a_{3}x^{3}+ a_{2}x^{2}+ a_{1}x+ a_{0}x^{0}

=x\times \left ( a_{3}x^{2} + a_{2} x + a_{1} \right ) + a_{0}

=x\times \left ( x \left ( a_{3}x + a_{2} \right ) + a_{1} \right ) + a_{0}

共需要 3 次乘法 3 次加法

***问题延申 ***

f\left ( x \right ) = a_ {n}x^ {n}+ a_ {n-1}x^ {n-1}+ a_ {n-2}x^ {n-2}+ ... a_ {1}x + a_ {0}

使用朴素算法：后一项比前一项的指数小 1 ，少算 1 次乘法，成等差数列，

故共进行的乘法数为 \frac{n\left ( n+1 \right )}{2},加法为 n，复杂度为O\left ( n^{2} \right )

使用秦九韶算法：将n次多项式的值转化为求n个一次多项式，

只进行 n 次乘法加法，复杂度为O\left ( n \right )

应用

一、求多项式的值

核心思想：将n次多项式的值转化为求n个一次多项式。

实现方法：确定 n 的大小，将系数用大小为 n 的数组存储 0\sim n 对应a_{0}\sim a_{n}。

设结果为 res 观察上述步骤发现，优先 res = a_{n} \times x ，后 res + a_{n-1}

然后反复执行，可以用 for 循环实现

代码实现：

1
2
3
4
5
6
7
8
9
10
#define int long long
int qFun(int factors[],int n, int x){//分别表示系数数组，最大项的系数，未知数x赋的值
    int res = factors[n];
    for(int i = n;i >=1 ;-- i)
    {
        res = res * x;
        res = res + factors[i-1];
    }
    return res;
}
二、大整数取模

提问：如何实现10^{10^{5}} 对101 进行取模运算？（提示：int类型能存 9 位数，long long 能存18位数，10^{10^{5}} 共有 10^{5} 位）

核心思想：秦九韶算法思想：从最高位逐步展开，步步取模。

实现方法：将大整数用字符串存储起来，再用一个int初始化为s[0] ,先取模p 再乘10，循环以往操作，可以迭代实现。

代码实现：

1
2
3
4
5
6
7
8
9
10
#define int long long
int qmod(string s,int p)
{
    int ans = 0;
    for(auto &i : s)
    {
        ans = (ans * 10 + i - '0') % p;
    }
    return ans;
}

总结

将多项式转化为多个一项式，是计算多项式的值最高效的算法。

自用复习以及分享给大家，有任何问题可以留言或私信。