《枚举算法的程序实现》由会员分享,可在线阅读,更多相关《枚举算法的程序实现(7页珍藏版)》请在金锄头文库上搜索。
1、- - 1 - -课题课题: : 枚枚举举算法的程序算法的程序实现实现 授授课课教教师师:黄玉芬:黄玉芬 单单位:宁波二中位:宁波二中【 【教材分析教材分析】 】本课课程标准内容:(1)了解穷举法的基本概念及用穷举法设计算法的基本过程。(2)能够根据具体问题的要求,使用穷举法设计算法,编写程序求解问题本课的学科指导意见内容:基本要求:1.了解枚举算法思想 2.初步掌握枚举算法的实现 说明 例 2“包装问题”不作要求,教师可以换成较简单的例子,实践体验也不作要求。教材内容:5.1 枚举算法的程序实现 1 课时 枚举算法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。它利用计算机
2、运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。从课程标准和学科教学指导意见对本课教学内容的要求来看,要求学生能从具体问题的解决过程中体会枚举法设计算法的基本思路,并用程序实现。对于基础较好的同学,可以进一步介绍一些程序优化的措施,以提高程序的执行效率。【 【学情分析学情分析】 】学生在学习本课之前对算法与程序设计已经经过一段时间学习,应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环语句的基本用法和 VB 基本操作,理解对象、事件驱动等基本概念及数据类型和表达式的构成。本课的学习对象是省一级重点中学的学生,基础较好,具备一定的逻辑
3、思维能力。本节内容采用的学习例子对他们而言在理解上并不是十分困难的事情,所以弱化了学生对算法流程图的描述(不是本课学习重点,教师根据学生分析直接给出),主要在于引导学生归纳用枚举算法解决问题的分析入手点和评价枚举算法的优劣。【 【教学目教学目标标】 】1 知识与技能了解枚举算法基本概念并理解用枚举法设计程序的基本思路。分析建立正确的数学模型,归纳枚举技巧(变量的设置、枚举方案的确定)。探讨枚举法的技术方法与技术思想。2、过程与方法经历用枚举法求解问题的基本过程。- - 2 - -在学习过程中,学习发现知识的规律和方法并把它运用到解决实际问题中去。体验枚举策略在枚举法中的地位和作用,并选择适当的
4、枚举方案解决问题。3、情感态度与价值观引导学生关注枚举法的应用,激发学生学习的热情。学会评价各种枚举方案的优劣,并形成反思的意识。初步了解枚举法在破解密码方面的现实应用,自觉养成保护密码的良好习惯。了解信息技术可能带来的不安全因素,养成健康使用信息技术的习惯。【教学重点与教学重点与难难点点】 】教学重点:建立正确的数学模型,确定枚举方案。根据命题确定变量的取值范围。正确表达“符合条件”的判断。教学难点:恰当安排枚举的方式,使得算法的效率更高。【教学方法与教学手段教学方法与教学手段】 】以培养学生的信息素养为前提,遵循“学生是学习的主体,教师是学习的指导者”的新课程教学理念,采用了“主题任务”的
5、教学模式,通过任务驱动法,使学生在任务情境中学习,在实践中探究,在探究中总结归纳知识规律和方法,加强知识的实际应用。教学主线:情境导入任务引领提出枚举算法的基本思想提出枚举方案并实践解决问题归纳归纳枚举算法分析要点和程序控制结构的实现枚举算法应用于现实生活学习线索:分析问题实际解决问题归纳提升【教学教学过过程程】 】一、新课导入(1)情境:某某小学准备一个星期后举行了“春日雏鹰飞”大型校园游园活动,二年级的多多小朋友为了提早做一些针对性,在学校网站上下载了游园活动项目规则.rar,但是遇到了密码。老师给他发来了密码指南,但是以他现在的能力无法打开,求助高中生的你。(2)密码指南:一位奇自然数学
6、生活动:解密讨论:你是如何解开这个密码?(描述思维过程)- - 3 - -教师引导:其实其实大家在一个一个尝试去破解这个密码的过程中包含了一个经典的算法枚枚举举算法算法设计意图:该例子十分常见和简单,让学生体会到算法并不抽象,有亲切感。二、新课教学教学步骤一、枚举算法的基本思想(1)学生活动:回忆刚刚破解密码过程概括枚举算法的基本思想枚枚举举算法的基本思想是根据算法的基本思想是根据问题问题本身的性本身的性质质,一一列,一一列举举出出该问题该问题所有可能解的情况,并根所有可能解的情况,并根据据问题问题的条件逐个作出判断,从中挑的条件逐个作出判断,从中挑选选出符合条件的解。出符合条件的解。(2)思
7、维发散:如果这个密码是 24 位数?设计意图:引发学生思考生活中的例子用计算机编程解决的必要性。教学步骤二、枚举方案的设计及程序实现(1)情境:多多顺利打开了 winrar 软件,查看了活动项目和游戏规则,其中一个项目是校园寻宝,重要级的。他准备先打印一份藏宝图。可以又遇到了密码。老师又给了他发了一份密码指南。密码指南:这个密码由所有满足以下条件的数从小到大排列构成。条件:3 位整数,满足被3 除余 2,被 5 除余 3,被 7 除余 2,并且这个数的中间一位(十位数)是 4。(2)学生活动:以组为单位,思考并提出解决方案教师引导学生从两方面讨论方案:(1)准备让程序一一列举数的范围(2)上面
8、的多个数用什么条件进行筛选设计意图:培养学生合作探究能力和思维过程描述能力。(2)方案解析(师生共同进行问题分析、绘制流程图、编写代码解决问题)以下是估计学生可能出现的一些方案,视课堂生成情况而定。方案一解析 1、问题分析 确定范围:3 位数 100999验证条件:1、这个 3 位数的十位是 42、这个数是 3 除余 2,被 5 除余 3,被 7 除余 22、流程图开始结束n100nn1bn10 mod10输出nn=999?b=4 and n mod 3=2 and n mod 5=3 and n mod 7=2?YYNN开始结束n100nn1bn10 mod10输出nn=999?b=4 an
9、d n mod 3=2 and n mod 5=3 and n mod 7=2?YYNN- - 4 - -3、程序实现:补充代码,补充代表算法思想的关键语句。方案二解析1、问题分析3 位数 4 确定范围:i: 1-9j: 0-9验证条件:这个数是 3 除余 2,被 5 除余 3,被 7 除余 22 流程图3、程序实现:补充代码,补充代表算法思想的关键语句。IJDim n as integer,b as integer n 表示 3 位整数,b 表示十位上的数字 For n= _ to _ step_ B=n10 mod 10 从 3 位数 n 中分离出十位上的数If _ then print
10、”满足条件的数有”; n Next n开始结束i1ii1i=9?枚举i40i49 求满足除3余2余5 余3除7余2的数YN开始结束i1ii1i=9?枚举i40i49 求满足除3余2余5 余3除7余2的数开始结束i1ii1i=9?枚举i40i49 求满足除3余2余5 余3除7余2的数YNj0jj+1n100*i+40+j输出nj=9?n mod3=2 And n mod 5=3 And n mod 7=2?YNYNj0jj+1n100*i+40+j输出nj=9?n mod3=2 And n mod 5=3 And n mod 7=2?YNYNDim i as integer, j as inte
11、ger i 表示百位上的数字,j 表示个位上的数字 Dim n as integer n 表示三位整数 For i=_ to _ step_For j=_ to _ step _ N=100*i+40+jIf _ then print ”满足条件的数有”; nNext j Next i- - 5 - -(3)学生活动:回顾解决问题过程归纳枚枚举举算法解决算法解决问题问题的分析要点的分析要点1、确定范、确定范围围2、 、验证验证条件条件(4)学生活动:观察两段程序代码,归纳枚枚举举算法程序控制算法程序控制结结构构范范围围枚枚举举循循环结环结构构验证验证条件条件选择结选择结构构(5)学生活动:比较
12、前面两个枚举方案的效率教师引导总结:为了提高程序执行效率效率,可以对循环次数进行优优化化,即减少循环次数 。也就是也就是说说尽可能使可能解的尽可能使可能解的罗罗列范列范围围最小,但也不能最小,但也不能遗遗漏任何一个真正解。漏任何一个真正解。设计意图:让学生体验枚举策略在枚举法中的地位和作用,并恰当安排枚举的方式,使得算法的效率更高。教学步骤三:联系实际,归纳枚举算法优缺点(1)讨论:我们使用银行卡在 ATM 机上取钱时,为什么系统要限制输入密码的次数?(2)教师展示用 P4 3.0 处理器本地穷举密码的时间(3)师生讨论归纳枚举算法优缺点优优点:点:结结构构简单简单,容易,容易实现实现缺点:当
13、数据缺点:当数据规规模模较较大大时时, ,执执行效率低行效率低(4)讨论:结合本课知识点讨论如何让我们的密码更安全。设计意图:初步了解穷举法在破解密码方面的现实应用,自觉养成保护密码的良好习惯。了解信息技术可能带来的不安全因素,养成健康使用信息技术的习惯。教学步骤四、探探讨讨哪些哪些问题问题适用枚适用枚举举算法来解决算法来解决学生活动:思考以下问题能用枚举算法解决吗?1“百钱买百鸡问题”:公鸡每只 5 元,母鸡每只 3 元,小鸡 1 元 3 只,要求公鸡、母鸡、小鸡都要,问 100 元买 100 只鸡,公鸡、母鸡、小鸡各多少只?2求班级 50 个同学的平均身高3如果一个三位数等于它的每个数字的
14、立方和,则此数称为“水仙花数”,如153135333 故 153 是水仙花数。求 100999 之间的全部水仙花数4有一道写于纸上的数学题被雨水淋湿,其中有两个数字已模糊不清(342)647 你能找出这两个数吗? - - 6 - -归纳总结:枚举算法属于搜索策略搜索策略,适用于那些解变量的连续值值域确定域确定的问题设计意图:运用枚举算法基本思想解决问题,又从大量问题中提取归纳枚举算法适用情况,内化枚举算法。教学步骤五:总结提升(1)枚举算法的基本思想、要点等(2)枚举算法的现实应用【教学教学设计说设计说明明】 】设计思想:枚举算法是程序设计中最最基础的算法,是刚学习完赋值语句、选择语句和循环语
15、句的一次综合应用。本课采用情境引入、任务引导等方式让学生快速进入教学过程。为学生设置了两处密码门,第一道密码 1 位奇自然数,让学生在简单的解密过程中讨论归纳枚举算法的基本思想,简单而亲切;第二道密码难道提升,让学生体会到人工穷举的局限性,发挥计算解决问题的优势,领会学习编程的意义。同时让学生经历分析问题、确定算法、编程求解等计算机解决问题基本过程,让学生在提出各个枚举方案的探讨过程中领会枚举算法解题的分析要点、优化思想及枚举算法的适用范围。在学生一道一道寻找密码的过程中引发学生对枚举法在破解密码方面的现实思考,体会到信息技术可能带来的不安全因素,自觉养成保护密码的良好习惯。学习算法的目的最终是回归现实、回归生活,所以最后设置了枚举算法的现实应用。例子说明:学科指导意见提出 例 2“包装问题”不作要求,教师可以换成较简单的例子。经典问题“百钱买百鸡”、 “取纸币 24 元 10 张:5 元 2 元 1 元组合”与此问题类似,所以都没有采用。我选用的这个 3 位数字问题可以用一重循环来解,也可以采用两重循环来解。两重循环数字变量的连续性,更降低两重循环的难度。【个人个人简简介介】 】黄玉芬,女,中学一级教师。单位:宁波二中;联系电话:13336888217;e-mail:。希望与同行多交流