§1.3.1辗转相除法与更相减损术导案

一、创设情景、导入课题 1.研究一个实际问题的算法，主要从哪几方面展开？
2.在程序框图中算法的基本逻辑结构有哪几种？
3.在程序设计中基本的算法语句有哪几种？
4.思考 1:18 与 30 的最大公约数是多少？你是怎样得到的？
5. 思考 2:对于 8251 与 6105 这两个数，它们的最大公约数是多少？你是怎样得 到的？ 由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没 有其它的方法可以较简单的找出它们的最大公约数呢？ 二、师生互动、探究新知 1. 辗转相除法 思考 3：注意到 8251=6105×1+2146，那么 8251 与 6105 这两个数的公约数 和 6105 与 2146 的公约数有什么关系？ 我们发现 6105=2146×2+1813， 同理， 6105 与 2146 的公约数和 2146 与 1813 的公约数相等. 思考 4：重复上述操作，你能得到 8251 与 6105 这两个数的最大公约数吗？ 6105＝2146×2＋1813
2.更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求 两个数的最大公约数 更相减损术求最大公约数的步骤如下： “可半者半之，不可半者，副置分母、 子之数，以少减多，更相减损，求其等也，以等数约之.” 翻译出来为： 第一步：任意给出两个正整数；判断它们是否都是偶数. 若是，用 2 约简； 若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以 大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个 数与约简的数的乘积就是所求的最大公约数. 例 1 用更相减损术求 98 与 63 的最大公约数. 解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减，即：98－ 63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98 与 63 的最大公约数是 7。
课后反思
INPUT m，n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
思考 6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数 m，n 的最大公约数的程序框图和程序分别如何表示？
INPUT m，n WHILE n>0 r=m MOD n m=n n=r WEND PRINT m END
四、课堂小结 1、辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数， 若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大 数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 2、更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数， 然后将差和较小的数构成新的一对数， 继续上面的减法， 直到差和较小的数相等， 此时相等的两数即为原来两个数的最大公约数. 五、作业布置
练习：用更相减损术求两个正数 84 与 72 的最大公约数。 （答案：12） 三、例题讲解 例 2 分别用辗转相除法和更相减损术求 168 与 93 的最大公约数. 辗转相除法： 168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6. 更相减损术: 168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3. 例 3 求 325，130，270 三个数的最大公约数. 因为 325=130×2+65，130=65×2，所以 325 与 130 的最大公约数是 65. 因为 270=65×4+10，65=10×6+5，10=5×2，所以 65 与 270 最大公约数是 5. 故 325，130，270 三个数的最大公约数是 5. 例 4.用更相减损术求两个正整数 m，n 的最大公约数，可以用什么逻辑结构来构 造算法？其算法步骤如何设计？ 第一步，给定两个正整数 m，n(m>n). 第二步，计算 m-n 所得的差 k. 第三步，比较 n 与 k 的大小，其中大者用 m 表示，小者用 n 表示.
武威十六中教学导学案教案
学科 主备课人 使用教师 课 题 学习 目标 重 点 难 点 教学 方法 高一 课 时 1 课时 审核人 高一数学备课组 使用时间 年 月 日 §1.3.1 辗转相除法与更相减损术 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法 分析。 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 进一步培养学生数形结合解决问题的能力 理解辗转相除法与更相减损术求最大公约数的方法。 把辗转相除法与更相减损术的方法转换成程序框图与程序语言。 引导、探究式、练习法 教学设计 个性化修改 数学 年 级 蒋继荣
第四步，若 m=n，则 m，n 的最大公约数等于 m；否则，返回第二步. 讨论:该算法的程序框图如何表示？ 讨论:该程序框图对应的程序如何表述？
INPUT m，n WHILE m≠n k=m-n IF n>k THEN m=n n=k ELSE m=k END IF WE3 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由 欧几里德在公元前 300 年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数 m 除以较小的数 n 得到一个商 q 0 和一个余数 r0 ； 第二步：若 r0 ＝0，则 n 为 m，n 的最大公约数；若 r0 ≠0，则用除数 n 除以 余数 r0 得到一个商 q1 和一个余数 r1 ； 第三步：若 r1 ＝0，则 r0 为 m，n 的最大公约数；若 r1 ≠0，则用除数 r0 除以余 数 r1 得到一个商 q 2 和一个余数 r2 ； „„ 依次计算直至 rn ＝0，此时所得到的 rn 1 即为所求的最大公约数. 思考 5:你能把辗转相除法编成一个计算机程序吗？ 第一步，给定两个正整数 m，n(m>n). 第二步，计算 m 除以 n 所得的余数 r. 第三步，m=n，n=r. 第四步，若 r=0，则 m，n 的最大公约数等于 m；否则，返回第二步.