高中信息技术选修1教案-4.2 用穷举法设计程序-粤教版

《用穷举法设计程序》教学设计
一、教材分析
本节课是广东教育出版社《算法与程序设计（选修1）》的4.2《用穷举法设计程序》的内容。包括：用穷举法求解问题的基本过程、用穷举法求解问题的实践。教材分别用“栽树数量问题的求解”、“钱币取法问题的求解”、“密码寻找问题的求解”三个问题求解案例进行教学组织。
二、学生分析
本节内容的教学对象是高一年级学生，他们已经具备了一定的逻辑思维、分析问题、表达思想的能力。同时，通过前面的学习与实践，学生已经历了编制计算机程序解决问题的过程，学会了对计算机程序进行调试，并掌握了顺序、条件、循环三种程序结构，为本节内容的学习提供了良好的基础。当然，对于如何寻找适当的穷举方案，设计出更好的穷举算法，学生尚缺乏足够的经验和能力。
三、教学目标
1.知识与技能
（1）了解穷举法的基本概念。
（2）能够根据具体问题的要求，使用穷举法设计算法，编写程序求解问题。
2.过程与方法
（1）在用穷举法求解问题的基本过程中，掌握用穷举法求解问题的基本思路和方法。
（2）在用不同的穷举方案求解问题的基本过程中，学会寻找适当的穷举方案，设计出更好的穷举算法。
3.情感态度与价值观
能够认识到穷举法在社会生活中的应用，在实例学习中同时激发学生探索真理的欲望。
四、教学重点
重点：掌握用穷举法求解问题的基本思路和方法。
五、教学难点
难点：学会寻找适当的穷举方案，设计出更好的穷举算法。
六、教学策略设计
教学中适宜采用讨论法、操作探究法相结合的任务驱动教学策略。
七、教学过程设计
教学内容
教师活动
学生活动
时间
设计意图
情境引入
【引入】
大家能猜出这是谁吗？
有没有同学看过有关福尔摩斯的作品？
他的身份是什么？
新快报：英发明“福尔摩斯”软件 可助警方破奇案
提问
聆听
介绍
引导
听讲
思考
回答
观看
约1分钟
通过有趣的引入，激发学生的好奇心，吸引学生的学习兴趣，引出后续学习任务的问题背景。
现代福尔摩斯侦探之谁是小偷问题的求解
【任务】
★问题描述
现代福尔摩斯侦探之谁是小偷：案发现场，有A、B、C、D四个人，其中一人偷了东西。当被问到是谁偷的时，A说：“不是我”，B说：“是C偷的”，C说：“是D偷的”，D说：“C胡说！”。已知四个人中有三个说的是真话，一个说的是谎话，您能否快速判断小偷究竟是谁？借助程序设计呢？
★问题解决
1.分析问题
提问：小偷是谁？您是如何求解的？
分析：
假设小偷是A，可知A说谎话、B说谎话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”不符，假设不成立；
假设小偷是B，可知A说真话、B说谎话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”不符，假设不成立；
假设小偷是C，可知A说真话、B说真话、C说谎话、D说真话，与已知的“三个说真话一个说谎话”符合，假设成立；
假设小偷是D，可知A说真话、B说谎话、C说真话、D说慌话，与已知的“三个说真话一个说谎话”不符，假设不成立。
2.设计算法
3.编写程序
Private Sub Form_Click()
For thief = Asc("A") To Asc("D")
If Int(Chr(thief) <> "A") + Int(Chr(thief) = "C") + Int(Chr(thief) = "D") + Int(Chr(thief) <> "D") = -3 Then
Print "The Thief is :"
Print Chr(thief)
End If
Next thief
End Sub
4.调试运行
5.检测结果
介绍
提问
聆听
演示
引导启发
听讲
思考
回答
观看
讨论
操作
约14分钟
通过讨论法、操练法引导学生初步体验用穷举法求解实际问题的基本过程，认识到穷举法在社会生活中的应用，吸引学生的学习兴趣。在实例学习中同时激发学生探索真理的欲望。
教学过程中重点引导学生掌握用穷举法求解问题的基本思路和方法，引导学生分析问题、设计算法，学生只需补充语句完善尚未完成的程序即可。
穷举法的基本思路
【思考与讨论】
请总结穷举法求解问题的基本思路？
【小结】
穷举法的基本思路
使用穷举法时，要恰当地设计变量，并且决定用哪些变量作为搜索的主线，接着列举一切与命题相关的情况，然后根据问题设定的条件，逐个加以检查，找到满足条件的解答。
【思考】
穷举方案都是唯一的吗？
提问
聆听
引导启发
介绍
听讲
思考
回答
讨论
约4分钟
通过引导学生结合前面任务的解决，归纳总结出穷举法求解问题的基本思路。
现代福尔摩斯侦探之密码破译问题的求解
【任务】
★问题描述
现代福尔摩斯侦探之密码破译：案发现场有一个密码箱，主人失踪了，为了追寻密码箱主人的下落，现需找出密码打开密码箱。已知密码箱主人是8月1日出生，他太太的生日是9月1日，密码箱主人的太太不大记得密码是多少，但她清晰地记得她先生曾告诉她密码是一个5位数，并且同时是81和91的倍数，她还记得密码的中间一位（百位数）是1。您能帮她找回这个密码吗？借助程序设计呢？
说明：
若学生按解决方案一回答，则引导学生按解决方案一求解程序；否则引导学生按解决方案二求解程序。
★问题解决——解决方案一
1.分析问题
提问：数学上如何求解这个问题？
分析：
（1）建立数学模型（用数学语言描述问题）——
求出一个5位数，它的百位是1，而且它能同时被81和91整除。
（2）确定解决方案——
因为这个密码有4位数字是未知的，把各位数字都对所有可能性演变一次（最高位是1-9，其余各位都是0~9），就可以把可能的情况穷举完。再把各位数字合成一个5位数，判断是否同时被81和91整除就可以了。
2.设计算法
3.编写程序
Private Sub Command1_Click()
For a1 = 1 To 9
For a2 = 0 To 9
For a4 = 0 To 9
For a5 = 0 To 9
d = a1 * 10000 + a2 * 1000 + 1 * 100 + a4 * 10 + a5
If (d Mod 81 = 0) And (d Mod 91 = 0) Then Print d
Next a5, a4, a2, a1
End Sub
4.调试运行
5.检测结果
★问题解决——解决方案二
1.分析问题
提问：数学上如何求解这个问题？
分析：
（1）建立数学模型（用数学语言描述问题）——
求出一个5位数，它的百位是1，而且它能同时被81和91整除。
（2）确定解决方案——
5位数字的范围是10000-99999，在此范围内穷举，并判断5位数是否同时被81和91整除，再对每一个数分解出它的百位数字检验它是否1就可以了。
2.设计算法
3.编写程序
Private Sub Command1_Click()
For a = 10000 To 99999
If (a Mod 81 = 0) And (a Mod 91 = 0) Then
If a \ 100 Mod 10 = 1 Then
Print a
End If
End If
Next a
End Sub
4.调试运行
5.检测结果
介绍
提问
聆听
演示
引导启发
听讲
思考
回答
观看
讨论
操作
约10分钟
通过讨论法、操练法引导学生在知识迁移中加深对穷举法求解问题的基本过程的理解。再次在实例学习中同时激发学生探索真理的欲望。
教学过程中重点引导学生分析问题、设计算法，不要求学生在课堂上完成程序的编写。
穷举法的改进思路
【思考】
前面的搜索方案执行效率如何？可以改进吗？（改进是以效率的高低而不是按程序的长短来衡量）
【小结】
穷举法的改进思路
“与命题相关的情况”所包含的范围可能很广，如果不加以限制可能会白白耗费计算机的运行时间。所以在设计穷举的过程时，应当明确或建立适当的数学模型，构造穷举的框架，然后通过逐步求精的过程，改善算法，使穷举过程变得恰当。
提问
聆听
引导启发
介绍
听讲
思考
回答
讨论
约2分钟
通过引导学生结合前面任务的解决，归纳总结出穷举法求解问题的改进思路。
现代福尔摩斯侦探之密码破译问题的再求解
【任务】
★问题描述
略
★问题解决——解决方案三
1.分析问题
提问：数学上如何求解这个问题？
分析：
（1）建立数学模型（用数学语言描述问题）——
求出一个5位数，它的百位是1，而且它能同时被81和91整除。
（2）确定解决方案——
有解的范围只限于同时是81和91的倍数。81和91的最小公倍数是81*91，所以我们只在5位数中就81*91的倍数进行穷举，然后分离出它的百位数字判断是否是1就能得到答案。
2.设计算法
3.编写程序
Private Sub Command1_Click()
p = 10000 \ (81 * 91) + 1
For a = p * (81 * 91) To 99999 Step (81 * 91)
If a \ 100 Mod 10 = 1 Then
Print a
End If
Next a
End Sub
4.调试运行
5.检测结果
介绍
提问
聆听
演示
引导启发
听讲
思考
回答
观看
讨论
操作
约10分钟
通过引导学生体验用另一种穷举方案求解问题的基本过程，认识到穷举法应用的灵活性。
教学过程中重点引导学生分析问题、设计算法，不要求学生在课堂上完成程序的编写。
穷举法中穷举方案的选择
【思考与讨论】
以上几个不同方案的程序在执行效率上有何不同？在用穷举法求解问题的过程中，我们应该怎样选择穷举方案？
【小结】
穷举法中穷举方案的选择
对于许多问题，解决问题的算法往往不只一种，这时我们就得注意加以选择，找一种更好的算法。评价一个算法的好坏，许多时候效率是很重要的。当然在考虑效率的同时也要重视程序的易读性。
提问
聆听
引导启发
介绍
听讲
思考
回答
讨论
约2分钟
通过引导学生对比前面任务的不同解决方案，树立“寻找适当的穷举方案，设计出更好的穷举算法”的意识。
总结
【总结】
1.穷举法求解问题的基本思路和方法。
2.学会寻找适当的穷举方案，设计出更好的穷举算法。
【思考与讨论】
我们登录网上银行或者电子邮箱时，为什么要限制输错密码的次数？
提问
聆听
引导启发
介绍
听讲
思考
回答
讨论
约2分钟
引导学生回顾、总结本节课学习的主要内容。
引导学生分析、讨论穷举法在日常生活中的其它应用。
八、参考文献
[1]中华人民共和国教育部.普通高中技术课程标准（实验）[M].北京：人民教育出版社2003年.
[2]广东基础教育课程资源研究开发中心信息技术教材编写组.信息技术（选修1）——算法与程序设计[M].广州：广东教育出版社2004年.
[3]广东基础教育课程资源研究开发中心信息技术教材编写组.信息技术（选修1）——算法与程序设计教师教学用书[M].广州：广东教育出版社2004年.