辗转相除法

辗转相除法 课题 1.3.1辗转相除法与更相减损术 1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分教学析; 目标 2.能根据算法语句与程序框图的知识完整的程序框图并写出算法程序. 教学理解辗转相除法与更相减损术求最大公约数的方法 重点 教学把辗 辗转相除法与更相减损术的方法转换成程序框图与程序语言难点 教学过程: 一:引入 问题一: 如何求18和30的最大公约数和最小公倍数, 最大公约数为___________________(列式) 最小公倍数为___________________(列式一) _______________________ (列式二) 问题二: 你能求出8251与6105的最大公约数吗, 二: 新知探究 探索:设两数分别为9k ，14k，k是整数。则这两数的最大公约数是____ 9k=5k 9k与5k的最大公约数是____ 14k- 9k-5k=4k 5k与4k的最大公约数是____ 你能得到什么结论 : (一 ) 更相减损术:以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减 小数.继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是 所求的最大公约数. 利用更相减损术，求98与63的最大公约数 练习1.用更相减损术求两个正数84与72的最大公约数 观察以上步骤，过程可以简单点吗, (二)辗转相除法 求8251和6105的最大公约数. :8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据 已有的知识即可求出最大公约数. 解: 练习2.利用辗转相除法求两数4081与20723的最大公约数 (三)比较辗转相除法与更相减损术 (1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主， 计算次数上辗转相除法计算次数相对较少。 (2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术 则以减数与差相等而得到. 思考:你能把辗转相除法编成一个计算机程序吗, 算法步骤如下: ，. 第一步:给定两个正整数mn 第二步:计算除以所得的余数. mnr 第三步:. m,n，n,r r,0第四步:若，则，的最大公约数等于;否则，返回第二步. mnm 程序框图: 程序: UNTIL型语句 INPUT "m,n="; m, n DO r = m MOD n m = n n = r LOOP UNTIL r = 0 PRINT m END WHILE型语句 INPUT "m,n="; m, n r = m MOD n WHILE r < > 0 r = m MOD n m = n n = r WEND PRINT m END 思考:你能用当型循环结构构造算法，求两个正整数的最大公约数吗,试写出程序框图. 三、归纳小结 辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写. 四、作业 课后习题1.2