枚举法的程序实现及优化

枚举法的程序实现及优化本部分内容是教育科学出版社出版的必修1《数据与计算》第四单元第一节中的内容，整本书的思路是初始数据与计算、编程计算、认识数据、计算与问题解决、数据分析与人工智能，第四章属于比较重要的一章，主要介绍算法的概念和特征、算法的实现以及怎样通过算法来解决现实中的问题。枚举法作为最重要的算法之一，在现实生活中也经常用它来解决问题，所以笔者把它挑出来用一节课的时间来讲。本节知识需要用两课时，第一课时主要讲解算法及其特征，第二课时主要讲解枚举法的程序实现及其优化，本节课是该节的第二课时。本节课的教学对象是高一的学生，他们在前面的学习中已经学习过Python语言，对该语言的基本语法以及程序的基本结构都有一定的了解，所以本节课中枚举法的实现部分将使用Python语言。了解枚举法的概念;掌握枚举法的特征;枚举法的程序实现;对枚举法进行优化。引导学生对提出的问题进行分析，探讨问题的解决方案，设计出解决问题的算法并使用程序设计语言来实现此算法，最终解决问题。解决之后继续思考是否有更好的解决方案，能否对算法进行优化，从而更高效地解决问题。通过本课学习，对学生的核心素养，特别是信息意识和计算思维的提高都有一定的促进作用。重点：枚举法的特征、枚举法的程序实现。难点：枚举法的程序实现、枚举法的优化。多媒体计算机教室、广播教学软件、投影仪、教学幻灯片、Python軟件。本节课主要采用信息技术网络教学平台支持下的教学模式，即在教师教学引导下，学生通过任务驱动实现自主学习的教学方法。教学流程为：提出问题→学生探讨解决问题的方法→引出枚举法的概念和特征→怎样用Python来实现枚举法→是否能让我们的程序更加高效→枚举法的优化。1.新课导入（3分钟）提出问题：有一类四位数，如3025，分为30和25两个两位数，这两个数之和的平方正好等于该数本身，即（30+25）2=552=3025，求所有符合这一特征的四位数。请同学们尝试解决这个问题，并告诉老师你的思路是怎样的。设计意图：提出实际问题并让学生自己去解决，引出今天要讲的内容;让学生使用不同的方法，为后面的优化埋下伏笔;最后让学生自己动手，让学生理解得更深刻。2.引出枚举法的概念（3分钟）教师引出枚举法的概念：一一列举所有可能的答案，合适就保留，不合适就丢弃（也就是我们日常生活中通常所说的一个一个去试）。要求学生列举出日常生活中可能用到或见到的枚举法，如密码锁忘记密码了;公安机关破案时先锁定几个嫌疑人，一个一个验证指纹，最后抓到犯罪嫌疑人。设计意图：不管学生有没有解决这个问题，他们的方法都是一个一个去试是否满足条件，这样就可以引出枚举法的概念。3.引导学生归纳总结出枚举法的特征（2分钟）归纳总结：观察以上例子，它们有什么共同点？明确：①有枚举范围;②有一定的验证条件。设计意图：在教师的引导下，学生根据前面的例子归纳出枚举法的特征。4.枚举算法的程序实现（4分钟）教师讲解枚举算法实现的三部曲：（1）确定枚举对象、枚举范围和判定条件。这个数i的范围为1000到9999，判定条件为前两位数x和后两位数y和的平方等于这个数。（2）枚举可能的解（使用循环结构）。foriinrange（1000，9999）：（3）验证是不是问题的解（使用选择结构）。If（x+y）2=i：pirnt（i）设计意图：将枚举法的实现分成三步来实现，让学生更容易理解枚举法，也更好去实现。5.课堂活动：实践与尝试（15分钟）实践一：按照上面讲解的枚举法实现的三部曲，写出以下两道习题的三部曲。题1：班里要举行班级聚会，要用600元班会费为50名同学准备50份礼品进行抽奖。选定了公仔（20元/个）、水杯（15元/个）和笔筒（10元/个）三类商品。要求刚好用完600元买50件礼品（每种礼品至少一件），这三种礼品的数量可以如何搭配？（提示：假设这三种物品的数量分别为x、y、z，它们的范围是多少？）题2：这次面试的冠军在A、B、C、D四位同学中产生。A说：“不是我。”B说：“是C。”C说：“是D。”D说：“C说的不对。”已知四人中有一人说了假话。你能判断出到底谁是冠军吗？（提示：可以将A、B、C、D看成1、2、3、4）实践二：使用Python软件写出上面题1的完整程序。注意点：①提示学生写程序时注意缩进，Python对这个要求比较严格;②三种循环是怎样实现的（教师演示）;③学生完成之后教师使用广播软件转播学生的完成情况，将错得比较多的地方挑出来讲解，总结并评价一些学生的程序。完整程序如下：forxinrange（1，50）：foryinrange（1，50）：forzinrange（1，50）：if（x+y+z==50）and（x*20+y*15+z*10==600）：print（x，y，z）设计意图：这两道习题主要用来训练学生怎样用程序来实现枚举法，第一道题难点在于确定枚举对象和范围，有一个三重循环，第二道题难点在于判断条件，怎样将现实中说的话转换为计算机里的if语句。6.交流评价，优化枚举（10分钟）提出问题：枚举法是一种比较耗时的方法，能不能克服这个缺点呢？有的时候我们可以通过优化来解决这个问题，让计算量减少，最常用的方法就是减少枚举的范围。同学们能不能通过优化使上面的题1的枚举范围减小呢？相邻的同学比一比，看谁优化得好，让循环的次数最少。优化前后本题循环次数分别是多少？同时思考，本节课开始的问题能不能优化呢？怎么优化？设计意图：通过枚举优化及优化前后枚举次数的比较，培养学生优化程序的思想;交流优化方案，引导学生自我反思，加深对所学知识的认识和理解，从而得到思想与方法的提升。7.总结与拓展（3分钟）回顾和总结本课所学的知识：枚举法的概念、枚举法的特征、枚举法的程序实现、枚举法的优化。枚举法是日常生活中经常用到的一种算法，是在没有其他更好的方法情况下所使用的容易理解的算法，它的缺点是所耗费的时间