浙教版信息技术八年级第 14 课枚举算法 教学设计 课题 学习 目标 枚举算法 单元 第三单元 学科 信息技术 年级 八年级 知识目标：理解枚举算法的思想，掌握枚举算法的步骤。 技能目标：初步掌握枚举算法的程序设计方法，提高分析问题、解决问题的能力。 情感目标：培养学生的创造性思维能力、探索精神，让学生体验成功的喜悦；。 重点 理解枚举算法的思想，掌握枚举算法的步骤。 难点 初步掌握枚举算法的程序设计方法，提高分析问题、解决问题的能力。 教学过程 教学环节 教师活动 导入新课 学生活动 设计意图 小明是一个数学迷，昨天他约了几个同学一起 到会议室里举行一个联谊会，可是粗心的小明去总 务处拿了一串钥匙回来准备开门时，却忘记了到底 哪一把才是会议室的钥匙。假设这串钥匙一共有 10 把。 问题： 怎样才能找到正确的钥匙来开门 ？ 找钥匙的过程 1.拿出第一把钥匙， 试验第一把钥匙能否开 门 2.拿出第二把钥匙， 试验第二把钥匙能否开 门； 3.拿出第三把钥匙， 试验第三把钥匙能否开 门； ······ 10.拿出第十把钥匙， 试验第十把钥匙能否开 门 枚举法 列举 检验 讲授新课 枚举算法就是按照问题本身的性质，一一列举 激发学生学习兴 思考并回答 问题 趣并快速进入学 习状态 出该问题所有可能的解，并根据问题的条件对 各 解进行逐个检验，从中挑选出符合条件的解， 通过教师的 通过小组合作， 弃不符合条件的解。 讲解，以小 加强学生组内团 一一列举；逐个检验 组合作的方 结、共同完成任 在很多时候，由于人类大脑的运算和处理能力 式，开展探 务 相对有限，立刻得出某个问题的可能解或最优解， 讨交流，完 如复杂密码的破解。 成任务。 舍 但是，人们可以利用计算机运算速度快和存储 容量大的特点，采用最原始的破解方法——枚举法。 一、枚举算法的思想和步骤 在日常生活中存在很多可以通过枚举算法来解 决的问题，例如，求解大面额纸币等值兑换成若干 张小面额纸币的方案。 枚举算法也称穷举法，基本思想是把问题所有 的可能解一一列举出来，并判断每一个列举出的可 能解是否为正确的解。 设计枚举算法时要在尽可能小的范围内罗列出 所有可能的情况，不能遗漏，也不能重复。 枚举算法的步骤： (1)确定枚举对象、范围和判定条件。 (2)逐一枚举可能的解，并验证每个解是否为 问题的解。 枚举法适合于解的候选者是有限、可枚举的场 合。 枚举法的算法一般都比较直观，容易理解。 但由于要检查所有的候选解，因此时间性能较 差。 二、枚举算法的流程图表示 通过教师的 加强学生组内团 讲解，以小 结、共同完成任 组合作的方 务 式，开展探 讨交流，完 成任务。 在枚举算法中，每列举出一个可能解，都需判 断该可能解是否为正确解 这个处理过程会重复执行直到判断完所有的可 能解，所以可采用循环结构来实现。 培锻炼学生的语 学生小组间 言组织能力和表 讨论，共同 达的能力。 完成任务。 而在利用问题提供的约束条件筛选、判断解的 过程中，则需要用到分支结构。 枚举算法的流程图如图所示。 三、枚举算法的程序实例 我国古代数学家张丘建在他的《算经》中提出 了著名的“百钱买百鸡”问题：鸡翁一，值钱五；鸡 母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问 翁、母、雏各几何? 1.问题分析 设公鸡有 x 只、母鸡有 y 只，小鸡有 z 只。 根据题意，若全部买公鸡，则最多可以买 100/5 只，因此 x 的取值范围为 0≤x≤20； 若全部买母鸡，则最多可以买 100/3 只，因此 y 的取值范围为 0≤y≤33； 若全部买小鸡，则最多可以买 100×3 只，但鸡 总共只有 100 只，因此 z 的取值范围为 0≤z≤100. 2.设计算法 利用枚举法解决该问题。 枚举对象为公鸡、母鸡和小鸡的只数，分别设 公鸡 x 只，母鸡 y 只，小鸡 z 只。 枚举范围为 0≤x≤20、0≤y≤33、0≤z≤100。 判定条件为： x+y+z=100 5x+3y+ z=100 加强学生组内团 通过教师的 结、共同完成任 讲解，以小 务 组合作的方 式，开展探 讨交流，完 成任务。 继 续 化 简 ， 判 断 条 件 为 ： 5x+3y+ (100-x培锻炼学生的语 y)=100。 其枚举算法用流程图表示，如图所示。 3.编写程序 根据算法设计，其程序代码如下： 学生小组间 言组织能力和表 讨论，共同 达的能力。 完成任务。 count = 0 #循环计数 For x in range(21) ： for y in range(34) ： count =count+ 1 if 5*x+3*y+(100-―x-y)/3==100： print("公鸡："， x， "母鸡："， y， "小鸡："， 100-x-y) print("循环运行次数："， count) 4.调试运行 按“F5”键调试运行程序，其运行结果如图所示。 枚举算法在程序实现时，要明确下列三要素 （1）“循环(枚举解)” 培锻炼学生的语 （2）“条件判断(筛选解)” 学生小组间 言组织能力和表 （3)“求解形式(输出解的内容或统计解的个 讨论，共同 达的能力。 完成任务。 数)” 算一算： 用 10 元和 50 元两种纸币组成 240 元，共有几 种组合方式？ （0 张 50 元）24 张 10 元 （1 张 50 元）19 张 10 元 （2 张 50 元）14 张 10 元 （3 张 50 元） 9 张 10 元 （4 张 50 元） 4 张 10 元 随堂练习 一张单据上有一个 5 位数的编号，千位数是 1，百位数是 7，个位数是 8，万位数和十位数已经 模糊不清，只知道该 5 位数是 7 或 11 的倍数，找 加强学生组内团 出所有满足这些条件的 5 位数并输出。 NO. ? 17 ? 8 通过教师的 结、共同完成任 提示： 讲解，以小 务 该题要列举的对象有两个，分别是万位数和个 组合作的方 位数。 式，开展探 讨交流，完 成任务。 加强学生组内团 通过教师的 结、共同完成任 讲解，以小 务 组合作的方 式，开展探 讨交流，完 成任务。 培锻炼学生的语 言组织能力和表 学生小组间 达的能力。 讨论，共同 完成任务。 培养学生独立完 成练习的能力。 学生小组间 讨论，共同 完成任务， 并分组汇报。 课堂小结 分小组总结归纳，教师补充。 各组汇报总 锻炼学生的总结 结，其他小 能力，逻辑思维、 组成员做补 语言表达能力。 充。 布置作业 在联欢会上，小明提议大家来玩数 7 的游戏。 游戏规则：从 1 开始数起，每个人数一个数，凡 是遇到 7 的倍数就要喊“过”,这样一直数到 100 为止。 帮小明找出 1——100 所有要喊“过”的数 板书 一、枚举算法的思想和步骤 二、枚举算法的流程图表示 三、枚举算法的程序实例