《4.2 枚举算法的程序实现1.docx》由会员分享，可在线阅读，更多相关《4.2 枚举算法的程序实现1.docx（6页珍藏版）》请在金锄头文库上搜索。
1、4.2枚举算法的程序实现分享人 江苏省丹阳高级中学 吴福舟一、教学目标1.知识与技能了解穷举法的基本概念及用穷举法设计算法的基本过程。分析建立正确的数学模型，归纳穷举法穷举技巧。能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。2.过程与方法经历用穷举法求解问题的基本过程。能通过实际问题的分析、求解过程，尝试归纳出利用穷举法解决问题的思路和方法。体验穷举策略在穷举法中的地位和作用，并选择适当的穷举方案解决问题。3.情感态度与价值观引导学生关注穷举法在社会生活中的应用，进一步提高利用信息技术解决实际问题的能力。通过小组讨论与探究活动，提高团队合作能力，促进探究的热情。在解决问题的过程
2、中进一步培养和提升学生的逻辑思维能力。二、学情分析本节内容的教学对象是高一年级学生，他们已经具备了一定的逻辑思维、分析问题、表达思想等能力。同时，通过前几个章节的学习与实践，学生已经历了用计算机解决问题的过程与步骤，学会了对计算机程序进行调试，并掌握了顺序、循环、条件三种程序结构，为本节内容的学习提供了良好的基础。前一节的学习，学生掌握了如何用解析法设计程序，但现实生活中也有很多问题往往无法用解析法找到答案，这时就需要使用计算机来帮助我们逐个列举出可能的情况，从而引出本课内容 “穷举法”。三、教材分析1.本节主要内容介绍枚举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。
3、它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。用枚举算法解决问题，通常可以从以下两个方面进行分析：确定范围：问题所涉及的情况有哪些，情况的种数可不可以确定。验证条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。只要把这两个方面分析好了，问题自然会迎刃而解。2.重点难点分析教学重点：建立正确的数学模型，确定枚举方案。根据题目确定枚举范围。正确表达“符合条件”的判断即验证条件。教学难点：如何评价各种枚举策略的优劣。算法的程序实现。课时安排：1课时。四、教学理念采用了以学生的学习和发展为中心，基于建构主义理论的任务驱动、情
4、境教学、游戏教学等教学方法，突出自主、合作、探究等学习方法；强调信息技术与生活实际的联系，培养学生的逻辑思维能力、解决问题的能力以及创新意识等；设置多元化的评价方式，让学生掌握学习内容的同时，形成交流与评价的能力。主要教学方法：讲授法、演示法、任务驱动、情境教学等主要学习方法：小组协作 自主探究五、教学策略在教学过程中，主要围绕“情境导入回顾算法思想任务引领合作探究交流评价总结拓展”这么一条主线索来开展教学活动。六、教学环境多媒体网络教室 投影仪 多媒体课件七、教学过程教学环节教师活动学生活动设计理念情境导入1.课前思考：陈婷有一个EMAIL邮箱的密码是一个5位数。但因为有一段比较长的日子没有
5、打开这个邮箱了，陈婷把这个密码给忘了。不过陈婷自己是8月1日出生，而她妈妈的生日则是9月1日，她特别喜欢把同时是81和91的倍数用作密码。陈婷还记得这个密码的中间一位(百位数)是1。你能设计一个程序帮她找回这个密码吗？2.学生探究分析，引出枚举算法概念。1.通过课前思考，初步体验枚举算法在现实生活中的应用。2.参与游戏，积极思考，在游戏过程中体会枚举算法的基本思路。1.贴近生活，将知识点巧妙地融入到算法应用游戏当中，寓教于乐，学生感到亲切，教学效果更佳。2.让学生亲自参与到游戏中去，更好地激发学生的学习兴趣，促使学生积极思考，更有利于对枚举算法的理解。枚举算法概念介绍枚举算法的基本思想：根据问
6、题本身的性质，一一列举出该问题所有可能解的情况，并根据问题的条件逐个作出判断，从中挑选出符合条件的解。回忆刚刚破解密码过程概括枚举算法的基本思想分析问题：用数学语言描述问题，叫做建立数学模型。在解决实际问题时，一般都需要为这个问题建立数学模型。本问题的数学模型是：求出一个5位数，它的百位是1，而且它能同时被81和91整除。以组为单位，思考并提出解决方案，教师引导学生从两方面讨论方案：（1）准备让程序一一列举数的范围（2）上面的多个数用什么条件进行筛选方案解析（师生共同进行问题分析、绘制流程图、编写代码解决问题）学生活动：1.回顾解决问题过程归纳枚举算法解决问题的分析要点：确定范围；验证条件2.
7、观察两段程序代码，归纳枚举算法程序控制结构：范围枚举循环结构；验证条件选择结构3.比较前面两个枚举方案的效率1.由于枚举算法在理解上并不十分困难，再加上学生在学习之前已经具备相当的基础。因此，在解决问题的过程中，遵循“学生为主体，教师为主导”的教学原则。2.解决这个问题不太困难，难的是选择最优的枚举策略。因此在进行这一教学环节时，培养学生发现知识的规律、方法并把它运用到解决实际问题中去的能力，并初步形成严谨的逻辑思维习惯。3.培养学生合作探究能力和思维过程描述能力。4.设计一题多解的任务，方法有难有易，使不同层次的学生均学有所得。5.为了提高程序执行效率，可以对循环次数进行优化，即减少循环次数
8、。也就是说尽可能使可能解的罗列范围最小，但也不能遗漏任何一个真正解。让学生体验枚举策略在枚举法中的地位和作用，并恰当安排枚举的方式，使得算法的效率更高。枚举方案的设计及程序实现（任务引领，层推优化）设计算法A：因为这个密码有4位数字是未知的，把各位数字都对所有可能性演变一次(最高位是19，其余各位都是09)，就可以把可能的情况穷举完。再把各位数字合成一个5位数，判断是否同时被81和91整除就可以了。分别用a1、a2、a3、a4、a5表示这个5位数的各个数位(a3=1在程序中没出现)，在它们各自的范围中变化，然后组成5位数d，判断d能否同时被81和91整除即可得到结果。程序实现：For a1 =
9、 1 To 9For a2 = 0 To 9For a4 = 0 To 9For a5 = 0 To 9d = a1 * 10000 + a2 * 1000 + 1 * 100 + a4 * 10 + a5If (d Mod 81 = 0) And (d Mod 91 = 0) Then Print dNext a5Next a4next a2next a1设计算法B：知识点回顾：（1）“”：整除运算符，即求出整数商。表示要截取整数B的某些数位。（2）“mod”：求余数运算符，即求出余数。要保留整数的某些数位。算法实现：把方案A的方法反其道而行之。5位数字的范围是1000099999，在此范围
10、内穷举，并对每一个数分解出它的百位数字检验它是否1，再判断此5位数是否同时被81和91整除就可以了。程序实现：For a = 10000 To 99999b = a 100 Mod 10If b = 1 And a Mod 7371 = 0 Then Print 这个位的密码是：; aNext a设计算法C：算法实现：受方案B的启发，有解的范围只限于同时是81和91的倍数。81和91的最小公倍数是7371，所以我们只在5位数中就7371的倍数进行穷举，然后分离出它的百位数字判断是否是1就能得到答案。按这个算法首先需要知道5位的7371的倍数中哪个最小。亦即求最小的正整数P，使7371P1000
11、，这时P100007371。显然，取100007371的整数部分加1就是可用的P，即P = 10000 7371 + 1程序实现：p = 10000 7371 + 1For a = p * 7371 To 99999 Step 7371c = a 100 Mod 10If c = 1 Then Print 这个位的密码是：; aNext a任务引领合作探究任务 密码问题小明忘记了自己一个word文档的打开密码，只记得是一个4位数的数字密码65，但知道该数能够被69整除，也能被95整除。请你完善程序，帮他找出这个密码。1.作为驱动任务。每位同学先独立思考问题，然后两人一组，进行协作探究。学生通过
12、辅助学习平台协作学习。2.巡视学生学习情况，指导和帮助学生自主、协作学习。3.参与到小组学习中，与学生一起探讨。4.根据完成任务的实际情况，选择有代表性的两三名学生上台展示作品并自评。1.根据任务需求，进行问题分析与算法设计，并编写程序解决问题。2.与同组其他同学进行枚举方案的对比实验，体验枚举策略在解决问题中的地位和作用。3.在探究过程中表达思想，与同学、老师交流观点、经验。1.充分应用小组合作探究的学习方法，捕捉学生的灵感。2.在课堂上，通过师生之间，生生之间的协作、交流，培养学生的合作意识、互助精神、人际沟通能力。3.给学生展示自我的机会，引导学生在欣赏作品的同时，取长补短，共同进步。4
13、.通过问题拓展让学生思考多种实现方法，使学生在实践中认识算法优劣在解决问题中的意义。交流评价1.展示评价标准，引导学生参考评价表进行交流和评价。2.引导全体学生开展自我评价。3.对学生作品中的闪光点和有待改进的地方进行点评。（如：问题分析、枚举方案的选择、语言表达流畅等）1.根据作品评价表，学生展示作品，并进行自评。2.欣赏别人作品，发表自已见解。3.听取教师点评，取长补短。4.填写评价信息反馈表。1.通过评价，引导学生自我反思，加深对所学知识的认识与理解，学会评价各种枚举方案的优劣。归纳总结布置练习1.通过演示文稿总结本节知识内容。2.归纳同学们在解决问题过程中所遇到的难题。3.略述枚举算法
14、的局限性。4.布置课外作业。1.知识总结，系统归纳。2.回忆课堂学习过程，提高对枚举算法的认识，并将所学知识应用到解决实际问题中去。1.通过知识总结，帮助学生将知识系统化，便于学生理解记忆。2.通过知识的延伸，促使学生将知识内化，并进行能力迁移，进一步提高学生解决问题的能力。3.通过练习，使学生体验枚举算法在解决现实生活问题中的作用及意义。4.课后思考有利于拓展学生的枚举思路，锻炼学生分析问题、解决问题的能力。八、教学反思枚举算法是程序设计中最最基础的算法，是刚学习完赋值语句、选择语句和循环语句的一次综合应用。本课为学生设置了一个任务，层层推进优化实现方法，让学生在简单的解密过程中讨论归纳枚举算法的基本思想，同时让学生经历分析问题、确定算法、编程求解等计算机解决问题基本过程，让学生在提出各个枚举方案的探讨过程中领会枚举算法解题的分析要点、优化思想及枚举算法的适用范围。在学生在层层优化程序的过程中引发学生对枚举法解决问题的思考，实现学生回归现实、回归生活。附件：评价信息反馈表评价信息反馈表评价任务编写程序解决问题班级姓名您找到问题的正确答案了吗？是否如果您没有找到正确答案，原因在于以下哪些方面？分析问题有误； 算法设计错误；选择、循环语句没有学好；变量设置错误； 对枚举算法理解不够；调试程序失败；
