第3课 算法设计预设教学目标：1.了解算法思想的概念，能够对问题选择合适的算法思想。2.了解经典算法中分治法、贪心算法和枚举法的概念；3.能清楚枚举法的概念和过程，学会使用枚举法进行算法设计。预设教学重点与难点：用枚举法进行算法设计。预设教学课时：1课时预设教学准备： 课件、课本、学生练习学案等预设教学过程：一、课题导入【探索】1.上一节课我们学习了抽象与建模，知道了抓住问题的核心，理清关键要素之间的关系，有助于问题的解决。请你来看这道数学题。课件出示：破译字母算式解决这个问题主要的方法和步骤是怎么样的呢？算一算，写一写。学生思考并回答。课件出示表格。这个问题需要知道的目标是？（ABC）现在我们知道它们分别代表什么数字吗？（未知）那它们之间有没有关系呢？想一想列竖式计算中，它们之间会是什么关系呢？学生回答，课件出示。根据列出来的关系，是不是就能马上解决这个问题了？（出示结果）2.再看一道常见的计算24点游戏题，谁来说一说，你会怎么计算呢？学生回答。题目问有几种凑成24点的方法？怎么样才能把所有解法都找出来呢？就这需要我们通过算法来获取所有可能的答案。3.揭题：今天这节课我们就一起来学习第三课：算法设计。二、新知建构【各种经典算法】1.说到算法，经典算法有很多种，我们日常生活中就经常会用到。比如：要在手机联系人里找到某个人，通常情况下，你会怎么做？学生回答。是的，要是查找“王红”这个人，会先去找他姓“王”的首字母“w”，然后再查找“王红”这个人。这种方法就是分治法，简而言之就是分而治之，就是把一个复杂的问题分成两个或n个相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解就是子问题的解的合并。比如：我们在查英文字典时，要想查找单词zoo，会先找到字母“z”,再去查找单词“zoo”,利用首字母分类查找的算法就是分治法。2.贪心算法如果从30张面值不等的钞票中抽出10张，怎样才能获得最多的价值？每次都选择现下的钞票中面值最大的，最后拿到的就是最优解。这种算法就是贪心算法，做出当前的最优选择。就是通过局部的最优选择获得整体的最优选择。平时生活中找零钱用的就是贪心算法，比如50元钱买了三块钱的东西，我们一般会找两个20元的，一个5元的和一个2元的。3.经典的算法还有很多，比如解析法、枚举法、动态规划算法等。经过大量的实践，人们发现了算法某些共性的规律，总结了经典的算法思想。合理地选择经典算法思想，可以为具体问题的解决设计出更加精妙的算法。“鸡兔同笼”问题需要在一定范围内寻找正确解，可以使用枚举法。今天我们重点来学习枚举法。【认识枚举法】1. 在班级名单中查找符合条件的名字，通常我们会怎么做？是的，从第一个名字开始，一个一个往下找，这种做法就是有序地尝试每一种可能的解，这也是枚举法的思想。枚举法，有个近义词叫列举，就是把所有的可能一个一个罗列出来，如果满足正确解的条件就采纳，否则继续枚举，做到不遗漏、不重复。它在生活有着广泛的应用，如玩24点游戏时在头脑中罗列各种可能的算式；在一篇文章中摘录好词好句；做这样的数学题等等。2. 用一串没有标记的钥匙打开教室的门，通常你会怎么做？学生回答。如果让计算机通过枚举法，从一串钥匙中找到打开教室对应的那一把钥匙，我们需要告诉计算机什么信息它才能停止查找？（如果这把钥匙能打开教室门，就不用再往下尝试了。）就这是在告诉计算机正确解的判断条件，不然计算机怎么知道找到怎样一把钥匙才可以解决问题呀。除了这个关键，还要告诉计算机有几把钥匙，这样计算机就知道一共需要尝试几次了，不然一串钥匙试完了再试一遍，那就没完没了了。就这是在确定枚举的范围。确定枚举的范围和正确解的判断条件是使用枚举法的关键。3.同学们，你知道怎样用流程图来表示枚举法吗？首先需要给定一个范围，在范围内进行查找，如果符合条件就把这个数据输出，否则就继续往下找，直到找完范围内所有的数据就结束。请你试一试，用拖动的方式，将枚举法的流程图补充完整。学生练习。反馈结果。4.想一想我们认识了枚举法，知道了枚举法的基本思想和关键，那么请你想一想：为什么在登录网站、APP、ATM自动柜员机时，系统要限制用户输入密码的次数？学生回答。是的。为了保护财产安全，防止犯罪分子利用枚举法的思想破解密码。【算法框架的确定】1.在明确了枚举算法思想的基础上，使用具体的计算模型，在合理选择控制结构，就可以得到解决具体问题的算法框架，最终解决问题，找到答案。我们继续上一节的“鸡兔同笼”问题，这是上一节课我们最后建立的计算模型。其中ji和tu的取值范围是0-35，这就是枚举的范围；而ji+tu=35；ji2tu4=94就是正确答案的判断条件。判断对错，那就要用到如果那么，这是一种分支结构；枚举范围在0-35之间，就要重复尝试36次，从0开始，直到35结束，这就是循环结构。2.现在我们跟随着计算机来一起进行罗列，为了能看得更加清楚，我们用表格来进行罗列，出示表格。由于ji+tu是35，那么我们选择其中动物来进行罗列，比如罗列兔子的只数，从0开始，那么鸡的只数就是35减去兔子的只数。课件出示，学生边回答，边展示。【算法的描述】1. 算法的框架确定好后，我们再用流程图来描述算法。描述算法时，要精准地描述算法的每一步骤，明确算法的输入和输出。对于大部分算法来说，输入数据是必要的，但是有的算法不需要输入数据或者算法本身给定了初始条件。比如鸡兔同笼的问题，就可以把tu的值初始化为0，因为是从0开始罗列的。2.课件呈现“鸡兔同笼”问题的算法流程图。对照自然语言描述呈现流程图。3.除了枚举兔的数量，还可以枚举哪些数量呢？（鸡的数量）其实只要通过鸡兔同笼的数据关系，我们知道，只要知道鸡的数量，就能计算出其他的数量，所以除了可以枚举鸡的数量，或者兔的数量，鸡脚、兔脚的数量都能枚举，只不过枚举的范围和判断的条件可能会发生相应的变化。请你试一试，枚举鸡的数量，进行表格的罗列和流程图的描述。学生练习。三、课堂小结今天我们一起学习了算法设计，了解了一些经典的算法，比如分治法、贪心算法等，重点学习了枚举算法。1.枚举法的思想是 地尝试 的解。2.枚举法的关键是 。 。四、课后练习【机动安排】利用枚举法设计百钱买百鸡的算法，填写百钱百鸡的表格填写。