1.3算法案例 整体设计 教学分析 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序三种不同 方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决 问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表 达能力 三维目标 1.理解算法案例的算法步骤和程序框图 2.引导学生得出自己设计的算法程序. 3.体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力 重点难点 教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序. 教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 课时安排 3课时 教学过程 第1课时案例1辗转相除法与更相减损术 导入新课 思路1(情境导入) 大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球, 东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的.在小学, 我们学过求两个正整数的最大公约数的方法:先用两个数公有的质因数连续去除,一直除到 所得的商是互质数为止,然后把所有的除数连乘起来.当两个数公有的质因数较大时(如8 251与6105),使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法 辗转相除法与更相减损术,由此可以体会东、西方文化的差异. 思路2(直接导入) 前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减 损术来进一步体会算法的思想 推进新课 新知探究 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大公约数? (3)怎样用辗转相除法求最大公约数? (4)怎样用更相减损术求最大公约数? 讨论结果 (1)短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得 的商是两个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举, 直到找到公约数立即中断列举,得到的公约数便是最大公约数
1 1.3 算法案例 整体设计 教学分析 在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同 方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决 问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表 达能力. 三维目标 1．理解算法案例的算法步骤和程序框图. 2．引导学生得出自己设计的算法程序. 3. 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 重点难点 教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序. 教学难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 课时安排 3 课时 教学过程 第 1 课时 案例 1 辗转相除法与更相减损术 导入新课 思路 1（情境导入） 大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球， 东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学， 我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到 所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时（如 8 251 与 6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法—— 辗转相除法与更相减损术,由此可以体会东、西方文化的差异. 思路 2（直接导入） 前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减 损术来进一步体会算法的思想. 推进新课 新知探究 提出问题 （1）怎样用短除法求最大公约数？ （2）怎样用穷举法（也叫枚举法）求最大公约数？ （3）怎样用辗转相除法求最大公约数？ （4）怎样用更相减损术求最大公约数？ 讨论结果： （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得 的商是两个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举， 直到找到公约数立即中断列举，得到的公约数便是最大公约数
(3)辗转相除法 辗转相除法求两个数的最大公约数,其算法步骤可以描述如下 第一步,给定两个正整数m,n 第二步,求余数r:计算m除以n,将所得余数存放到变量r中 第三步,更新被除数和余数:m=n,n=r 第四步,判断余数r是否为0.若余数为0,则输出结果:否则转向第二步继续循环执行 如此循环,直到得到结果为止.这种算法是由欧几里得在公元前300年左右首先提出 的,因而又叫欧几里得算法 (4)更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古 代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之, 不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代 语言如下: 第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简:若不是,执 行第二步 第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数 继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是 所求的最大公约数 应用示例 例1用辗转相除法求8251与6105的最大公约数,写出算法分析,画出程序框图,写出 算法程序 解:用两数中较大的数除以较小的数,求得商和余数:8251=6105×1+2146. 由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105 的公约数也是6105与2146的公约数,所以它们的最大公约数相等 对6105与2146重复上述步骤:6105=2146×2+1813 同理,2146与1813的最大公约数也是6105与2146的最大公约数.继续重复上述步骤 2146=1813×1+333 1813=333×5+148, 333=148×2+37, 最后的除数37是148和37的最大公约数,也就是8251与6105的最大公约数. 这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可 以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数 算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结 构来构造算法 算法步骤如下: 第一步,给定两个正整数m,n 第二步,计算m除以n所得的余数为r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步 程序框图如下图
2 （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 m，n. 第二步，求余数 r：计算 m 除以 n，将所得余数存放到变量 r 中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数 r 是否为 0.若余数为 0，则输出结果；否则转向第二步继续循环执行. 如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出 的，因而又叫欧几里得算法. （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古 代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之， 不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代 语言如下： 第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用 2 约简；若不是，执 行第二步. 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数， 继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是 所求的最大公约数. 应用示例 例 1 用辗转相除法求 8 251 与 6 105 的最大公约数,写出算法分析，画出程序框图，写出 算法程序. 解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146. 由此可得，6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数，反过来，8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数，所以它们的最大公约数相等. 对 6 105 与 2 146 重复上述步骤：6 105=2 146×2+1 813. 同理，2 146 与 1 813 的最大公约数也是 6 105 与 2 146 的最大公约数.继续重复上述步骤： 2 146=1 813×1+333， 1 813=333×5+148， 333=148×2+37， 148=37×4. 最后的除数 37 是 148 和 37 的最大公约数，也就是 8 251 与 6 105 的最大公约数. 这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可 以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数. 算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结 构来构造算法. 算法步骤如下： 第一步，给定两个正整数 m，n. 第二步，计算 m 除以 n 所得的余数为 r. 第三步，m=n，n=r. 第四步，若 r=0，则 m，n 的最大公约数等于 m；否则，返回第二步. 程序框图如下图：
开始 输人mn/ 求m除以n的余数 结束 程序: INPUT m n r=m mod n LOOP UNTIL r=o PRINT m 点评:从教学实践看,有些学生不能理解算法中的转化过程,例如:求8251与6105的最 大公约数,为什么可以转化为求6105与2146的公约数.因为8251=6105×1+2146, 可以化为8251-6105×1=2164,所以公约数能够整除等式两边的数,即6105与2146 的公约数也是8251与6105的公约数 变式训练 你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程 序 解:当型循环结构的程序框图如下图: 开始 ∠输入mn 求m除以的余数 输出m 结束
3 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求 8 251 与 6 105 的最 大公约数,为什么可以转化为求 6 105 与 2 146 的公约数.因为 8 251=6 105×1+2 146， 可以化为 8 251-6 105×1=2 164，所以公约数能够整除等式两边的数，即 6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数. 变式训练 你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程 序. 解：当型循环结构的程序框图如下图：
程序: NPUT WHILE r>o r=m mod n MEn WEND PRINT m END 例2用更相减损术求98与63的最大公约数. 解:由于63不是偶数,把98和63以大数减小数,并辗转相减,如下图所示 63-35=2 35-28=7 28-7=21 21-7=14 所以,98和63的最大公约数等于7 点评:更相减损术与辗转相除法的比较:尽管两种算法分别来源于东、西方古代数学名著, 但是二者的算理却是相似的,有异曲同工之妙.主要区别在于辗转相除法进行的是除法运算, 即辗转相除:而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归 过程 变式训练 用辗转相除法或者更相减损术求三个数324,243,135的最大公约数 解:324=243×1+81, 243=81×3+0 则324与243的最大公约数为81. 又135=81×1+54,81=54×1+27 54=27×2+0, 则81与135的最大公约数为27. 所以,三个数324、243、135的最大公约数为27 另法:324-243=81,243-81=162,162-81=81,则324与243的最大公约数为81 35-81=54,81-54=27,54-27=27,则81与135的最大公约数为27 所以,三个数324、243.135的最大公约数为27 例3(1)用辗转相除法求123和48的最大公约数 (2)用更相减损术求80和36的最大公约数 解:(1)辗转相除法求最大公约数的过程如下 123=2×48+27, 48=1×27+21, 27=1×21+6, 21=3×6+3
4 程序： INPUT m，n r=1 WHILE r＞0 r=m MOD n m=n n=r WEND PRINT m END 例 2 用更相减损术求 98 与 63 的最大公约数. 解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减，如下图所示. 98-63=3 5 63-35=2 8 35-28=7 28-7=21 21-7=14 14-7=7 所以，98 和 63 的最大公约数等于 7. 点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名著， 但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法运算， 即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归 过程． 变式训练 用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数. 解：324=243×1＋81， 243=81×3＋0， 则 324 与 243 的最大公约数为 81. 又 135=81×1＋54，81=54×1＋27， 54=27×2＋0， 则 81 与 135 的最大公约数为 27. 所以,三个数 324、243、135 的最大公约数为 27. 另法：324－243=81,243－81=162,162－81=81，则 324 与 243 的最大公约数为 81. 135－81=54,81－54=27,54－27=27，则 81 与 135 的最大公约数为 27. 所以，三个数 324、243.135 的最大公约数为 27. 例 3 （1）用辗转相除法求 123 和 48 的最大公约数. （2）用更相减损术求 80 和 36 的最大公约数. 解：（1）辗转相除法求最大公约数的过程如下： 123＝2×48＋27， 48＝1×27＋21， 27＝1×21＋6， 21＝3×6＋3
6=2×3+0, 最后6能被3整除,得123和48的最大公约数为3. (2)我们将80作为大数,36作为小数,因为80和36都是偶数,要除公因数2 80÷2=40,36÷2 40和18都是偶数,要除公因数2 下面来求20与9的最大公约数 20—9=11, 9-2=7 7-2=5 3-2=1, 可得80和36的最大公约数为22×1=4. 点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为0,更相减损术是到达减 数和差相等 变式训练 分别用辗转相除法和更相减损术求1734,816的最大公约数 解:辗转相除法 1734=816×2+102,816=102×8(余0) ∴1734与816的最大公约数是102 更相减损术:因为两数皆为偶数,首先除以2得到867,408,再求867与408的最大公约 867-408=459, 459-408=51, 408-51=357 357-51=306, 306-51=255, 204-51=153, 153-51=102, 102-51=51. ∴1734与816的最大公约数是51×2=102 利用更相减损术可另解: 1734-816=918, 918-816=102, 816-102=714, 714-102=612 612-102=510, 510-102=408 408-102=306, 306-102=204 204-102=102
5 6＝2×3+0， 最后 6 能被 3 整除，得 123 和 48 的最大公约数为 3. （2）我们将 80 作为大数，36 作为小数，因为 80 和 36 都是偶数，要除公因数 2. 80÷2=40，36÷2=18. 40 和 18 都是偶数，要除公因数 2. 40÷2=20，18÷2=9. 下面来求 20 与 9 的最大公约数， 20－9=11， 11－9=2， 9－2=7， 7－2=5， 5－2=3， 3－2=1， 2－1=1， 可得 80 和 36 的最大公约数为 2 2×1=4. 点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为 0，更相减损术是到达减 数和差相等. 变式训练 分别用辗转相除法和更相减损术求 1 734，816 的最大公约数． 解：辗转相除法： 1 734=816×2+102，816=102×8（余 0）， ∴1 734 与 816 的最大公约数是 102． 更相减损术：因为两数皆为偶数，首先除以 2 得到 867，408，再求 867 与 408 的最大公约 数． 867-408=459， 459-408=51， 408-51=357， 357-51=306， 306-51=255， 255-51=204， 204-51=153， 153-51=102， 102-51=51. ∴1 734 与 816 的最大公约数是 51×2=102． 利用更相减损术可另解： 1 734－816＝918， 918－816＝102， 816－102＝714， 714－102＝612， 612－102＝510， 510－102＝408， 408－102＝306， 306－102＝204， 204－102＝102
∴1734与816的最大公约数是102 知能训练 求319,377,116的最大公约数 解:377=319×1+58, 319=58×5+29 58=29×2. ∴377与319的最大公约数为29,再求29与116的最大公约数 116=29×4 ∴29与116的最大公约数为29. ∴377,319,116的最大公约数为29 拓展提升 试写出利用更相减损术求两个正整数的最大公约数的程序 解:更相减损术程序: WHILE mon IF m>n Then ELSE ME-n-m END IF PRINT m 课堂小结 (1)用辗转相除法求最大公约数. (2)用更相减损术求最大公约数 思想方法:递归思想. 作业 分别用辗转相除法和更相减损术求261,319的最大公约数. 分析:本题主要考查辗转相除法和更相减损术及其应用.使用辗转相除法可依据mnq+r 反复执行,直到r=0为止;用更相减损术就是根据mn=r,反复执行,直到n=r为止 解:辗转相除法 319=261×1+58, 261=58×4+29, 58=29×2. ∴319与261的最大公约数是29 更相减损术 203-58=145 145-58=8 58-29=29, 319与261的最大公约数是29 6
6 ∴1 734 与 816 的最大公约数是 102． 知能训练 求 319，377，116 的最大公约数． 解：377=319×1+58， 319=58×5+29， 58=29×2. ∴377 与 319 的最大公约数为 29，再求 29 与 116 的最大公约数． 116=29×4. ∴29 与 116 的最大公约数为 29. ∴377，319，116 的最大公约数为 29. 拓展提升 试写出利用更相减损术求两个正整数的最大公约数的程序． 解：更相减损术程序： INPUT “m，n=”；m，n WHILE m<>n IF m>n THEN ｍ＝m-n ELSE m=n-m END IF WEND PRINT m END 课堂小结 （1）用辗转相除法求最大公约数. （2）用更相减损术求最大公约数. 思想方法：递归思想. 作业 分别用辗转相除法和更相减损术求 261，319 的最大公约数. 分析：本题主要考查辗转相除法和更相减损术及其应用．使用辗转相除法可依据 m=nq+r， 反复执行，直到 r=0 为止；用更相减损术就是根据 m-n=r，反复执行，直到 n=r 为止． 解：辗转相除法： 319=261×1+58, 261=58×4+29, 58=29×2. ∴319 与 261 的最大公约数是 29． 更相减损术： 319-261=58, 261-58=203, 203-58=145, 145-58=87, 87-58=29, 58-29=29, ∴319 与 261 的最大公约数是 29．
设计感想 数学不仅是一门科学,也是一种文化,本节的引入从东、西方文化的不同开始,逐步向 学生渗透数学文化.从知识方面主要学习用两种方法求两个正整数的最大公约数,从思想方 法方面,主要学习递归思想.本节设置精彩例题,不仅让学生学到知识,而且让学生进一步 体会算法的思想,培养学生的爱国主义情操 第2课时案例2秦九韶算法 导入新课 思路1(情境导入) 大家都喜欢吃苹果吧,我们吃苹果都是从外到里一口一口的吃,而虫子却是先钻到苹果 里面从里到外一口一口的吃,由此看来处理同一个问题的方法多种多样.怎样求多项式 f(x)=x3+x+x3+x2+x+1当x=5时的值呢?方法也是多种多样的,今天我们开始学习秦九韶算 思路2(直接导入) 前面我们学习了辗转相除法与更相减损术,今天我们开始学习秦九韶算法 推进新课 新知探究 提出问题 (1)求多项式f(x)=x5+x+x2+x2+x+1当x=5时的值有哪些方法?比较它们的特点 (2)什么是秦九韶算法? (3)怎样评价一个算法的好坏? 讨论结果: (1)怎样求多项式f(x)=x°+x+x3+x2+x+1当x=5时的值呢? 一个自然的做法就是把5代入多项式f(x),计算各项的值,然后把它们加起来,这时 我们一共做了1+2+3+4=10次乘法运算,5次加法运算 另一种做法是先计算x2的值,然后依次计算x2·x,(x2·x)·x,((x2·x)·x)·x 的值,这样每次都可以利用上一次计算的结果,这时,我们一共做了4次乘法运算,5次加 法运算 第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于 计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法 计算机能更快地得到结果. (2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约12021261)在 他的著作《数书九章》中提出了下面的算法 把一个n次多项式f(x)=anx+an1x+…+a1x+a改写成如下形式 f(x=anx+a-x+.+ax+ao X“+an-1X +a2)x+a1)x+ Fau) xta 求多项式的值时,首先计算最内层括号内一次多项式的值,即 VI=a.xtan-, 然后由内向外逐层计算一次多项式的值,即 V3=V2X+a-3
7 设计感想 数学不仅是一门科学，也是一种文化，本节的引入从东、西方文化的不同开始，逐步向 学生渗透数学文化.从知识方面主要学习用两种方法求两个正整数的最大公约数，从思想方 法方面，主要学习递归思想.本节设置精彩例题，不仅让学生学到知识，而且让学生进一步 体会算法的思想，培养学生的爱国主义情操． 第 2 课时 案例 2 秦九韶算法 导入新课 思路 1（情境导入） 大家都喜欢吃苹果吧，我们吃苹果都是从外到里一口一口的吃，而虫子却是先钻到苹果 里面从里到外一口一口的吃，由此看来处理同一个问题的方法多种多样.怎样求多项式 f(x)=x5 +x4 +x3 +x2 +x+1 当 x=5 时的值呢？方法也是多种多样的，今天我们开始学习秦九韶算 法. 思路 2（直接导入） 前面我们学习了辗转相除法与更相减损术， 今天我们开始学习秦九韶算法. 推进新课 新知探究 提出问题 （1）求多项式 f(x)=x5 +x4 +x3 +x2 +x+1 当 x=5 时的值有哪些方法？比较它们的特点. （2）什么是秦九韶算法？ （3）怎样评价一个算法的好坏？ 讨论结果： （1）怎样求多项式 f(x)=x5 +x4 +x3 +x2 +x+1 当 x=5 时的值呢？ 一个自然的做法就是把 5 代入多项式 f(x)，计算各项的值，然后把它们加起来，这时， 我们一共做了 1+2+3+4=10 次乘法运算，5 次加法运算. 另一种做法是先计算 x 2 的值，然后依次计算 x 2·x，（x 2·x）·x，（（x 2·x）·x）·x 的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了 4 次乘法运算，5 次加 法运算. 第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于 计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法， 计算机能更快地得到结果. （2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约 1202~1261）在 他的著作《数书九章》中提出了下面的算法： 把一个 n 次多项式 f(x)=anx n +an-1x n-1 +…+a1x+a0改写成如下形式： f(x)=anx n +an-1x n-1 +…+a1x+a0 =（anx n-1 +an-1x n-2 +…+a1）x+ a0 =（（anx n-2 +an-1x n-3 +…+a2）x+a1)x+a0 =… =（…（（anx+an-1）x+an-2）x+…+a1）x+a0. 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1=anx+an-1， 然后由内向外逐层计算一次多项式的值，即 v2=v1x+an-2， v3=v2x+an-3， …
V,Vo-xtao 这样,求n次多项式f(x)的值就转化为求n个一次多项式的值 上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法 (3)计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志 仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这 样的算法就只能是一个理论的算法 应用示例 例1已知一个5次多项式为f(x)=5x°+2x+3.5x2-2.6x2+1.7x-0.8, 用秦九韶算法求这个多项式当x=5时的值 解:根据秦九韶算法,把多项式改写成如下形式 f(x)=((5x+2)x+3.5)x-2.6)x+1.7)x0.8, 按照从内到外的顺序,依次计算一次多项式当x=5时的值 V1=5×5+2=27; V2=27×5+3.5=138.5; V3=138.5×5-2.6=689.9 V=689.9×5+1.7=3451.2 V5=3415.2×5-0.8=17255.2 所以,当x=5时,多项式的值等于17255.2. 算法分析:观察上述秦九韶算法中的n个一次式,可见v的计算要用到v-的值,若令w=a 我们可以得到下面的公式 k=V-1x+ank(k=1,2,…,m) 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现. 算法步骤如下: 第一步,输入多项式次数n、最高次的系数a。和ⅹ的值. 第二步,将v的值初始化为a,将i的值初始化为n-1 第三步,输入i次项的系数a; 第四步,v=vx+a;,i=i-1 第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值 程序框图如下图
8 vn=vn-1x+a0， 这样，求 n 次多项式 f（x）的值就转化为求 n 个一次多项式的值. 上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法. （3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志 仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这 样的算法就只能是一个理论的算法. 应用示例 例 1 已知一个 5 次多项式为 f（x）=5x5 +2x4 +3.5x3 -2.6x2 +1.7x-0.8， 用秦九韶算法求这个多项式当 x=5 时的值. 解：根据秦九韶算法，把多项式改写成如下形式： f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8， 按照从内到外的顺序，依次计算一次多项式当 x=5 时的值： v0=5； v1=5×5+2=27; v2=27×5+3.5=138.5; v3=138.5×5-2.6=689.9; v4=689.9×5+1.7=3 451.2; v5=3 415.2×5-0.8=17 255.2; 所以，当 x=5 时，多项式的值等于 17 255.2. 算法分析：观察上述秦九韶算法中的 n 个一次式，可见 vk 的计算要用到 vk-1 的值，若令 v0=an， 我们可以得到下面的公式： = + = = − − ( 1,2, , ). , 1 0 v v x a k n v a k k n k n 这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现. 算法步骤如下： 第一步，输入多项式次数 n、最高次的系数 an 和 x 的值. 第二步，将 v 的值初始化为 an，将 i 的值初始化为 n-1. 第三步，输入 i 次项的系数 ai. 第四步，v=vx+ai,i=i-1. 第五步，判断 i 是否大于或等于 0.若是，则返回第三步；否则，输出多项式的值 v. 程序框图如下图：
G始〕 输人几ax的值/ =-1 /输人a/ 程序: INPUT“n=”;n INPUT“an=”; INPUT WhILE i>=0 PRINT“i=”;i v=v冰x+a WEND PRINT V END 点评:本题是古老算法与现代计算机语言的完美结合,详尽介绍了思想方法、算法步骤、程 序框图和算法语句,是一个典型的算法案例. 变式训练 请以5次多项式函数为例说明秦九韶算法,并画出程序框图 解;设f(x)=a5x°+a1x+a3x+a2x2+a1x+ao 首先,让我们以5次多项式一步步地进行改写 f (x)=(asxtaxta3xta2xtai)x+ao (Casx+ax2+ a3x+a,)x+au)x+ (((asx ta, x+ a3)xta2)xta,) xtao =((((a5x+a4)x+a3)x+a2)x+a1)x+a0 上面的分层计算,只用了小括号,计算时,首先计算最内层的括号,然后由里向外逐层计算, 直到最外层的括号,然后加上常数项即可. 程序框图如下图:
9 程序： INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i＞=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END 点评：本题是古老算法与现代计算机语言的完美结合，详尽介绍了思想方法、算法步骤、程 序框图和算法语句,是一个典型的算法案例. 变式训练 请以 5 次多项式函数为例说明秦九韶算法，并画出程序框图. 解：设 f（x）=a5x 5 +a4x 4 +a3x 3 +a2x 2 +a1x+a0 首先，让我们以 5 次多项式一步步地进行改写： f（x）=（a5x 4 +a4x 3 +a3x 2 +a2x+a1）x+a0 =（（a5x 3 +a4x 2 + a3x+a2）x+a1）x+a0 =（（（a5x 2 +a4x+ a3）x+a2）x+a1）x+a0 =（（（（a5x+a4）x+ a3）x+a2）x+a1）x+a0. 上面的分层计算,只用了小括号，计算时，首先计算最内层的括号，然后由里向外逐层计算， 直到最外层的括号，然后加上常数项即可. 程序框图如下图：
开始 输入a1aa3aa、a =m=+1 输出y/ 例2已知n次多项式P(x)=ax+a1x+…+a-x+a,如果在一种算法中,计算x6(k=2,3, 4,…,n)的值需要k一1次乘法,计算P3(x)的值共需要9次运算(6次乘法,3次加法), 那么计算P10(x0)的值共需要 次运算.下面给出一种减少运算次数的算法 次运计算(的值共要次运用该第达,计算Bd的值共 点评:秦九韶算法适用一般的多项式f(x)=anx+anx7+…+a1x+a的求值问题.直接法乘法运 算的次数最多可到达(+1,加法最多n次秦九韶算法通过转化把乘法运算的次数减少 到最多n次,加法最多n次 例3已知多项式函数f(x)=2x-5x-4x+3x2-6x+7,求当x=5时的函数的值 解析:把多项式变形为:f(x)=2x°-5x4-4x+3x2-6x+7 (2x-5)x-4)x+3)x-6)x+7 计算的过程可以列表表示为 变形后的数23一1-25105,540y今 多项式x系数 运算所得的值 211085342677*5 最后的系数2677即为所求的值 算法过程: V1=2×5-5=5; V2=5×5-4=21 V3=21×5+3=108 V=108×5-6=534 Vs=534×5+7=2677. 点评:如果多项式函数中有缺项的话,要以系数为0的项补齐后再计算 知能训练 当x=2时,用秦九韶算法求多项式f(x)=3x°+8x-3x3+5x2+12x-6的值 解法一:根据秦九韶算法,把多项式改写成如下形式: f(x)=((3x+8)x-3)x+5)x+12)x-6. 按照从内到外的顺序,依次计算一次多项式当x=2时的值 V1=vo×2+8=3×2+8=14 V2=v1×2-3=14×2-3=25
10 例 2 已知 n 次多项式 Pn(x)=a0x n +a1x n-1 +…+an-1x+an，如果在一种算法中，计算 k x0 （k=2，3， 4，…，n）的值需要 k－1 次乘法，计算 P3(x0)的值共需要 9 次运算（6 次乘法，3 次加法）， 那么计算 P10(x0)的值共需要__________次运算.下面给出一种减少运算次数的算法： P0(x)=a0,Pk+1(x)=xPk(x)+ak+1（k＝0，1，2，…，n－1）．利用该算法，计算 P3(x0)的值共需 要 6 次运算，计算 P10(x0)的值共需要___________次运算. 答案：65 20 点评：秦九韶算法适用一般的多项式 f(x)=anx n +an-1x n-1 +…+a1x+a0 的求值问题.直接法乘法运 算的次数最多可到达 2 (n +1)n ，加法最多 n 次.秦九韶算法通过转化把乘法运算的次数减少 到最多 n 次，加法最多 n 次. 例 3 已知多项式函数 f(x)=2x5－5x4－4x3 +3x2－6x+7，求当 x=5 时的函数的值. 解析：把多项式变形为：f(x)=2x5－5x4－4x3 +3x2－6x+7 =((((2x－5)x－4)x+3)x－6)x+7. 计算的过程可以列表表示为： 最后的系数 2 677 即为所求的值. 算法过程： v0=2； v1=2×5－5=5； v2=5×5－4=21； v3=21×5+3=108； v4=108×5－6=534； v5=534×5+7=2 677. 点评：如果多项式函数中有缺项的话，要以系数为 0 的项补齐后再计算. 知能训练 当 x=2 时，用秦九韶算法求多项式 f(x)=3x5 +8x4 -3x3 +5x2 +12x-6 的值． 解法一：根据秦九韶算法，把多项式改写成如下形式： f(x)=((((3x+8)x-3)x+5)x+12）x-6. 按照从内到外的顺序，依次计算一次多项式当 x=2 时的值. v0=3; v1=v0×2+8=3×2+8=14; v2=v1×2-3=14×2-3=25;