1、案例2 秦九韶算法 1 复习 1、求两个数的最大公数的两种方法分是 _和_ 2.两个数21672，8127的最大公数是 （ ） A. 2709 B. 2606 C. 2703 D. 2706 3.用更相减 求140和80的最大公数是（ ） A. 4 B. 5 C. 10 D. 20 更相减损术辗转相除法 A D 21672=81272+5418 8127=54181+2709 5418=27092+0 2 辗转相除法与更相减损术的比较: （1）都是求最大公约数的方法，计算上辗转 相除法以除法为主，更相减损术以减法为主; 计算次数上辗转相除法计算次数相对较少， 特别当两个数字大小区别较大时计算次
2、数的 区别较明显。 （2）从结果体现形式来看，辗转相除法体现 结果是以相除余数为0则得到，而更相减损术 则以减数与差相等而得到. 3 1：怎求多式f(x)=x5+x4+x3+x2+x+1 当x=5的？并写出程序. 算法1： = 3906 因为f(x)=x5+x4+x3+x2+x+1 所以(5)=555551 =31256251252551 一共做了多少次乘法运算和多少次加法运算？ 上述算法一共做了1+2+3+4=10次乘法运算 ，5次加法运算.优点是简单易懂，但计算 效率不高. 4 算法2： (5)=555551 =5(55551 ) 1 =5(5(555 1 )1 ) 1 =5(5(5(5+
3、5 +1) +1 ) +1 ) +1 =5(5(5(5 (5 +1) +1 )+1)+1) +1 计算多项式f(x)=x5+x4+x3+x2+x+1当x = 5的值 共做了4次乘法运算，5次加法运算。 5 问题2：能否探索一个算法,来解决任意多项式的 求值问题? f(x)=2x5-5x4-4x3+3x2-6x+7 =(2x4-5x3-4x2+3x-6)x+7 =(2x3-5x2-4x+3)x-6)x+7 =(2x2-5x-4)x+3)x-6)x+7 =(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=21
4、5+3=108 v4=v3x-6=1085-6=534 v5=v4x+7=5345+7=2677 所以,当x=5时,多 项式的值是2677. 这种求多项式值的方法就叫秦九韶算法. 当x=5时,多项式 的值是多少？ 6 数书九章秦九韶算法 设是一个n 次的多项式 对该多项式按下面的方式进行改写： 7 要求多项式的值，应该先算最内层的一次多项式的 值，即 然后，由内到外逐层计算一次多项式的值，即 最后的一 项是什么 ？ 这种将求一个n次多项式f(x)的值转化成求n个 一次多项式的值的方法，称为秦九韶算法。8 f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0. 我们可以改写成如下
5、形式: f(x)=(anx+an-1)x+an-2)x+a1)x+a0. 求多项式的值时,首先计算最内层括号内一 次多项式的值,即 v1=anx+an-1, 然后由内向外逐层计算一次多项式的值,即 一般地,对于一个n次多项式 v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0. 这样,求n次多项式f(x)的值就转化为求n个 一次多项式的值.这种算法称为秦九韶算法. 9 特点：通过一次式的反复计算，逐步得出 高次多项式 的值. 注:对于一个n次多项式: 秦九韶算法把运算的次数由最多 1+2+3+n=n(n+1)/2次乘法和 n次加法的运算,减少为最多只需做 n次乘法和
6、n次加法运算,大大提高 了运算效率. 10 例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法一:首先将原多项式改写成如下形式 : f(x)=(2x-5)x-4)x+3)x-6)x+7 v0=2 v1=v0 x-5=25-5=5 v2=v1x-4=55-4=21 v3=v2x+3=215+3=108 v4=v3x-6=1085-6=534 V5=v4x+7=5345+7=2677 所以,当x=5时,多 项式的值是2677. 然后由内向外逐层计算一次多项式的值,即 11 2 -5 -4 3 -6 7 x=5 10 5 25 21 105 108
7、540 534 2670 2677 所以,当x=5时,多项式的值是2677. 原多项式 的系数 多项式 的值. 例1:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值. 解法二:列表 2 v0 v1 v2 v3 v4 v5 12 2 -5 0 -4 3 -6 0 x=510 5 25 25 125 121 605 608 3040 3034 所以,当x=5时,多项式的值是15170. 练一练:用秦九韶算法求多项式 f(x)=2x6-5x5 -4x3+3x2-6x当x=5时的值. 解:原多项式先化为: f(x)=2x6-5x5 +0x4-4x3+3x2-6x
8、+0,列表如下 2 15170 15170 注意:n次多项式有n+1项,因此缺少哪 一项应将其系数补0. 13 v1=anx+an-1, v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0. 观察上述秦九韶算法中的n个一次式,可见 vk的计算要用到vk-1的值. 若令v0=an,得 v0=an, vK=vK-1x+an-k(k=1,2,n 这是一个在秦九韶算法中反复执行的步 骤,因此可用循环结构来实现.因此可用循环结 构来实现。 14 算法步骤： 第一步：输入多项式次数n、最高次项 的系数an和x的值. 第二步：将v的值初始化为an，将i的值 初始化为1. 第三步：
9、输入n-i次项的系数an-i. 第四步：v=vx+an-i , i=i+1. 第五步：判断i是否小于或等于n，若是 ，则返回第三步；否则，输出多项式 的值v。15 否 开始 输入a0,a1,a2,a3,a4,a5 输入x0 n5? n=1 v=a5 v=vx0+a5-n n=n+1 输出v 结束 是 INPUT a0,a1,a2,a3,a4,a5 INPUT x0 n=1 v=a5 WHILE n=5 v=vx0+a5-n n=n+1 WEND PRINT v END 程序 程序框图 16 练习、已知多项式 f(x)=x5+5x4+10 x3+10 x2+5x+1 用秦九韶算法求这个多项式当x=-2时的值 的过程中，求v1和v4 3，1 17 课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的程序框图 18 课本P45页练习T2; P48页A组T2. 19
