第14课 枚举算法 课件(25张PPT)+教案

中小学教育资源及组卷应用平台 浙教版信息技术八年级第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)pr ... ...