(
课件网) 第11章 算法初步 第11章 算法初步 较大数 较小数 余数和较小数 较小数 × √ 本部分内容讲解结束 按ESC键退出全屏播放 A 预习案,自生学习 研读·思考·尝试11.4 算法案例 1.理解辗转相除法与秦九韶算法的含义，了解其执行过程. 2.掌握用算法解决实际问题. 1.辗转相除法 所谓辗转相除法，就是对于给定的两个正整数，用较大数除以较小数Ｗ.若余数不为零，则将余数和较小数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小数就是原来两个数的最大公约数. 伪代码如下： INPUT a，bDO r＝a MOD b a＝b b＝rLOOP UNTIL r＝0PRINT aEND 2.秦九韶算法 秦九韶算法其实质是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，最多只需做n次乘法和n次加法即可. 伪代码如下： INPUT———n＝”；nINPUT———an＝”；aINPUT———x＝”；xv＝ak＝n－1WHILE k>＝0 PRINT———k＝”；k INPUT———ak＝”；a v＝v x＋a k＝k－1WENDPRINT vEND 1.判断正误.(对的打“√”，错的打“×”) (1)求两个正整数的最大公约数可以用辗转相除法.( ) (2)利用秦九韶算法计算时，乘法运算与加法运算次数相等.( ) 答案：(1)√ (2)× 2.用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是( ) A.6，6 B.5，6 C.5，5 D.6，5 答案：A 3.“辗转相除法”与“更相减损术”有何区别？ 解：辗转相除法的操作过程是先用两个数中较大的数除以较小的数，得商和余数；再用除数除以余数，重复操作，直到出现余数为零，则这个最小除数就是两个数的最大公约数；而更相减损术是用较大数减去较小数，再把差与较小数作为一对相减直至差相等为止，则这个等数就是所求的最大公约数. 辗转相除法[学生用书P22] 利用辗转相除法求46，115和276的最大公约数. 【解】 求三个数的最大公约数，可以先求两个数的最大公约数，然后求第三个数与前两个数的最大公约数. 276＝2×115＋46，115＝2×46＋23，46＝23×2， 所以276与115的最大公约数为23. 又46与23的最大公约数为23， 所以46、115和276的最大公约数为23. 利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数. 1.378与90的最大公约数为 Ｗ. 解析：辗转相除法： 378＝90×4＋18， 90＝18×5＋0， 所以378与90的最大公约数是18. 答案：18 二分法[学生用书P22] 写出用二分法求方程x3－2x－3＝0在区间[1，2]内的一个近似解(误差不超过0.001)的一个算法. 【解】 算法如下： S1：令f(x)＝x3－2x－3，a＝1，b＝2，c＝0.001； S2：取x0＝； S3：若|a－b|≥c，则进入S4；否则输出x0结束算法； S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法； S5：若f(x0)f(a)>0，则解在[x0，b]中，用x0替换a； 若f(x0)f(a)<0，则解在[a，x0]中，用x0替换b，返回S2. 用二分法求方程的近似解的步骤 (1)画草图探索解所在的区间； (2)用二分法求符合限制条件的解； (3)编制伪代码用计算机完成. 2.写出用二分法求方程x2－2＝0的一个正的近似解(误差不超过0.005)的算法. 解：算法如下： S1：令f(x)＝x2－2，因为f(1)<0，f(2)>0， 所以令a＝1，b＝2，c＝0.005； S2：取x0＝； S3：若|a－b|≥c，则进入S4；否则输出x0结束算法； S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法； S5：若f(a)·f(x0)>0，则解在[x0，b]，用x0替换a ... ...
