高中数学 1.3 算法案例教案 新人教A版必修3

用心 爱心 专心 1 31 3 算法案例算法案例 第一 二课时第一 二课时 辗转相除法与更相减损术辗转相除法与更相减损术 1 1 教学目标 教学目标 a 知识与技能 1 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进行算法分析 2 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序 b 过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式 的方法 比较它们在算法上的区别 并从程序的学习中体会数学的严谨 领会数学算法计 算机处理的结合方式 初步掌握把数学算法转化成计算机语言的一般步骤 c 情态与价值 1 通过阅读中国古代数学中的算法案例 体会中国古代数学对世界数学发展的贡献 2 在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力 在利用 算法解决数学问题的过程中培养理性的精神和动手实践的能力 2 2 教学重难点 教学重难点 重点 理解辗转相除法与更相减损术求最大公约数的方法 难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 3 3 学法与教学用具 学法与教学用具 学法 在理解最大公约数的基础上去发现辗转相除法与更相减损术中的数学规律 并 能模仿已经学过的程序框图与算法语句设计出辗转相除法与更相减损术的程序框图与算法 程序 教学用具 电脑 计算器 图形计算器 4 4 教学设想 教学设想 一 创设情景 揭示课题 1 教师首先提出问题 在初中 我们已经学过求最大公约数的知识 你能求出 18 与 30 的公约数吗 2 接着教师进一步提出问题 我们都是利用找公约数的方法来求最大公约数 如果公 约数比较大而且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公 约数 比如求 8251 与 6105 的最大公约数 这就是我们这一堂课所要探讨的内容 二 研探新知 1 辗转相除法 例 1 求两个正数 8251 和 6105 的最大公约数 分析 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即为所求的最大公约数 练习 利用辗转相除法求两数 4081 与 20723 的最大公约数 答案 53 2 更相减损术 我国早期也有解决求最大公约数问题的算法 就是更相减损术 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 翻译出来为 第一步 任意给出两个正数 判断它们是否都是偶数 若是 用 2 约简 若不是 执 行第二步 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小 数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 例 2 用更相减损术求 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 练习 用更相减损术求两个正数 84 与 72 的最大公约数 答案 12 3 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为 主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数 的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为 0 则得到 而更相减 损术则以减数与差相等而得到 4 辗转相除法与更相减损术计算的程序框图及程序 利用辗转相除法与更相减损术的计算算法 我们可以设计出程序框图以及 BSAIC 程序 来在计算机上实现辗转相除法与更相减损术求最大公约数 下面由同学们设计相应框图并 相互之间检查框图与程序的正确性 并在计算机上验证自己的结果 1 辗转相除法的程序框图及程序 程序框图 用心 爱心 专心 输入两个正 整数m n m n r m MOD n r 0 m n n r 结束 开始 x n n m m x 输出n 否 是 否 是 程序 INPUT m m INPUT n n IF m n THEN x m m n n x END IF r m MOD n WHILE r0 r m MOD n m n n r WEND PRINT m END 5 课堂练习 一 用辗转相除法求下列各组数的最大公约数 并在自己编写的 BASIC 程序中验证 用心 爱心 专心 1 225 135 2 98 196 3 72 168 4 153 119 二 思考 用求质因数的方法可否求上述 4 组数的最大公约数 可否利用求质因数的算 法设计出程序框图及程序 若能 在电脑上测试自己的程序 若不能说明无法实现的理由 三 思考 利用辗转相除法是否可以求两数的最大公倍数 试设计程序框图并转换成 程序在 BASIC 中实现 6 小结 辗转相除法与更相减损术求最大公约数的计算方法及完整算法程序的编写 5 5 评价设计 评价设计 作业 P38 A 1 B 2 补充 设计更相减损术求最大公约数的程序框图 第三 四课时第三 四课时 秦九韶算法与排序秦九韶算法与排序 1 1 教学目标 教学目标 a 知识与技能 1 了解秦九韶算法的计算过程 并理解利用秦九韶算法可以减少计算次数提高计算效 率的实质 2 掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序 进而能设计 冒泡排序法的程序框图及程序 理解数学算法与计算机算法的区别 理解计算机对数学的 辅助作用 b 过程与方法 模仿秦九韶计算方法 体会古人计算构思的巧妙 能根据排序法中的直接插入排序法 与冒泡排序法的步骤 了解数学计算转换为计算机计算的途径 从而探究计算机算法与数 学算法的区别 体会计算机对数学学习的辅助作用 c 情态与价值 通过对秦九韶算法的学习 了解中国古代数学家对数学的贡献 充分认识到我国文化 历史的悠久 通过对排序法的学习 领会数学计算与计算机计算的区别 充分认识信息技 术对数学的促进 2 2 教学重难点 教学重难点 重点 1 秦九韶算法的特点 2 两种排序法的排序步骤及计算机程序设计 难点 1 秦九韶算法的先进性理解 2 排序法的计算机程序设计 3 3 学法与教学用具 学法与教学用具 学法 1 探究秦九韶算法对比一般计算方法中计算次数的改变 体会科学的计算 2 模仿排序法中数字排序的步骤 理解计算机计算的一般步骤 领会数学计算在计算 机上实施的要求 教学用具 电脑 计算器 图形计算器 4 4 教学设想 教学设想 一 创设情景 揭示课题 我们已经学过了多项式的计算 下面我们计算一下多项式 1 2345 xxxxxxf当5 x时的值 并统计所做的计算的种类及计算次 数 用心 爱心 专心 根据我们的计算统计可以得出我们共需要 10 次乘法运算 5 次加法运算 我们把多项式变形为 1 1 1 1 2 xxxxxxf再统计一下计算当 5 x时的值时需要的计算次数 可以得出仅需 4 次乘法和 5 次加法运算即可得出结果 显然少了 6 次乘法运算 这种算法就叫秦九韶算法 二 研探新知 1 秦九韶计算多项式的方法 0121 012 3 1 2 01 3 2 2 1 1 01 2 2 1 1 aaxaxaxa axaxaxaxa axaxaxaxa axaxaxaxaxf nnn n n n n n n n n n n n n n n n n 例 1 已知一个 5 次多项式为8 07 16 25 325 2345 xxxxxxf 用秦九韶算法求这个多项式当5 x时的值 解 略 思考 1 例 1 计算时需要多少次乘法计算 多少次加法计算 2 在利用秦九韶算法计算 n 次多项式当 0 xx 时需要多少次乘法计算和多少次加 法计算 练习 利用秦九韶算法计算15 033 0 16 0 41 0 83 0 2345 xxxxxxf 当5 x时的值 并统计需要多少次乘法计算和多少次加法计算 例 2 设计利用秦九韶算法计算 5 次多项式 01 2 2 3 3 4 4 5 5 axaxaxaxaxaxf 当 0 xx 时的值的程序框图 解 程序框图如下 用心 爱心 专心 开始 输入f x 的系数 a1 a2 a3 a4 a5 输入x0 n 1 v a5 n 5 v v x0 a5 n n n 1 输出v 结束 是 否 练习 利用程序框图试编写 BASIC 程序并在计算机上测试自己的程序 2 排序 在信息技术课中我们学习过电子表格 电子表格对分数的排序非常简单 那么电子计算 机是怎么对数据进行排序的呢 阅读课本 P30 P31 面的内容 回答下面的问题 1 排序法中的直接插入排序法与冒泡排序法的步骤有什么区别 2 冒泡法排序中对 5 个数字进行排序最多需要多少趟 3 在冒泡法排序对 5 个数字进行排序的每一趟中需要比较大小几次 游戏 5 位同学每人拿一个数字牌在讲台上演示冒泡排序法对 5 个数据 4 11 7 9 6 排序 的过程 让学生通过观察叙述冒泡排序法的主要步骤 并结合步骤解决例 3 的问题 例 3 用冒泡排序法对数据 7 5 3 9 1 从小到大进行排序 解 P32 练习 写出用冒泡排序法对 5 个数据 4 11 7 9 6 排序的过程中每一趟排序的结果 例 4 设计冒泡排序法对 5 个数据进行排序的程序框图 解 程序框图如下 用心 爱心 专心 开始 输入a1 a2 a3 a4 a5 i 1 ai ai 1 x ai ai ai 1 ai 1 x i 5 r 5 输出 a1 a2 a3 a4 a5 结束 i i 1r r 1 r 1 否 否 是 否 是 是 思考 直接排序法的程序框图如何设计 可否把上述程序框图转化为程序 练习 用直接排序法对例 3 中的数据从小到大排序 3 小结 1 秦九韶算法计算多项式的值及程序设计 2 数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法 3 冒泡法排序的计算机程序框图设计 5 5 评价设计 评价设计 作业 P38 A 2 3 补充 设计程序框图对上述两组数进行排序 第五课时第五课时 进位制进位制 1 1 教学目标 教学目标 a 知识与技能 了解各种进位制与十进制之间转换的规律 会利用各种进位制与十进制之间的联系进 行各种进位制之间的转换 b 过程与方法 学习各种进位制转换成十进制的计算方法 研究十进制转换为各种进位制的除 k 去余 法 并理解其中的数学规律 用心 爱心 专心 c 情态与价值 领悟十进制 二进制的特点 了解计算机的电路与二进制的联系 进一步认识到计算 机与数学的联系 2 2 教学重难点 教学重难点 重点 各进位制表示数的方法及各进位制之间的转换 难点 除 k 去余法的理解以及各进位制之间转换的程序框图的设计 3 3 学法与教学用具 学法与教学用具 学法 在学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系 熟悉各种进位制表示数的方法 从而理解十进制转换为各种进位制的除 k 去余法 教学用具 电脑 计算器 图形计算器 4 4 教学设想 教学设想 一 创设情景 揭示课题 我们常见的数字都是十进制的 但是并不是生活中的每一种数字都是十进制的 比如时 间和角度的单位用六十进位制 电子计算机用的是二进制 那么什么是进位制 不同的进位制 之间又又什么联系呢 二 研探新知 进位制是一种记数方式 用有限的数字在不同的位置表示不同的数值 可使用数字符 号的个数称为基数 基数为 n 即可称 n 进位制 简称 n 进制 现在最常用的是十进制 通常使用 10 个阿拉伯数字 0 9 进行记数 对于任何一个数 我们可以用不同的进位制来表示 比如 十进数 57 可以用二进制 表示为 111001 也可以用八进制表示为 71 用十六进制表示为 39 它们所代表的数值都 是一样的 表示各种进位制数一般在数字右下脚加注来表示 如 111001 2 表示二进制数 34 5 表示 5 进制数 电子计算机一般都使用二进制 下面我们来进行二进制与十进制之间的转化 例 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 化为二进制数 解 根据二进制数满二进一的原则 可以用 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 2 这种算法叫做除 2 取余法 还可以用下面的除法算式表示 用心 爱心 专心 把上式中的各步所得的余数从下到上排列即可得到 89 1011001 2 上述方法也可以推广为把十进制化为 k 进制数的算法 这种算法成为除 k 取余法 当数字较小时 也可直接利用各进位制表示数的特点 都是以幂的形式来表示各位数字 比如 2 103表示千位数字是 2 所以可以直接求出各位数字 即把 89 转换为二进制数时 直接观察 得出 89 与 64 最接近故 89 64 1 25 同理 25 16 1 9 9 8 1 即 89 64 1 16 1 8 1 1 26 1 24 1 23 1 20 位数 6543210 数字 1011001 即 89 1011001 2 练习 1 把 73 转换为二进制数 2 利用除 k 取余法把 89 转换为 5 进制数 把 k 进制数 a 共有 n 位 转换为十进制数 b 的过程可以利用计算机程序来实现 语句为 INPUT a k n i 1 b 0 WHILE i n t GET a i b b t k i 1 i i 1 WEND PRINT b END 练习 1 请根据上述程序画出程序框图 参考程序框图 89 44 22 11 5 2 1 2 2 2 2 2 2 2 0 余数 1 0 0 1 1 0 1 用心 爱心 专心 开始 结束 输入a k n i 1 b 0 t GET a i b b t k i 1 i n 输出b i i 1 是 否 2 设计一个算法 实现把 k 进制数 a 共有 n 位 转换为十进制数 b 的过程的程序中的 GET 函数的功能 输入一个正 5 位数 取出它的各位数字 并输出 小结 1 进位制的概念及表示方法 2 十进制与二进制之间转换的方法及计算机程序 5 5 评价设计 评价设计 作业 P38 A 4 补充 设计程序框图把一个八进制数 23456 转换成十进制数 用心 爱心 专心 算法初步算法初步 复习课复习课 1 1 教学目标 教学目标 a 知识与技能 1 明确算法的含义 熟悉算法的三种基本结构 顺序 条件和循环 以及基本的算法 语句 2 能熟练运用辗转相除法与更相减损术 秦九韶算法 排序 进位制等典型的算法知 识解决同类问题 b 过程与方法 在复习旧知识的过程中把知识系统化 通过模仿 操作 探索 经历设计程序框图表 达解决问题的过程 在具体问题的解决过程中进一步理解程序框图的三种基本逻辑结构 顺序 条件分支 循环 c 情态与价值 算法内容反映了时代的特点 同时也是中国数学课程内容的新特色 中国古代数学以 算法为主要特征 取得了举世公认的伟大成就 现代信息技术的发展使算法重新焕发了前 所未有的生机和活力 算法进入中学数学课程 既反映了时代的要求 也是中国古代数学 思想在一个新的层次上的复兴 也就成为了中国数学课程的一个新的特色 2 2 教学重难点 教学重难点 重点 算法的基本知识与算法对应的程序框图的设计 难点 与算法对应的程序框图的设计及算法程序的编写 3 3 学法与教学用具 学法与教学用具 学法 利用实例让学生体会基本的算法思想 提高逻辑思维能力 对比信息技术课程 中的程序语言的学习和程序设计 了解数学算法与信息技术上的区别 通过案例的运用 引导学生体会算法的核心是一般意义上的解决问题策略的具体化 面临一个问题时 在分 析 思考后获得了解决它的基本思路 解题策略 将这种思路具体化 条理化 用适当的 方式表达出来 画出程序框图 转化为程序语句 教学用具 电脑 计算器 图形计算器 4 4 教学设想 教学设想 一 本章的知识结构 算法 程 序 框 图 算 法 语 句 辗转相除法与更相减损术 排序 进位制 秦九韶算法 二 知识梳理 1 四种基本的程序框 用心 爱心 专心 终端框 起止框 输入 输出框 处理框 判断框 2 三种基本逻辑结构 顺序结构 条件结构 循环结构 3 基本算法语句 一 一 输入语句 单个变量 多个变量 INPUT 提示内容提示内容 变量 变量 INPUT 提示内容提示内容 1 提示内容 提示内容 2 提示内容 提示内容 3 变量 变量 1 变量 变量 2 变量 变量 3 用心 爱心 专心 二 二 输出语句 三 三 赋值语句 四 条件语句 四 条件语句 IF THEN ELSEIF THEN ELSE 格式格式 当计算机执行上述语句时 首先对 IF 后的条件进行判断 如果条件符合 就 执行 THEN 后的语句 1 否则执行 ELSE 后的语句 2 其对应的程序框图为 如上右 图 IF THENIF THEN 格式格式 计算机执行这种形式的条件语句时 也是首先对 IF 后的条件进行判断 如果条 件符合 就执行 THEN 后的语句 如果条件不符合 则直接结束该条件语句 转而执 行其他语句 其对应的程序框图为 如上右图 五 循环语句 五 循环语句 1 WHILE 语句 IF 条件 THEN 语句 1 ELSE 语句 2 END IF 满足条件 语句 1语句 2 是 否 IF 条件 THEN 语句 END IF 满足条件 语句 是 否 WHILE 条件 循环体 WEND 满足条件