§13算法案例(1)

兰州新区永登五中高一年级 数学 必修 3 导学案 学案设计 王超芬 科任老师 小组长签字 第 1 页 共 1 页 1 3 1 3 算法案例算法案例 1 1 班级班级 组名组名 姓名姓名 得分得分 学习目标学习目标 1 知识与能力 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进 行算法分析 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程 序 2 过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的 约分求公因式的方法 比较它们在算法上的区别 并从程序的学习中体会数学的严谨 领会数学算法计算机处理的结合方式 初步掌握把数学算法转化成计算机语言的一般步 骤 3 情感态度与价值观 通过阅读中国古代数学中的算法案例 体会中国古代数学对世界 数学发展的贡献 在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维 能力 在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力 4 学习重点 理解辗转相除法与更相减损术求最大公约数的方法 5 学习难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 温故互查温故互查 在初中 我们已经学过求最大公约数的知识 你能求出 18 与 30 的公约数吗 设问导读设问导读 探究 辗转相除法 求两个正数 8251 和 6105 的最大公约数 解 8251 6105 1 2146 显然 8251 的最大公约数也必是 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 的最大公约数 以上我们求最大公约数的方法就是 也叫欧几里德算法 它是由欧几里德 在公元前 300 年左右首先提出的 利用辗转相除法求最大公约数的步骤如下 第一步 用较大的数 m 除以较小的数 n 得到一个商 q0和一个余数r0 第二步 若r0 0 则 n 为 m n 的最大公约数 若r0 0 则用除数 n 除以余数r0得到一 个商 q1和一个余数r1 第三步 若r1 0 则r1为 m n 的最大公约数 若r1 0 则用除数r0除以余数r1得到 一个商 q2和一个余数r2 依次计算直至rn 0 此时所得到的rn 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 我国早期也有解决求最大公约数问题的算法 就是 更相减损术求最大公约 数的步骤如下 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求 其等也 以等数约之 翻译出来为 第一步 任意给出两个正数 判断它们是否都是偶数 若是 用 2 约简 若不是 执行 第二步 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 自学检测自学检测 例 1 用更相减损术求两个正数 98 与 63 的最大公约数 巩固练习巩固练习 1 我国古代数学发展一直处于世界领先水平 特别是宋 元时期的 算法 其中可以同欧几 里得辗转相除法相媲美的是 A 中国剩余定理 B 更相减损术 C 割圆术 D 秦九韶算法 2 840 和 1764 的最大公约数是 A 84 B 12 C 168 D 252 拓展延伸拓展延伸 利用辗转相除法求两数 4081 与 20723 的最大公约数 兰州新区永登五中高一年级 数学 必修 3 导学案 学案设计 王超芬 科任老师 小组长签字 第 1 页 共 1 页 1 3 1 3 算法案例算法案例 2 2 班级班级 组名组名 姓名姓名 得分得分 学习目标学习目标 1 知识与能力 了解秦九韶算法的计算过程 并理解利用秦九韶算法可以减少计算次数 提高计算效率的实质 2 过程与方法 模仿秦九韶计算方法 体会古人计算构思的巧妙 3 情感态度与价值观 通过对秦九韶算法的学习 了解中国古代数学家对数学的贡献 充分认识到我国文化历 史的悠久 通过对排序法的学习 领会数学计算与计算机计算的区别 充分认识信息技 术对数学的促进 4 学习重点 秦九韶算法的特点 两种排序法的排序步骤及计算机程序设计 5 学习难点 秦九韶算法的先进性理解 温故互查温故互查 1 回顾用辗转相除法和更相减损术求最大公约数的操作方法 2 三个数 42 56 78 的最大公约数是 头 头 头 头 头 头 头 头 头 头 头 头 头 头 头 wxckt wxckt 头 头 头 头 头 头 头 头 头 头 头 头 头 头 头 设问导读设问导读 探究 秦九韶算法 我们已经学过了多项式的计算 下面我们计算一下多项式f x x5 x4 x3 x2 x 1 当 x 5 时 的值 并统计所做的计算的种类及计算次数 根据我们的计算统计可以得出我们共需要 次乘法运算 次加法运算 我们把多项式变形为 f x x2 1 x 1 x 1 x x 1 再统计一下计算当 x 5 时的值时需要的计算次数 可以得出仅需 次乘法和 次加法运算即可得出结果 显然少了 次乘法运算 这种算法就叫秦九韶算法 探究 进位制 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 可使用数字 符号的个数称为基数 基数为 n 即可称 n 进位制 简称 n 进制 现在最常用的是十进制 通常使用 10 个阿拉伯数字 0 9 进行记数 1 把二进制数 110011 2 化为十进制数 解 110011 1 25 1 24 0 23 1 24 0 22 1 21 1 20 32 16 2 1 51 2 把 89 化为二进制数 解 89 2 44 1 44 2 22 0 22 2 11 0 11 2 5 1 5 2 2 1 所以 89 2 2 2 2 2 2 1 1 0 0 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1011001 1 自学检测自学检测 例 1 已知一个 5 次多项式为f x 4x5 2x4 3 5x3 2 6x2 1 7x 0 8 用秦九韶算法求这个多 项式当 x 5 时的值 例 2 把二进制数 110 011 2 化为十进制数 例 3 把 89 化为二进制数 巩固练习巩固练习 1 把 89 化成五进制的末尾数是 A 1 B 2 C 3 D 4 2 用秦九韶算法计算多项式 在时的值时 的值为 65432 3567983512 xxxxxxxf 4 x 3 V A 845 B 220 C 57