1、郑州一中主体课堂 学习指导书 13 算法案例算法案例 第第一一课时课时 辗转辗转相除法与相除法与更相更相减损术减损术 授课人：郑州一中 胡莉萍 【知识沙盘知识沙盘】 基基本本概概念念辗辗转转相相除除法法与与更更相相减减损损术术 算算法法初初步步 基基本本结结构构算算法法案案例例 秦秦九九韶韶算算法法 进进位位制制基基本本语语句句 【自主学习自主学习】 A 级级 1.分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求 168 与与 93 的最大公约数，写出计算过的最大公约数，写出计算过 程程. 辗转相除法：辗转相除法： 更相减损术：更相减损术： 168=93 1+75 168-93=7
2、5 2.根据算法步骤根据算法步骤补充完整补充完整辗转相除辗转相除法求最大公约数的程序框法求最大公约数的程序框图，图， 并并根据框图根据框图 写出程序写出程序. 郑州一中主体课堂 学习指导书 3将辗转相除法的直到型循环结构改写为当型循环结构将辗转相除法的直到型循环结构改写为当型循环结构, 根据框图写出程根据框图写出程 序序. 思考思考： （1）初始初始输入的输入的 m,n 是否是否需要比较大小？需要比较大小？ （2）输出）输出的的结果结果是是 m 还是还是 n ？ B 级级 求求 420，588，1092 三个数的最大公约数三个数的最大公约数. C 级级(拓展拓展) 求求 420，588 的的最
3、最小小公倍数公倍数. 思考思考：能否将求：能否将求最大公约的程序框图改编为求最最大公约的程序框图改编为求最小小公倍数的程序呢？公倍数的程序呢？ 【交流研讨交流研讨】 请同学们讨论各自的疑惑及感悟，提出问题，并相互解决请同学们讨论各自的疑惑及感悟，提出问题，并相互解决 郑州一中主体课堂 学习指导书 【归类归类方法方法】 使用辗转相除法时，余数是使用辗转相除法时，余数是 0 时得到最大公约数；使用更相减损术时，当时得到最大公约数；使用更相减损术时，当 减数与差相等时得到最大公约数减数与差相等时得到最大公约数. 【自我测评自我测评】 1. 必做题：用辗转相除法求下列两数的最大公约数，并用更相减损术检验必做题：用辗转相除法求下列两数的最大公约数，并用更相减损术检验 你的结果你的结果： （： （1）228，48； （； （2）185，98. 2. 选做题：求选做题：求 225，135 最小公倍数最小公倍数. 3. 拓展延伸：请查阅相关书籍资料画出更相减损术这种算法的程序框图，拓展延伸：请查阅相关书籍资料画出更相减损术这种算法的程序框图， 并用语句来描述这个算法并用语句来描述这个算法.
