3.2《用穷举法解决问题》教学设计

标签:
教育 |
分类: 算法与程序设计(高二) |
一、 教材分析与教法:
穷举法是算法中比较常见,日常运用很多的一种。在课本和学业水平考试中都作为一个重要的部分出现。经典问题有水仙花数、搬砖问题、鸡兔同笼等。课本在介绍穷举法时用的例子是一个相对复杂的演讲比赛分组的问题。我个人认为,这样的一个引入部分不适合我们的学生,一是学生不是很感兴趣,二是比较复杂。
其次,在课本第三章,我的教学方法借鉴了数学课的教法:从简单问题详细剖析,推出一般情况,得到结论(算法理论),再从理论推展开区,再解决其他问题。
根据我校学生的特点,我选择了一个反暴力破解的例子引入,要反暴力破截,就必须了解它的原理。首先让学生自己来尝试暴力破解一个密码。这样,学生马上就能体会到什么叫穷举。从简单破解2位数,到学生无法简单破解5位数的密码,自然引出这样单一的重复的过程可以由计算机来解决。了解了暴力破解的原理,我们也就了解了穷举法的原理、特点。
了解原理后,我使用两个例题让学生练习,以便理解、运用穷举法。1、水仙花数。属于趣味数学,这个话题很能引起学生的兴趣(该问题类似鸡兔同笼)。2、“搬砖”问题。
通过这两个问题,由简单到复杂,学生便可基本掌握穷举法的应用。
二、 教学目标
1.知识与技能
3.情感态度与价值观
教学重点:⑴建立正确的数学模型,确定穷举方案。
⑵根据命题确定变量的取值范围。
⑶正确表达“符合条件”的判断。
教学难点:⑴恰当安排穷举的方式,使得算法的效率更高。
⑵如何评价各种穷举策略的优劣。
四、课时安排:1课时。
环节 |
教师活动 |
学生活动 |
设计意图 |
激趣 导入 |
播放《终结者2》影片片断:主人公用解码器破解密码的场面: 在电影中我们经常看到这样的镜头,这似乎距离我们很遥远。其实,在我们的生活中,你是否有过密码被盗的经历呢? |
观看影片,积极思考,在看片的过程中体会穷举法的基本思路。 学生口答:QQ密码被盗,银行卡密码被盗等 |
通过学生喜欢的影片将学生引入到课堂学习的环境中来,激发学生的学习兴趣。 |
新知 导授
|
一、穷举法的概念 下面请大家打开桌面上的2位数破解密码的程序:程序界面如下图:
http://s1/mw690/002Qupwugy6GKY8uXiof0&690 请学生运行该程序,破解密码。(每排为一组,看谁破解的快) 请破解出密码的学生介绍经验:一个一个的去尝试。 教师总结:(投影)这种将求解对象一一列举出来,然后逐一加以分析、处理,并验证结果是否满足给定的条件,穷举完所有对象,问题将最终得以解决的方法,称为穷举法。 任务布置一:如果密码是5位数,我们还能用刚才的方法破解吗? 教师总结:用人工计算工作量大,很耗时,可由计算机完成。 分析问题:密码范围是10000—99999。 算法实现:设a为设定的5位数密码,I为输入的破解密码。穷举过程如下:
(1)
(2) 输出密码正确,若不是,将I加1,反复执行(2),直到密码正确后退出。 教师引导学生进行代码实现:
(1)
(2) |
小组讨论破解方法与技巧,分工破解
介绍破解经验与技巧
小组讨论:学生根据刚才的经验,思考是在10000—99999之间尝试,很耗时
学生运行桌面上的5位数密码破解程序,体验计算机破解密码 |
小组间通过竞争和协作使得每个学生都积极思考,参与问题解决
引导学生利用计算机来解决问题
让学生亲身体验,消除对密码破解程序神秘感 |
规律
总结
|
利用穷举法解决问题的基本思路:依据题目的已知条件,确定答案的大致范围,在此范围内对所有可能的情况,逐一验证,直到全部情况验证完,若某种情况经验符合条件则输出结果,否则继续查找,直到全部情况查询完毕为止。 |
学生通过讨论,尝试归纳总结
|
训练学生的逻辑思维习惯,培养学生总结规律的能力。 |
合作 探究 |
任务布置二: 36块砖,36人搬。男搬4,女搬3,两个小孩抬一块砖。要求一次全搬完。问需男、女、小孩各若干? 教师引导学生进行问题分析: 在数学中,通常如何解决这个问题? 设男、女、小孩人数分别为a、b、c (1)需要满足的条件: ________________=36 _________________=36 (2)穷举范围:
男:最多有__人, 小孩:最多有__人,并且人数必须是偶数。 教师发送半成品代码,要求学生填空: 任务设置三:
如:153=13+53+33 教师发送半成品代码,要求学生填空 |
学生根据实践情况,小组讨论得出结果
小组讨论得出结果: 1)明确本题的验证条件: a + b + c = 36 2)确定对象的范围: c 必须是偶数。
学生独立思考后口答 |
在课堂上,通过师生之间,生生之间的协作、交流,培养学生的合作意识、互助精神、人际沟通能力。
强化训练,深化理解,达到举一反三的目的。 |
拓展 延伸 |
提出问题:我们使用信用卡在柜员机上取钱时,为什么系统要限制输入密码的次数?
|
1、了解穷举法在破解密码方面的现实应用。 2、鼓励有兴趣的学生课余自主学习有关密码破解的知识,进行更深入的探索。 |
了解信息技术可能带来的不安全因素,自觉养成健康使用信息技术的习惯。
|
课堂 总结 |
(1)问题解的可能搜索的范围:用循环或循环嵌套结构实现; (2)写出符合问题解的条件; (3)能使程序优化的语句,以便缩小搜索范围,减少程序运行时间。 |
根据本节课的学习经验,小组讨论用穷举法解决问题的要领。 |
通过知识总结,帮助学生将知识系统化,便于学生理解记忆。
|
教学札记:
本节课由暴力破截的小游戏开头,学生立即投入进来,迅速接受穷举法的概念和关键技术点,这都符合我备课的预想。
难度适中,过渡自然,逐步推进是本节课比较成功的地方。在教学中,学生有激情,有思考,有实践,有成功,跌宕生趣,下课时意犹未尽,恋恋不舍。
发送半成品作品让学生完善也是本节课的一个特色。有时如果每个程序的每一步骤都让学生完成,效率太低,而发送半成品,可以达到事半功倍的效果。
总体而言,这节课基本上符合我事先备课的预想。但是,也有一定的问题,由于学生的两极分化比较明显,我带的班级既有理科的实验班,又有学史政的平衡班,史政治平衡班的学生感觉拿到题目,尽管已经知道算法思想,依然无法下手怎么样将这几名同学也能在课堂上编出一段程序来,也就是,怎样将题目设置的阶梯性更强些,基础题再基础些,以后在备课中要多注意。
附:
1、五位自然数密码破解程序:
Private Sub Command1_Click()
a = Val(Text1.Text)
For i
If
Text2.Text = Str(i)
End If
Next I
End Sub
2、“搬砖”问题半成品程序:
Private Sub Command1_Click()
Dim a, b, c As Integer
For a =
For b =
For c =
If
Print "男:"; a; "女:"; b; "小孩:"; c
End If
Next c
Next b
Next a
End Sub
3、水仙花数半成品程序:
Dim x, y, z As Integer
For x = __ To 9
For y = __ To 9
For z = __To 9
If ______________ = x ^ 3 + y ^ 3 + z ^ 3 Then
Print x ; y ; z
End If
Next z
Next y
Next x