高中数学 5.4.2《算法案例2》教案 苏教版必修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 求两个正数 8 251 和 6 105 的最大公约数 分析 8 251 与 6 105 两数都比较大 而且没有明显的公约数 如能把它们都变小一点 根据已有的知识即可求出最大公约数 解 8 251 6 105 1 2 146 显然 8 251 和的 2 146 最大公约数也必是 2 146 的约数 同样 6 105 与 2 146 的公约数 也必是 8 251 的约数 所以 8 251 与 6 105 的最大公约数也是 6 105 与 2 146 的最大公约 数 6 105 2146 2 1813 2 146 1813 1 333 1 813 333 5 148 333 148 2 37 148 37 4 0 则 37 为 8 251 与 6 105 的最大公约数 小结 以上我们求最大公约数的方法就是欧几里得辗转相除法 其求最大公约数的步骤如 下 第一步 用较大的数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 204 85 的余数为 34 S2 85 34 的余数为 17 用心 爱心 专心 2 S3 34 17 的余数为 0 所以它们的最大公约数为 17 算法描述 计算出 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 流程图 伪代码伪代码 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 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 c m Int m n n 用心 爱心 专心 4 m n n c End While Print n Int x 表示不超过 x 的最大整数 解 求 m n 的最大公约数 2 用辗转相除法求下列各组数的最大公约数 1 225 135 2 98 196 3 用更相减损法求下列各组数的最大公约数 31 72 168 2 153 119 4 现有长度为 360cm 和 780cm 两种规格的钢筋若干 要焊接一批正方形模型 问 怎样才能保 证正方体体积最大且不浪费 思路点拨 正方体的所有棱长都相等 故必须将钢筋剪裁成长度相等的钢筋条 又必须不浪费 这 就说明必须剪后无剩余 于是为了保证正方体的体积最大 故剪的钢筋的最大长度为 360cm 和 780cm 的最大公约数 可用更相减损术求最大公约数 用心 爱心 专心 5 第第 1111 课时算法案例课时算法案例 2 2 分层训练分层训练 1 阅读下列代码 写出该代码的运行结果 t 1 n 3 s 0 While s 10 t t n s s t End While Print s 答 2 设计一个计算 1 3 5 7 9 的算法 下面给出了程序的一部分 则在横线上不能填入 下面数据中的 S l I 3 While I S S I I I 2 End While Print S A 9 B 9 5 C 10 D 10 5 3 下列一段伪代码执行结束后 S 的目的是 S 0 a l For I From l To 4 a 2a S S a End For A 计算 2 22 23 24 B 计算 2 22 23 C 计算 23 D 计算 24 4 先用不同的算法计算 1111 1 22 33 499 100 再比较其优劣 5 已知 ABC 中 ABc BCa CAb 试写出作 ABC 的一个算法 用心 爱心 专心 6 6 用条件语句表示 输入 x 的值 通过 1 24 2 2 2 2 2 2 x xx yxx x 计算 y 的值 7 写出求 123100 a a aa 中最大数的一个算法 8 一球从 l00m 高度落下 每次落地后反弹回原高度的一半 再落下 在第十次落地时 共 经过多少路程 第十次下落多高 思考思考 运用运用 9 我国古代劳动人民对不定方程的研究作出过重要贡献 其中 张丘建算经 中的百 鸡问题就是一个很有影响力的问题 今有鸡翁一值钱五 鸡母一值钱三 鸡雏三值钱一 凡百钱买百鸡 问鸡翁 母 雏各几何 其意思是 一只公鸡