福建省平潭县高中数学 1.3 算法案例1导学案 新人教A版必修3

1 1 3 1 3 算法案例算法案例 1 1 授课 时间 第 周 星期 第 节 课 型 新授 课 主 备 课 人 刘百 波 学习 目标 1 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进行 算法分析 2 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程 序 重点难点 理解辗转相除法与更相减损术求最大公约数的方法 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 学习 过程 与方 法 自主学习自主学习 认真自学课本 34 37 1 辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直 到大数被小数除尽为止 这时的较小的数即为原来两个数的最大公约数 2 更相减损术 就是对于给定的两个正整数 用较大的数减去较小的数 然后将差和较小的数构成新的一对数 继续上面的减法 直到差和较小的数 相等 此时相等的两数即为原来两个数的最大公约数 合作探究 一 合作探究 一 辗转相除法辗转相除法 思考 1 18 与 30 的最大公约数是多少 你是怎样得到的 思考 2 对于 8251 与 6105 这两个数 由于其公有的质因数较大 利用上述方 法求最大公约数就比较困难 注意到 8251 6105 1 2146 那么 8251 与 6105 这两个数的公约数和 6105 与 2146 的公约数有什么关系 思考 3 又 6105 2146 2 1813 同理 6105 与 2146 的公约数和 2146 与 1813 的公约数相等 重复上述操作 你能得到 8251 与 6105 这两个数的最大公约数 吗 思考 4 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算 法 一般地 用辗转相除法求两个正整数 m n 的最大公约数 可以用什么逻 辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数 m n m n 第二步 第三步 第四步 思考 5 该算法的程序框图如何表示 思考 6 该程序框图对应的程序如何表述 2 思考 7 如果用当型循环结构构造算法 则用辗转相除法求两个正整数 m n 的 最大公约数的程序框图和程序分别如何表示 合作探究 二 合作探究 二 更相减损术更相减损术 思考 1 设两个正整数 m n 若 m n k 则 m 与 n 的最大公约数和 n 与 k 的最大 公约数相等 反复利用这个原理 可求得 98 与 63 的最大公约数为多少 思考 2 上述求两个正整数的最大公约数的方法称为更相减损术 一般地 用更 相减损术求两个正整数 m n 的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数 m n m n 第二步 第三步 第四步 思考 3 该算法的程序框图如何表示 思考 4 该程序框图对应的程序如何表述 合作探究 三 合作探究 三 辗转相除法与更相减损术的区别辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以 为主 更 相减损术以 为主 计算次数上辗转相除法计算次数相对 特别 当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是 则得 到 而更相减损术则以 相等而得到 自我检测 自我检测 例 1 分别用辗转相除法和更相减损术求 168 与 93 的最大公约数 辗转相除法 更相减损术 例 2 求 325 130 270 三个数的最大公约数 达标检测 达标检测 1 在对 16 和 12 求最大公约数时 整个操作如下 16 12 4 12 4 8 4 4 由此可以看出 12 和 16 的最大公约数是 3 A 4 B 12 C 16 D 8 2 下列各组关于最大公约数的说法中不正确的是 A 16 和 12 的最大公约数是 4 B 78 和 36 的最大公约数是 6 C 85 和 357 的最大公约数是 34 D 105 和 315 的最大公约数是 105 3 算法 输入 若 表示 的整数部分 则输出 否则执行 执行 输出 上述算法的含义是 4 用辗转相除法求 840 与 1785 的最大公