下载文档原格式
§4.2用穷举法设计程序一、教学目标课程标准规定本节内容主要在于穷举法与问题解决。
包括两个方面：1、理解穷举法的思路。
2、能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。
二、学情分析本节内容的教学对象是高一或高二年级学生，他们已经具备了一定的逻辑思维、分析问题、表达思想等能力。
同时，通过前三个章节的学习与实践，学生已初步体验了穷举法的基本思想，经历了用计算机解决问题的过程与步骤，学会了对计算机程序进行调试，掌握了程序的三种基本结构等基础知识，为本节内容的学习提供了良好的基础。
三、教材分析1、本节主要内容介绍穷举法是程序设计中使用得最为普遍、大家必须熟练掌握和正确运用的一种算法。
它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。
用穷举算法解决问题，通常可以从以下两个方面进行分析：⑴确定范围：问题所涉及的情况有哪些，情况的种数可不可以确定。
⑵验证条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案。
只要把这两个方面分析好了，问题自然会迎刃而解。
本节内容是广东教育出版社出版的普通高中信息技术（选修１）《算法与程序设计》教材第四章第２节的教学内容，包括有穷举法的基本思路，用穷举法求解问题，穷举法中穷举方案的选择等。
2、重点难点分析教学重点：⑴建立正确的数学模型，确定穷举方案。
⑵根据命题确定变量的取值范围。
⑶正确表达“符合条件”的判断。
教学难点：⑴恰当安排穷举的方式，使得算法的效率更高。
⑵如何评价各种穷举策略的优劣。
3、课时安排1课时。
四、教学环境多媒体网络教室、投影仪等。
五、教学过程六、学习评价在教学过程中，设置了学生自评、互评，教师点评等多种评价方式。
同时制订了评价信息反馈表，充分发挥了教学评价的作用。
2、对于多种解决问题的方案，学会评价它们的好坏。
教学重点和难点分析（一）教学重点：建立正确的数学模型，确定穷举方案；根据命题确定自变量的取值范围。
（二）教学难点：如何确定穷举方案并评价各种穷举方案的优劣。
教学过程教学环节教师活动学生活动设计意图案列引入1、WiFi密码这样设置，最容易被大家破解我们的网络除了一些企业，我们家里自用的wifi，由于大家的安全意识欠缺，密码设置的依然是简单粗暴。
这样的密码很容易被隔壁老王猜中或者被黑客破解！甚至遭到攻击！2、暴力穷举密码破解技术中最基本的就是暴力破解，也叫密码穷举。
如果黑客事先知道了账户号码，如邮件帐号、QQ用户帐号、网上银行账号等，而用户的密码又设置的十分简单，比如用简单的数字组合，黑客使用暴力破解工具很快就可以破解出密码来。
举例自己家里无线网的情况，有时也会出现卡顿或掉线，思考会不会是密码被破解了。
WIFI是现在娱乐生活工作离不开的工具，引起学生共鸣，提高学生对本节内容的学习兴趣并引起思考。
案列剖析1、密码破解小程序演示运行密码破解小程序，尝试手动破解密码、自动破解两位密码和自动破解三位密码这种功能小程序的应用，极大提高同学学习兴趣和积极性。
2、思考破解的原理引出穷举的概念思考为何能够破解，它的原理是什么体会穷举的执行过程3、小程序核心代码理解①For循环语句回顾：For 循环变量=初值to 终值Step 步长循环体Next 循环变量②2位和3密码破解代码分析带同学一起分析2位密码破解程序3位密码破解程序填空，请同学思考并回答回顾for循环语句的执行过程，理解2位密码程序结合2位密码破解程序，思考这段程序的代码考虑学生层次，这里有必要带同学再回顾一下for语句的执行过程，以便于小程序核心代码的理解通过思考，理解穷举范围的选取和穷举结束4、思考提高密码安全性①增加密码长度②增加密码复杂性填空思考如何让密码不容易破解条件的设置提高密码安全设置的意识和能力穷举法案例实战及提高1、现有面值为1元、2元和5元的钞票（假设各钞票的数量足够多），从这些钞票中取出30张使总面值为100元，问有多少种取法输出每种取法中各种面额钞票的张数。
《穷举法求解问题的实践》教学设计一、教材分析本节选自广东教育出版社出版的普通高中信息技术选修1《算法与程序设计》4.2.2穷举法求解问题的实践。
前一个课时已经初步接触了穷举法的概念，本节课可以作为穷举法的第二节课，也可以独立作为穷举法的学习。
穷举法在实践中属于比较常见的一种算法，经典例子有百鸡百钱、鸡兔同笼等。
对于教材，我进行了一些处理再加工，使得本节课用到的三个例子由易到难，逐层深入，符合学生的认知特点。
二、学情分析通过高二上学期对前面的章节的学习，学生已经掌握了程序的基本语法、程序三种基本结构、解析法，有了一定的用编程解决问题的能力，但是怎么样把实际生活中的问题转化为计算机程序解决这一个过程对于学生而言是个难点。
三、教学目标1．了解穷举法的基本概念和穷举法解决问题的基本过程。
2．学会用穷举法编程解决实际问题，能够根据具体问题分析建立数学模型，编写程序求解问题3．通过经历穷举法解决问题的过程提高学生的计算思维能力，通过案例的分析引导学生关注信息社会责任。
四、教学重难点教学重点1、建立正确的数学模型，确定穷举方案。
2、根据命题确定穷举变量的取值范围，正确表达“符合条件”的判断。
教学难点：1、合理选择穷举方案2、算法和程序代码之间的转化五、教学策略根据我校学生的特点，我选择了一个尝试密码开宝箱的例子引入，首先让一个学生自己来演示尝试暴力破解这个密码。
这样，学生马上就能体会到什么叫穷举。
通过问题为刚才操作的同学尝试的过程，是不是有一个范围，引入穷举的范围，从简单破解2位数，到学生无法简单破解5位数的密码，自然引出这样单一的重复的过程可以由计算机来解决。
了解了暴力破解的原理，我们也就了解了穷举法的原理、特点。
通过实践活动一，让每个学生全员参与运行2位数密码破解和5位数密码破解的两个小程序，同时观察破解的时间长短和什么有关，老师再分析核心代码，进一步了解破解的原理，消除对新知识的恐惧感。
了解原理后，我使用两个实践活动问题，让学生练习，以便理解、运用穷举法。
一、教学目标1、知识与技能(1)．认识程序调试的意义。
(2)．基于计算机解决问题的调整，穷举法是计算机求解问题的基本算法。
(3)．穷举法也是人们常用的解决问题的方法，计算机的出现大大提升了这种方法的意义。
(4)．掌握用穷举法设计程序的基本思路。
(5)．通过调试不同的例程，掌握穷举法穷举技巧(变量安排、穷举方案的确定)。
(6)．计算机只是人类的工具，穷举方案的确定得靠人脑来完成，但穷举过程的实施计算机却比人脑有效。
(7)．通过深入研究穷举的技巧，积累程序设计的经验，提升自己设计程序求解问题的能力。
(8)．对于多种解决问题的方案，学会评价它们的好坏。
2、方法与过程本节以“百钱买百鸡问题”入手，由浅入深讲解了穷举算法的思路。
并通过钞票币值问题、电子邮箱密码问题的求解，介绍了如何恰当地安排穷举算法中的多个变量，如何设计穷举方案，使得穷举过程更加合理更有效率，举出了求一个5位密码问题的3种穷举方案，通过讨论、对比、总结，熟练掌握穷举算法的求解问题方法。
教学案例在最后部分安排了一个用于交流的问题，介绍了在穷举算法中，变量安排和穷举方案的确定是密切相关的如何安排，求解问题将会有许多方案，而不同的方案可能导致解决的效率有巨大的差异。
组织这些活动，在编程实践之后，对各种方案进行对比试验，加深穷举算法的理解。
3、情感态度和价值观通过本节内容的学习，学生对设计算法求解问题有了进一步的认识，对设计算法的步骤更加熟练，思考问题更加严密和有条理，程序编制和调试更有经验。
本节的学习对算法知识的积累，对继续学习的激发有更加强烈的愿望，培养学生的爱国主义精神。
二、重点难点1、教学重点(1)建立正确的数学模型，确定穷举方案。
(2)根据命题确定可解空间（即变量的取值范围）。
(3)正确表达“符合条件”的判断。
2、教学难点(1)如何确定穷举方案。
(2)如何评价各种穷举方案的优劣。
三、教学环境1、教材处理教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第二节，本节由一个植树数量的IQ题人手，引入穷举算法的思路。
一、教材分析与教法：《用穷举法解决问题》是《算法与程序设计》第三章第二节的内容，编程，对一部分学生来说，还是比较难和比较枯燥的。
因此，我在教学中，一直尽量使用趣味性程序等手段，贴近学生生活，将课堂的气氛调动得活跃起来，并可培养学生对这门课的兴趣。
穷举法是算法中比较常见，日常运用很多的一种。
在课本和学业水平考试中都作为一个重要的部分出现。
经典问题有水仙花数、搬砖问题、鸡兔同笼等。
课本在介绍穷举法时用的例子是一个相对复杂的演讲比赛分组的问题。
我个人认为，这样的一个引入部分不太适合我们的学生，一是学生不是很感兴趣，二是比较复杂。
其次，在课本第三章，我的教学方法借鉴了数学课的教法：从简单问题详细剖析，推出一般情况，得到结论（算法理论），再从理论推展开区，再解决其他问题。
根据我校学生的特点，我选择了一个反暴力破解的例子引入，要反暴力破解，就必须了解它的原理。
首先让学生自己来尝试暴力破解一个密码。
这样，学生马上就能体会到什么叫穷举。
从简单破解2 位数，到学生无法简单破解5 位数的密码，自然引出这样单一的重复的过程可以由计算机来解决。
了解了暴力破解的原理，我们也就了解了穷举法的原理、特点。
了解原理后，我使用两个例题让学生练习，以便理解、运用穷举法。
1、“搬砖”问题。
2、水仙花数。
属于趣味数学，这个话题很能引起学生的兴趣（该问题类似鸡兔同笼）通过这两个问题，由简单到复杂，学生便可基本掌握穷举法的应用。
二、教学目标1.知识与技能⑴理解用穷举法设计程序的基本思路。
⑵分析建立正确的数学模型，归纳穷举法穷举技巧（变量的设置、穷举方案的确定）。
2.过程与方法⑴经历用穷举法求解问题的基本过程。
⑵在学习过程中，发现穷举法的规律，并把它运用实际问题的解决中去。
3.情感态度与价值观⑴通过学习穷举法，体会“信息技术是双刃剑”的含义，树立正确使用信息技术的道德观，并形成反思的意识。
⑵引导学生关注穷举法在社会生活中的应用，激发学生学习的热情。
高中信息技术算法与程序设计分册4.2穷举法教案[授课形式]讲授课、实践课[教学目标]1、理解穷举法是计算机求解问题的差不多算法。
2、掌握穷举法设计程序的差不多思路。
3、通过调试不同的程序，掌握穷举法穷举技巧。
4、关于多种解决问题的方案，学会评价它们的好坏。
[教学重点]1、建立正确的数学模型，确定穷举方案。
3、正确表达“符合条件”的判断。
[教学难点]1、如何确定穷举方案。
2、如何评价各种穷举方案的优劣。
[教学方法]讲授法、探究法、演练法[教学课时]2课时[教学过程]穷举法的思路是，列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解答。
穷举算法模式：〔1〕问题解的可能搜索的范围：用循环或循环嵌套结构实现；〔2〕写出符合问题解的条件；〔3〕能使程序优化的语句，以便缩小搜索范围，减少程序运行时间。
陈婷所在学校的3个环保活动小组经常利用节假日去栽树。
有一天，李老师问他们3个小组各栽了多少棵树?因为李老师是教数学的，陈婷就调皮地回答：“3个小组的栽树数量相乘的积是30723，您能把3个小组的栽树数量算出来吗?”李老师说：“只有那个条件不能确定答案呀。
你能补充点情况吗?’’因此陈婷补充说：“A组都是大个子同学组成的，栽的树尽管不到100棵，但比另外两组合起来的还要多。
栽树最少的C组也早就超过了10棵。
这时李老师说：“那我算出来了。
”李老师是怎么样算出来的呢?李老师后来告诉陈婷，她用的是穷举法。
例题一：栽树数量问题的求解a、b、c是三个整数，100>a>b>c>10，a×b×C=30723，且a>b+c，试确定a、b、c 的值。
(1)分析问题。
解决那个问题应当从a×b×C=30723人手。
把30723分解成三个正整数相乘的积，只能有有限种情况，我们能够把这些情况一一罗列出来，然后分析哪一种情况是符合条件(100>a>b>c>10，且a>b+c)的，从而找到答案(在列举所有情况时，注意三个因子都大于10，这能够减少列举的工作量)。
高中信息技术算法与程序设计分册4.2穷举法说课稿
【一】说教材
1、教材的地位与作用
首先，本章内容是在前面两章关于编程的差不多结构的基础上，关于实际生活中有代表性的某一类问题的具体算法的介绍，在本章第一节介绍了解析法之后，关于实际生活中列举类问题运用解析法不是太合适，因此引入第二种代表性的算法穷举法的介绍。
穷举法是算法中比较常见，日常运用特别特别多的一种。
经典问题有鸡兔同笼、百鸡百钱等。
在课本和等级考试中都作为一个重要的部分出现。
2、教学目标：
基于对教材的理解和分析，结合学生的实际，我从知识与技能、过程与方法、情感态度与价值观三方面制定了本课的教学目标。
知识与技能：使学生了解什么是穷举法及其特点，以及用穷举法设计算法的差不多过程；能够依照具体问题的要求，使用穷举法设计算法。
过程和方法：运用观看、发明、归纳、应用的方法，进展学生的归纳思维；培养学生独立探究与自主发明的学习能力。
情感态度与价值观：使学生了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的欢乐。
3、本课重点：用穷举算法解决问题的一般步骤；能依照具体问题的要求，提高运用穷举算法解决问题的能力。
难点：通过观看、类比多种方式培养学生归纳思维。
【二】说学情
第一，高二学生对世界的认识正处于由感性到理性，由具体到抽象的认识。
学生已掌握VB编程的差不多知识，并理解掌握解析法解决问题。
学生关于列举类的问题用解析法来实现感到困惑，有学习穷举算法的需求。
第二，选择《算法与程序设计》这本教材，关于我校相当一部分学生来说，依旧比较难和枯燥的，要想充分调动学生学习的积极性和主动性，必须选择合适的教学方法。
【三】说教法
成功的教学不是强制，而是激发学生的学习兴趣。
课本在介绍穷举法时用的例子是一个相对复杂的演讲竞赛分组的问题。
我个人认为，那个问题不太适合我们的学生，一是学生不是特别感兴趣，二是比较复杂。
依照我校学生的特点，本课采纳小组内合作的形式，降低了问题解决的难度，学生在教师的指导下带着任务通过小组合作、实际操作、探究学习等方式，逐
步完成任务，增强了凝聚力。
在讲解问题的过程中我借鉴了数学课的教法：从简单问题详细剖析，推出
一般情况，得到结论〔算法理论〕，再从理论推展开去，再解决其他问题。
【四】教学过程
在教学中，围绕教学的重点和难点，调动学生的主观能动性，引导学生层层深入，依照本课时特有的内容，我设计了如下的教学过程：
观看一发明一归纳一应用
我使用水仙花数问题这一例题让学生观看-发明-归纳。
通过那个问题，由简单到复杂，学生便可差不多掌握穷举法的应用。
然后及时让学生归纳总结穷举法解决问题的步骤并再接再厉利用假设干问题进行思维的深化与巩固。
学生的头脑不是一个需要填满的容器，而是一个需要燃烧的火把。
通过对比、分析、归纳，引导学生的思维活动向纵深进展，由表及里，培养学生良好的思维适应。
1、观看
学生阅读以下程序，分析程序的执行过程，说出程序的功能，此程序代码如下：Fori=1O0to999
a=int(i／1O0)
b=int(i／10)mod10
C=Imod10
Ifa5+b5+c5=ithen
Printi
Endif
Nexti
教师：首先问大伙，在第一次循环的时候，循环变量i值是多少？学生回答：100 那变量a的值是多少？学生回答：1
变量b的值是多少？学生回答：0
变量c的值是多少？学生回答：0
满不满足条件？有输出吗？
那第二次循环的时候，循环变量i值是多少？学生回答：101
那变量a的值是多少？学生回答：1
变量b的值是多少？学生回答：0
变量c的值是多少？学生回答：1
满不满足条件？有输出吗？
提问：
生活中你遇到过用穷举法解决的问题吗？让学生加深理解穷举的思想。
(2)发明
教师引导：①通过分析程序的执行过程，可看出变量a存放的是什么？学生：一个三位的自然数百位上的数字。
变量b存放的是？学生：是其十位上的数字，变量C存放的是？学生：是其个位上的数字；②一个三位的自然数，假设满足百位
的立方、十位的立方与个位的立方之和等于它本身，就输出；③此程序的功能是输出100～999之间的水仙花数。
教师总结：此程序的最大特点是列出了所有可能的对象，然后逐一判断是否满足给定的条件，从而求出问题的解。
当穷举完所有对象，问题将最终得以解决。
我们把这种算法称之为穷举法。
这节课我们学习用穷举法解决问题。
穷举法的定义：穷举法也叫枚举法，它是将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件，穷举完所有对象，问题将最终得以解决。
教师提问：生活中你遇到穷举法解决的问题吗？
教师引导：关于此题，某同学给出了另一种解法，请判断他的程序代码是否正确? Fora=1tO9
Forb=OtO9
Forc=OtO9
Ifa^3+b^3+c^3=a*1OO+1O*b+cthen
Printa*10O+b*1O+c
Endif
NextC
Nextb
Nexta
学生发明：第二种方法依旧采纳的是穷举算法。
在第一个程序中，循环的次数是900次，每次循环要执行四条语句。
而在第二个程序中，循环的次数是9XlOX10=900次，但每次循环只执行一条语句，因此第二个程序的执行效率高。
(3)归纳。
教师活动：通过“输出水仙花数”这一例子，能归纳出用穷举法解决问题的步骤吗?
学生归纳：①确定穷举对象及搜索范围：用循环或循环嵌套实现；②写出符合问题解的条件：用IF语句实现；③尽可能缩小搜索范围，减少程序运行时间，提高程序的执行效率。
(4)应用。
教师活动：现在我们反回头来看刚开始时让大伙思考的那道找回QQ密码的题，在编程实现之前，我们先来分析回答以下几个和此题相关的问题：①穷举的对象是什么?其搜索的范围是什么?②符合问题解的条件是什么?③你有方法减小搜索范围，提高程序的执行效率吗?
学生活动：①穷举的对象是密码，其搜索的范围是67008～67998；②符合问题解的条件是：此数既能被78整c除，也能被67整除。
学生活动：在用自然语言描述其算法后，编程实现，关心某同学找回QQ密码。
师生互动：在编程过程中，你遇到哪些困难?你是如何解决的?
设计意图：从一个学生熟悉的例子着手，让学生在观看中发明，在发明中质疑，在质疑中归纳，在归纳中解决问题。
学生增长知识的过程是轻松愉快的。
对比归纳，深化思维
判断以下两题能否用穷举算法解决，什么原因?通过分析，你能归纳出哪些能用穷举法解决，哪些不能用穷举法解决?
①在一个直角三角形中，三条边a、b、C的长度都为整数，且一条直角边a的长度已确定，斜边C的长度不能超过某数I，找出满足条件的所有直角三角形。
②使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w。
学生归纳：通过两题的对比分析，穷举算法适用的条件是：有明显的穷举范围且求解对象应该是有限的；能够按某种规那么列举对象；有穷举规那么；一时找不出解决问题的更好途径时。
通过对比归纳，学生不但巩固了穷举法的解题方法，而且深化了思维，学会对题目进行深入分析。
⏹总结：本课一是让学生理解穷举的思想，二是利用观、发明、归纳、应用一系列程
序，目的是让学生得出穷举的解题步骤：即三步走：
⏹①确定问题解搜索范围：用循环或循环嵌套实现；
⏹②写出符合问题解的条件：用IF语句实现；
⏹③尽可能缩小搜索范围，减少程序运行时间，提高程序的执行效率。
让学生看见穷举题目就会反射性地用三步解决它。
【五】说反思
回忆整个授课过程，我有如下感触:首先本课从一个熟悉的例子着手，让学生在观看中发明，在发明中质疑，在质疑中归纳，在归纳中解决问题。
学生增长知识的过程是轻松愉快的。
其次，在评价和展示学生成果时，应特别注意学生不同的编程思路，着重对其进行分析，找出优缺点。
第三，学生的头脑不是一个需要填满的容器，而是一个需要燃烧的火把。
通过对比、分析，归纳，引导学生的思维活动向纵深进展，由表及里，能够培养学生良好的思维适应。
