引言
秦九韶（1208年-1261年），字道古，中国南宋数学家，其传世佳作 《数书九章》 是中国宋元数学的巅峰之作， 代表了世界中世纪数学发展的最高水平，是继 《九章数学》之后又一部具有创造性成就的数学经典。
以上是秦九韶的个人简介。emmmm....... ， 只能说也是大佬中的大佬，在数学界的创作延续八百年形象至今，秦九韶算法在求多项式的值方面仍然是最强最优秀的，在大数取模也用到了秦九韶思想。
介绍
一般地朴素的讲，一元n次多项式的求值需要经过(n+1)*n/2次乘法和n次加法
而秦九韶算法只需要n次乘法和n次加法。
其核心思想在于将一元n次多项式转换为n个一次式
意义
其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。
在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；
对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少CPU运算时间。
抛出问题
![fleft ( x right ) = a_{3}x^{3}+ a_{2}x^{2}+ a_{1}x^{1}+ a_{0}x^{0}]()
如果是朴素的算法：
需要 3 次乘法 ，
需要 2 次乘法，
需要 1 次乘法 ，共需要 6 次乘法，3 次加法
但若使用秦九韶算法进行简化：
![fleft ( x right ) = a_{3}x^{3}+ a_{2}x^{2}+ a_{1}x+ a_{0}x^{0}]()
![=xtimes left ( a_{3}x^{2} + a_{2} x + a_{1} right ) + a_{0}]()
![=xtimes left ( x left ( a_{3}x + a_{2} right ) + a_{1} right ) + a_{0}]()
共需要 3 次乘法 3 次加法
*问题延申 *
![fleft ( 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{nleft ( n+1 right )}{2}](),加法为
，复杂度为
使用秦九韶算法：将n次多项式的值转化为求n个一次多项式，
只进行
次乘法加法，复杂度为
应用
一、求多项式的值
核心思想：将n次多项式的值转化为求n个一次多项式。
实现方法：确定
的大小，将系数用大小为
的数组存储
对应
。
设结果为
观察上述步骤发现，优先
，后 ![res + a_{n-1}]()
然后反复执行，可以用
循环实现
代码实现：
#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; }
二、大整数取模
提问：如何实现
对
进行取模运算？（**提示：
** 类型能存 9 位数，
能存18位数，
共有
位）
核心思想：秦九韶算法思想：从最高位逐步展开，步步取模。
实现方法：将大整数用字符串存储起来，再用一个
初始化为![s[0]](https://latex.csdn.net/eq?s%5B0%5D) ,先取模
再乘
，循环以往操作，可以迭代实现。
代码实现：
#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; }
总结
将多项式转化为多个一项式，是计算多项式的值最高效的算法。
自用复习以及分享给大家，有任何问题可以留言或私信。
评论加载中…