高中数学 第五章 第12课时《算法案例二》教案（学生版） 苏教版必修3

用心 爱心 专心1 第第 1212 课时课时 5 45 4 算法案例算法案例 重点难点重点难点 重点重点 通过案例分析理解辗转相除法与更相减损术求最大公约数的方法 体会算法思想 难点难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 学习要求学习要求 1 理解辗转相除法与更相减损术中蕴含的 数学原理 并能根据这些原理进行算法分 析 2 基本能根据算法语句与程序框图的知识 设计完整的程序框图并写出算法程序 课堂互动课堂互动 问题 问题 写出求两个正整数 a b a b 的最大公 约数的一个算法 1 1 辗转相除法辗转相除法 公元前 3 世纪 欧几里得介绍了求两个 正整数 a b a b 的最大公约数的方法 求 出一列数 0 121nn rrrrba 这列数 从第三项开始 每一项都是前两项相除所 得的余数 即 12 nnn rrModr 余数 等于 0 的前一项 n r 即是 a 和 b 的最大公 约数 这种方法称为 欧几里得辗转相除 法 例 1 求两个正数 8251 和 6105 的最大公约 数 分析 8251 与 6105 两数都比较大 而且 没有明显的公约数 如能把它们都变小一 点 根据已有的知识即可求出最大公约数 解 8251 6105 1 2146 显然 8251 和 2146 的最大公约数也必 是 2146 的约数 同样 6105 与 2146 的公约 数也必是 8251 的约数 所以 8251 与 6105 的最大公约数也是 6105 与 2146 的最大公 约数 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 则 37 为 8251 与 6105 的最大公约数 小结 以上我们求最大公约数的方法就是欧 几里得辗转相除法 其求最大公约数的步骤如 下 第一步 用较大的数m除以较小的数n得 到一个商 0 q和一个余数 0 r 第二步 若 0 0r 则n为 m n的最大公 约数 若 0 0r 则用除数n除以余数 0 r得到 一个商 1 q和一个余数 1 r 第三步 若 1 0r 则 1 r为 m n的最大公 约数 若 1 0r 则用除数 0 r除以余数 1 r得到 一个商 2 q和一个余数 2 r 依次计算直至0 n r 此时所得到的 1n r 即为所求的最大公约数 练习 求 a 204 b 85 的最大公约数 步骤 为 S1 S2 S3 所以它们的最大公约数为 算法描述 计算出 a b 的余数 r 若 r 0 则 b 为 a b 的最大公约数 若 r 0 则 把前面的除数 b 作为新的被除数 把余数 r 作 为新的除数 a b 要重新赋值 a b b r 继续进行上述运算 直到余数为 0 用 While 循 环语句 循环的执行条件是 r 0 当 r 0 时 循环终止 此时的除数即为所求的最大公约数 算法如下 S1 输入两个正整数 a b a b S2 若 Mod a b 0 则转 S3 否则 r Mod a b a b b r 转 S2 S3 输出最大公约数 b 流程图 用心 爱心 专心2 伪代码伪代码 2 2 更相减损法更相减损法 我国早期也有解决求最大公约数问题 的算法 就是更相减损术 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母之数 以少减多 更相减损 求其等也 以等数 约之 翻译出来为 第一步 任意给出两个正数 判断它 们是否都是偶数 若是 用 2 约简 若不 是 执行第二步 第二步 以较大的数减去较小的数 接着 把较小的数与所得的差比较 并以大数减小 数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 再从这个角度看一下 求 a 204 b 85 的 最大公约数 的问题 S1 步可以等价为等式 34285204 S2 步可以等价为等式 1723485 这两步从减法的角度可以理 解为 204 85 所得的差与减式中的较小数比 较 再用大的数减小的数 循环执行以上步骤 直到结果为 0 此时减数就是 a 和 b 的最大公 约数 这一算法根据它的特点 也可以用循环 语句完成 参考代码参考代码 a 放较大的数 b 放较小的数 If a r Then a b b r Else a r End If r a b 确保相减后仍用较大的数减去较小的数 End While Print b 用 更相减损法 求多于两个数的最大公 约数就可以显示出其优越性 小结小结 比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相 除法以除法为主 更相减损术以减法为主 计 算次数上辗转相除法计算次数相对较少 特别 当两个数字大小区别较大时计算次数的区别较 明显 2 从结果体现形式来看 辗转相除法体现结 果是以相除余数为 0 则得到 而更相减损术则 以减数与差相等而得到 追踪训练 1 分析下面一段代码的目的 Read m n While m n Int m n Read a b While Mod a b 0 r Mod a b a b b r End While Print b 开始 b r Y N 结束 输入 a b a b r Mod a b Mod a b 0 输出 b 用心 爱心 专心3 c m Int m n n m n n c End While Print n Int x 表示不超过 x 的最大整数 解 2 用辗转相除法求下列各组数的最大公约 数 1 225 135 2 98 196 3 用更相减损法求下列各组数的最大公约 数 31 72 168 2 153 119 4 现有长度为 360cm 和 780cm 两种规格的 钢筋若干 要焊接一批正方形模型 问怎样 才能保证正方体体积最