《k5§1.3.1辗转相除法与更相减损术(珠海市斗门和风中学邝国均).pdf》由会员分享，可在线阅读，更多相关《k5§1.3.1辗转相除法与更相减损术(珠海市斗门和风中学邝国均).pdf（3页珍藏版）》请在三一文库上搜索。
1、知识就是力量 本文为自本人珍藏版权所有仅供参考 13 辗转相除法与更相减损术 珠海市斗门和风中学邝国均 【教学目标】： （1） 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。 （2） 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 【教学重点】理解辗转相除法与更相减损术求最大公约数的方法。 【教学难点】把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 【学法与教学用具】： 学法： 比较辗转相除法与更相减损术求最大公约数在算法上的区别，并从程序的学习中体会 数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言
2、的一般步骤。 教学用具:计算机， TI-voyage200 图形计算器 【教学过程】 提出问题： 在小学，我们已经学过求最大公约数的知识，如口算求出12 与 20 的公约数。 分析： 我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不 能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与 6105的最大公 约数？这就是我们这一堂课所要探讨的内容。 辗转相除法 例 1 求两个正数 8251和 6105的最大公约数。 分析： 8251 与 6105 两数都比较大，而且没有明显的公约数，可以把它们都变小一点，根据 已有的知识即可求出最大公约数 82516
3、10512146 显然 8251的最大公约数也必是2146的约数， 同样 6105与 2146的公约数也必是 8251的约数， 所以 8251 与 6105 的最大公约数也是6105与 2146的最大公约数。 6105214621813 214618131333 18133335148 333148237 1483740 则 37 为 8251与 6105 的最大公约数。 以上我们求最大公约数的方法就是辗转相除法 。也叫 欧几里德算法 ，它是由欧几里德在公元 前 300 年左右首先提出的。利用辗转相除法求最大公约数的步骤如下： （1） ：用较大的数 m除以较小的数 n 得到一个商 0 S 和一
4、个余数 0 R ； 知识就是力量 （2） ：若 0 R 0，则 n 为 m ，n 的最大公约数；若 0 R 0，则用除数 n 除以余数 0 R 得到一个商 1 S 和一个余数 1 R ； （3） ：若 1 R 0，则 1 R 为 m ，n 的最大公约数； 若 1 R 0，则用除数 0 R 除以余数 1 R 得到一个商 2 S 和一个余数 2 R ；, 依次计算直至 n R0，此时所得到的 1n R 即为所求的最大公约数。 其程序框图见课本 其程序语言（ BASIC ）如下： INPUT “m= ”;m INPUT “n=”;n IF m MOD n=n n=x END IF r=m MOD n
5、 WHILE r0 r=m MOD n m=n n=r WEND PRINT m END 学生利用 TI-voyage200 图形计算器操作：（老师现场指导） 输入不同的 m、n 都可以算出它们的最大公约数。这下子，学生会感到自己变得神通广 大了。利用 TI-voyage200 图形计算器更能培养学生的动手操作能力，并让他们获得完成程序 后的成功感！ 更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术。在九章算术中记载了更 相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数，以少减多，更相 减损，求其等也，以等数约之。 翻译为： （1） ：任意给出两个正数；判断
6、它们是否都是偶数。若是，用2 约简；若不是，执行第二步。 （2） ：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续 这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 运行 知识就是力量 例 2 用更相减损术求 98 与 63 的最大公约数 . 分析：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减， 即：986335 63 3528 35 287 28 721 21 714 14 77 所以， 98 与 63 的最大公约数是 7。 学生利用 TI-voyage200 图形计算器操作：（老师现场指导） （其中“ dashu”指输入数值大的整数， “ xiaoshu ”指数值小的整数，学生课余时间可以继 续修改） 辗转相除法与更相减损术的区别： （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计 算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区 别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0 则得到，而更相减损术则 以减数与差相等而得到 小结： 对比分析辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序。 思考： 利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在图形计算器 中实现。 运行