秦九韶算法

§75秦九韶算法§75秦九韶算法──求多项式的值一、泰勒定理简介二、求多项式值的求法三、秦九韶算法1.直接法2.累乘法3.秦九韶算法1.步骤2.编程复杂函数多项式函数泰勒定理先改后算两大步降幂提因○补缺由内到外逐层算人工递推系数表4.其他法递推公式法人工系数表法三大语言三结构五种语句三案例高考主流是框图循环结构是重点辗转相除法与更相减损术进位制秦九韶算法注4：注1：自然语言框图程序设计语言注2：顺序结构条件结构循环结构输入语句注3：赋值语句输出语句条件语句循环语句───求最大公约数───求多项式的值框图的画法是次要的重点是要能看懂框图2.辗转相除法1.短除法求最大公约数的方法3.更相减损术数字较小短除法公质因数连续除除到所有商互质除数连乘是答案大除小余换大辗转除何时停0或11互质0除数即答案大减小差换大连续减何时停两相等即答案若可半可省功注：辗转相除法与更相减损术的异同点1.辗转相除法以除法运算为主3.两法本质上都是递推，都可用循环结构编程更相减损术以减法运算为主2.辗转相除法当除法运算余数为O或1时终止运算更相减损术当减法运算差为O时终止运算§75秦九韶算法──求多项式的值一、泰勒定理简介二、求多项式值的求法三、秦九韶算法1.直接法2.累乘法3.秦九韶算法1.步骤2.编程复杂函数多项式函数泰勒定理先改后算两大步降幂提因○补缺由内到外逐层算人工递推系数表4.其他法递推公式法人工系数表法常见的多项式（整式）函数我省的大压轴题，每年都是以三次函数来说事2013年的全国Ⅰ卷的小压轴题，是四次函数泰勒中值定理一、泰勒定理简介复杂函数多项式函数泰勒定理②n越大越精确①阶乘的概念：参课本P：32练习2麦克劳林公式一、泰勒定理简介复杂函数多项式函数泰勒定理1.直接法2.累乘法3.秦九韶算法最多n(n+1)/2次乘法，n次加法最多n次乘法，n次加法xn=(xn-1)xxn-1=(xn-2)xxn-2=(xn-3)x…二、求多项式值的求法4.其他法例如当n=10时……引例.求f(x)=x5+x4+x3+x2+x+1当x=5时的值直接法f(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906累乘法f(5)=5５＋5４＋5３＋5２＋5＋１＋5＋１□=＋□＋□＋□251253125625=3906引例.求f(x)=x5+x4+x3+x2+x+1当x=5时的值秦九韶算法f(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１=5×(5×(5×(5×6+１)+１)+１)+１=5×(5×(5×31+１)+１)+１=5×(5×156+１)+１=5×781+１=3906先改后算迭代法降幂提因○补缺由内到外逐层算人工递推系数表后算先改可以看出，该算法是：将求一个5次多项式f(x)的值转化成了求5个一次多项式的值的方法引例.求f(x)=x5+x4+x3+x2+x+1当x=5时的值1.直接法2.累乘法f(5)=5５＋5４＋5３＋5２＋5＋１3.秦九韶算法4.其他法5５，5４，5３，5２，5，１应用等比数列的求和公式最简洁吧秦九韶算法：设是一个n次的多项式先对该多项式按下面的方式进行改写：先改后算两大步降幂提因○补缺由内到外逐层算如何求该多项式的值呢？最后一项Vn是所求值秦九韶算法是将求一个n次多项式f(x)的值转化成了，求n个一次多项式的值的方法。

用秦九韶算法计算多项式的值c语言多项式是数学中的一个重要概念，它在各个领域都有广泛的应用。

在计算机科学中，多项式的计算也是一个常见的问题。

本文将介绍一种高效的算法——秦九韶算法，用它来计算多项式的值。

一、秦九韶算法的原理秦九韶算法是一种快速计算多项式值的算法。

它的基本思想是将多项式的系数和变量分离，然后通过递推的方式计算多项式的值。

具体来说，假设多项式为：f(x) = a0 + a1x + a2x^2 + ... + anx^n我们可以将其表示为：f(x) = a0 + x(a1 + x(a2 + ... + x(an-1 + anx)...))这样，我们就可以通过递推的方式计算多项式的值。

具体来说，我们可以从最高次项开始，依次计算每一项的值，然后将其累加起来。

这样，我们就可以在O(n)的时间复杂度内计算多项式的值。

二、用c语言实现秦九韶算法下面，我们将用c语言来实现秦九韶算法。

具体来说，我们可以定义一个数组来存储多项式的系数，然后通过循环来计算多项式的值。

代码如下：```c#include <stdio.h>double qinjiushao(double a[], int n, double x) {double result = a[n];for (int i = n - 1; i >= 0; i--) {result = result * x + a[i];}return result;}int main() {double a[] = {1, 2, 3, 4, 5};int n = 4;double x = 2;double result = qinjiushao(a, n, x);printf("f(%lf) = %lf\n", x, result);return 0;}```在这个例子中，我们定义了一个数组a来存储多项式的系数，n表示多项式的最高次数，x表示要计算的多项式的值。

编程用秦九韶算法计算多项式的值秦九韶算法（又称秦九韶快速幂算法）是一种用于计算多项式的值的高效算法。

该算法的思想是将多项式的计算过程进行优化，减少重复的计算。

多项式可以表示为：P(x) = a0 + a1*x + a2*x^2 + ... + an*x^n 普通的计算方法是按照上述公式逐项计算每一项相乘再相加的结果。

然而，这种方法在项数较多时，计算量会急剧增加，效率低下。

秦九韶算法通过一系列的优化，可以极大地提高计算效率。

秦九韶算法的核心思想是通过重复平方的方式，快速地计算多项式的值。

具体过程如下：Step 1: 将多项式的系数存储在一个数组中。

例如，多项式P(x) = 2 + 3x + 4x^2可以表示为：coefficients = [2, 3, 4]Step 2: 设定一个初始值result为0Step 3: 从n=0开始，遍历coefficients数组，对每个系数进行以下操作：- 将result乘以x的n次幂。

初始情况下，x的幂为1，乘以coefficients[0]得到r0 = coefficients[0]。

之后，将x平方，得到x^2，依次类推。

- 将上述结果与result相加，得到新的result。

例如，r0 + coefficients[1]*x + coefficients[2]*x^2 + ... +coefficients[n]*x^n = resultStep 4: 返回result作为多项式P(x)的值。

以以上示例的多项式P(x)=2+3x+4x^2为例，假设x=2，那么应用秦九韶算法的计算过程如下：Step 1: coefficients = [2, 3, 4]Step 2: result = 0Step 3: 遍历coefficients数组-第一次迭代：- result = result * x + coefficients[0] = 0 * 2 + 2 = 2-第二次迭代：- result = result * x + coefficients[1] = 2 * 2 + 3 = 7-第三次迭代：- result = result * x + coefficients[2] = 7 * 2 + 4 = 18Step 4: 返回result = 18，即多项式P(x) = 2 + 3x + 4x^2在x=2时的值为18通过秦九韶算法，我们可以在O(n)的时间复杂度内计算多项式的值，极大地提高计算效率。

实验1 秦九韶算法（贺俊杰 2020022060）一、实验目的人类的计算能力等于计算工具的效率与计算方法的效率的乘积，高效率计算方法大大减少了计算次数，从而也能较少舍入误差的传播和积累，构造高效率计算方法一直是科学计算的一个主要目的。

本次实验以完成秦九韶算法为契机，深入了解高效计算多项式结果的数值计算方法，同时加深对Matlab 环境的熟悉。

二、算法分析对于n 次多项式：1110()n n n n n P x a x a x a x a −−=+++ (1)可改写为嵌套形式：1210()((()))n n n n p x a x a x a x a x a −−=++++ (2)在(1)式中，n i n i a x −−需要计算n i −次乘法运算(其中0,1,1i n =−)和n 次加法运算，共需要进行(1)2n n+次乘法运算和n 次加法运算。

而在(2)式中，仅需要经过n 次乘法运算和n 次加法运算，能够极大地减少运算次数，提高运算效率。

根据程序设计地习惯，把公式(2)写成下来等价的地推形式：(1,2,)n n k y a y y x a k n −⇐⎧⎨⇐⋅+=⎩ (3)三、算法代码实现秦九韶算法Matlab 实现如下：Qinjiu.m 文件其中a 为多项式系数从高次向低次排列数组(缺项系数为0)，n 为多项式多高次数，x 为变量。

四、实验结果1、 设543()851f x x x x =++−，计算()f x 在1,1.5,2.1,3x =上的值。

编写run_qinjiu.m 代码文件如下所示：run_qinjiu.m 文件取多项式系数a = [8, 5, 1, 0, 0, -1]，运行结果如下图所示：图1 run_qinjiu.m 运行结果由图可知算法能正确运行。

2、 利用Matlab 库中的horner 命令，可直接把多项式变为如(2)式的嵌套形式。

编写run_horner.m 代码文件如下所示：程序运行结果如下图所示：从图中可看出，horner库函数可正确地将多项式转为嵌套形式。