第九讲算法实例-枚举算法

信息技术备课组 算法实例 教案 算法实例算法实例 枚举算法枚举算法 课课 题 题 算法实例 两课时 教学目的 教学目的 复习算法的三种结构 掌握枚举算法的特征 学会使用枚举算法来解决日常生活中的问题 教学重点 难点 教学重点 难点 枚举算法的引入 教学方法 教学方法 讲授 启发 讨论相结合 练习法 教学媒体 教学媒体 多媒体演示 教学过程 教学过程 教学引言 教学引言 这是今天的课程内容的第二个内容 我们已经学过了算法的三种结构 我们学过了三种结构 顺序结构 选择结构 循环结构 我们在日常生活中可以用这三种算法结 构来解决任何实际问题 但是在日常生活中 需要解决的问题多种多样 我们也不可能有一种统 一的方法来解决所有的问题 为了解决各种各样的问题 我们必须学习各种各样的算法设计技巧 也就是所谓的算法的实例 今天我们就要学习算法实例当中的一种算法 枚举算法 那么请同学们思考两个问题 1 什么是枚举算法 2 枚举算法有什么特点 3 引入今天的课题 引入两个生活中的实例 在一串钥匙中找到所有能开启某扇门锁的钥匙 情景设置 教师给学生展示一串钥匙 并说这些钥匙一共有 10 把 并且每把钥匙都一模一样 我 不知道这 10 把钥匙中有几把能够打开这把锁 询问学生 你可以用什么样的方法在最短的时间内找到所有能开启某扇门锁的钥匙呢 方法 把 所有的钥匙都去试一遍 直到找到能够开门的那一把钥匙 学生回答 把一把把钥匙去试 学生一边说 教师一边演示 看看第一把钥匙能够打开锁吗 如 果不能打开锁的话 就接着试下一把 找到了能够打开门锁的那一把 就把它取下来 再接着找 下一把钥匙 那么剩下的钥匙还要不要再找下去 我们用流程图怎么来表示这个算法呢 分析 我们要从第几把钥匙开始找 学生回答 第一把 然后一共要找几次 找 10 次 那我们是 不是要用一个循环结构来解决这个问题 同时要用到计数器 i 吧 i 的初始值应该是几 1 从第 几把钥匙开始找 从第一把开始找 然后要找几次 循环条件是什么 i 10 我可以给这串钥匙 编个号吧 第一把钥匙就是 1 号 然后第二把钥匙就是二号 那么我就可以用计数器来表示这些 钥匙了吧 然后我一把一把钥匙开始试能否打开这把锁 那么我在循环体里做些什么事情呢 是 不是要判断一下这把钥匙能够打开这把锁吗 那我在这个循环结构里是不是要嵌套一个选择结构 判断条件应该怎么写 这把钥匙是这个锁的钥匙吗 如果不能打开 我就继续尝试下一把钥 匙 教师演示 如果能够开的话 我就把这把钥匙取下来 同时记录这把钥匙的编号 然后再继 续找下一把钥匙 直到 10 把钥匙都找好为止 在黑板上画出流程图 同时请学生转换成伪代码在黑板上画出流程图 同时请学生转换成伪代码 问题 要不要把所有的钥匙都找一遍 找过的钥匙还要不要再找 问题 要不要把所有的钥匙都找一遍 找过的钥匙还要不要再找 那么刚才我们讲的这种算法是不是把找出所有能开锁的钥匙这个问题解决了呢 这种算法就是枚 举算法 请同学们概括一下什么是枚举算法 枚举算法有什么特点 提问学生 什么是枚举算法 枚举算法有什么特点 提问学生 什么是枚举算法 枚举算法有什么特点 信息技术备课组 算法实例 教案 今天我们来讲算法中的枚举算法 当问题的所有可能解的个数不太多时 一一列举出该问题 所有可能的解 提问学生 像刚才这道找出所有能够开锁的钥匙的题 它的可能的解是什么 是 不是所有的 10 把钥匙都可能把这把锁打开 并在逐一列举的过程中把每个问题的解通过循环结 构代入到问题中进行检验 检验每个可能解是否是问题的真正解 如果是问题的真正解 就采纳 它 否则抛弃它 不重复 不遗漏 这类似于我们数学中的带入法 当一个问题用正常方法无法 求解时 可以把一些数字直接带入题目中进行检验从而求得答案 由此可见 枚举算法的一般结构是 循环结构中嵌套一个分支判断结构 其中循环结构用以实现 逐一列举问题每个可能的解 分支结构用于实现检验 检验每一个解是否是问题真正的解 当然 具体的检验条件和列举内容应该根据实际问题来进行设置 课堂练习 1 求 15 到 100 中 找出所有是 3 倍数的自然数 分析 要找出 15 到 100 中所有的 3 倍数 首先这个问题我是不是要用枚举算法来解 我先确定查 找的答案的范围 很明显是 15 到 100 假设用 a 来表示 1 到 1000 之内的所有自然数 那么这道题 我要用那么循环结构和枚举算法来做 循环结构的 4 个要素各是什么 1 初始化条件 a 15 我从几开始找 从 1 开始找 所以计数器的初始值应该是多少 2 循环条件 a 100 循环条件是什么 我从 15 找到几 找到 100 所以说查找的可能的答案的 范围是从 1 到 1000 的所有自然数 循环体 把 15 到 1000 的所有自然数一个个带进去检验 把 15 代进去 15 是 3 的倍数吗 是的 我输出 15 不是 下一个数应该是几 用 a 怎么表示下一个数 16 是 a 是 3 的倍数吗 不是 如果 a 是 3 的倍数 选择结构内这个检验条件应该怎么写 就输出 a 然后下一个数怎么表示 a a 1 在数学运算中 怎样才能判断一个数是否是 3 的倍数 如果这个数除以 3 的余数是 0 的 话 那么就说明这个数是偶数 那么这个数 a 除以 3 的取它的余数是否为 0 怎么用数学表达式来进 行表示呢 2 看流程图说出流程图的功能 解法提示 1 首先判断是不是枚举算法 然后查看枚举变量所列举的可能的解的范围是多少 这里变量 a 是代表所有可能的答案 也就是枚举变量 2 看看在什么样的情况下 答案是符合题目要求的解 这里的判断条件是 a mod 2 0 表示什么意 思 也就是当变量 a 所列举的范围内的每一个整数除以 2 的余数是 0 的时候就输出该数 那这样的 数应该是什么数呢 3 八位数 5090637 的 1 个数字模糊不清 但是知道该八位数能被 7 整除 找出所有满足条件的 八位数 题目分析 提示学生 空余的个位数上的数字的取值范围是 0 9 然后这个八位数 n 的最小值是 50906370 可能值是 50906370 50906371 50906379 那么这个取值范围我用一个变量 a 来表示 a 就 表示 0 9 这样一组数 想一想 初始化 a 的值是多少 循环条件又是什么 这个八位数 n 的表达式 n 怎样用 a 来表示 50906370 a 再嵌套一个选择结构来进行判断 只要这个数能 够被 7 整除 这个判断的条件应该怎样写 就把这个数输出 然后继续寻找下一个数 请学生请学生 上来画出流程图 并写出伪代码上来画出流程图 并写出伪代码 在屏幕上逐步打出流程图 并进行讲解 思考 1 为什么 a 每次循环加 1 或减 1 改变 加 2 3 不行吗 因为枚举算法的特征是列举所有可能的 解 而 a 每次循环加 2 3 有可能会漏掉解 信息技术备课组 算法实例 教案 2 如果所有的数字都模糊不清呢 用枚举法会产生什么后果 可能会消耗非常多的时间去解决 问题 因为可能的解的数量太多了 枚举法的局限性是效率不高 是以消耗时间为代价来获得算 法的准确性和全面性的 所以当枚举的解的个数太多时不适合用枚举算法 为什么 当可能的解的个数非常多时是否还适用枚举法 枚举法注意点 适用情况 当问题可能的解的个数不是太多时才能适用枚举算法 采用枚举算法我们要注意两个问题 1 这个问题的它的答案的范围是多少 或者说列举的范围是多少到多少 那我们就可以用一个循 环结构来列举所有的解 2 是检验的条件是什么 我们利用这个检验的条件可以在列举的过程中把所有问题的可能的解代 入到这个条件里进行验算 也就是在循环结构中我再使用一个选择结构来对问题的所有的解进 行检验 是的 我就保留它 不是的 我就舍弃它 并继续寻找下一个可能的解 由此可见 枚举算法的一般结构是 循环结构中嵌套一个分支判断结构 其中循环结构用以实现 逐一列举问题每个可能的解 分支结构用于实现检验 检验每一个解是否是问题真正的解 当然 具体的检验条件和列举内容应该根据实际问题来进行设置 已知 3 6528 3 8256 等式中方框内的数字相同 求该数字 分析 用什么算法 算法用什么结构 列举的范围应该是多少到多少 0 9 检验条件是什么 当这个表达式成立的情况下 输出 i 那这个程序应该怎么写 3 课堂练习 输出 100 200 之间能被 3 整除 或者能被 7 整除的所有整数 作业分析 这一次的作业情况并不是太好 得优的同学不是很多 我们来看一下这一次的作业题 1 要找出所有能在 100 200 之间能被 3 整除又能被 7 整除的所有整数 首先首先这个问题我是 不是要用枚举算法来解 先确定查找答案的范围 非常显然是 100 200 假设这个范围内的所 有整数我用 i 来表示 那么 i 的初始值是什么 从几开始找 i 100 有的同学初始值写 i 0 对不对 一直找到几为止 200 所以循环条件是什么 i 100 and i 200 有没有必要 没有 因为 的初始值已经是 100 了 它会不会从比 100 小的数开始找 不会的 在明确了查找范围之后 循环体内的检验条件是什么 能被 3 整除或者被 7 整除 用数 学表达式怎么来表示 I mod 3 0 or I mod 7 0 如果符合检验的条件 我就输出这个数 100 符