1.3.1 算法案例---辗转相除法与更相减损术

《1.3.1 算法案例---辗转相除法与更相减损术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、长沙市中（小）学教师统一备课用纸科目数学年级高一班级时间年月日课题1.3.1算法案例---辗转相除法与更相减损术教学目标理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.教材分析重点：理解辗转相除法与更相减损术求最大公约数的方法.难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.实施教学过程设计一、复习准备：1.回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.2.提问：①小学学过的求两个数

2、最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数.②除了用这种方法外还有没有其它方法？，和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至，得出4即是36和64的最大公约数.二、讲授新课：1.教学辗转相除法：例1：求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数.（适用于两数较大时）①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除

3、法求最大公约数的步骤如下：（1）用较大的数m除以较小的数n得到一个商和一个余数；（2）若＝0，则n为m，n的最大公约数；若≠0，则用除数n除以余数得到一个商和一个余数；（3）若＝0，则为m，n的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；……依次计算直至＝0，此时所得到的即为所求的最大公约数.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数.（乘

4、法格式、除法格式）2.教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术.在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例2：用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，

5、这个数（等数）就是所求的最大公约数.（反思：辗转相除法与更相减损术是否存在相通的地方）练习：用更相减损术求72和168的最大公约数.3.小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.三、巩固练习：1、练习：教材P35第1题　　2、作业：教材P38第1题教学反思