回作业文件夹“密码”——《枚举算法的应用》教学设计
优质课展台
回作业文件夹“密码”
——《枚举算法的应用》教学设计
陈珊  上海交通大学附属中学嘉定分校
● 教学内容分析
枚举算法是一种常用的基础算法。依赖计算机的高速运算能力,枚举算法能解决很多问题,如密码破译、搜索等。利用枚举算法解决问题的关键是通过分析问题,确定枚举对象、范围和检验条件。另外,同一问题的枚举方式可以多样。本节课是枚举算法的应用,要求学生利用枚举算法解决两个具体问题——“百鸡百钱”和密码破解,让他们在分析循环次数的基础上,体会利用计算机的高速运算能力进行枚举解决问题的优势。
● 学情分析
学生已经学习了枚举算法的概念,有利用分支、循环语句编写程序解决问题的经验,但用枚举算法解决具体问题时,枚举对象、范围、检验条件的确定还存在一定困难,对同一问题的不同枚举方式认识不到
位,同时对利用计算机的高速运算能力进行枚举解决问题的优势体会不强烈。本节课,笔者利用两个具体问题,在体验、讨论、小组合作的过程中,让学生经历枚举算法解决实际问题的过程,体会枚
举算法的价值,了解人解决问题与
计算机解决问题的差异。
● 教学目标
知识与技能目标:进一步理
解枚举算法的思想,利用枚举算
法解决具体问题。
过程与方法目标:在解决“百
鸡百钱”、密码破解问题的过程中,体
验利用枚举算法解决问题的方法;
通过小组合作,经历分析问题、设计
算法、编写/调试程序的过程。
情感态度与价值观目标:感
受利用计算机进行枚举的优势,愿
意用枚举算法去解决生活、实践中
的问题。
● 教学重点、难点
重点:利用枚举算法解决问
题的一般过程。
难点:认识到枚举
算法是利用计算机的高速
运算能力来解决问题。
● 教学过程
梁家辉女儿晒吻照1.导入环节
(1)情境导入:被“加
密”的作业文件夹。
师:许多同学已经发现,今天
的作业文件夹竟然被“加密”了。接
下来,给大家一分钟时间,亲自动
手尝试“回”作业文件夹的密码。
(PPT中1分钟倒计时开始)
学生在紧张、兴奋中开始尝试
“破解”作业文件夹密码,1分钟到
了,但文件仍未打开(如图1)。
(2)小组讨论:破解密码需要
线索。
师:刚才是如何“”密码的?
回密码存在什么困难?请大家围
绕这两个问题开展讨论。
师生互动,确定“”密
码的过程就是枚举,是人工在
一一列举所有可能的密码(如
“123456”“xinxi”等),逐一输入
检验能否打开作业文件夹。
由于密
图1 被“加密”的作业文件夹
码的位数、组成等特征未知,所以猜测密码非常困难。学生要想破解作业文件夹密码,需要一些线索。
2.活动一:解决“百鸡百钱”问题,获得密码线索
(1)给出密码线索一。师:破解密码需要两条至关重要的线索。每个小组需要用10个积分来换取线索一。线索一描述:鸡翁一值钱五,鸡母一值钱三,鸡
雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?
(2)利用枚举算法解决“百鸡百钱”问题。
Step1:分析问题。
分析“百鸡百钱”问题,学生抽象提炼出方程组(如图2,公鸡x 只、母鸡y只,小鸡z只)。
小组开展讨论:如何才能求解x、y、z的值?学生习惯从数学思
维出发,逐一人工凑数来求解这一不定方程组,也有学生尝试消元后再出符合条件的解。教
师充分肯定这一思路,同时引导学生思考能否利用计算机来解决这一问题。学生认同,可以利用枚举
算法解决“百鸡百钱”问题。
Step2:设计算法。
小组讨论枚举对象、范围和检验条件,写在A3纸板上,并在全班展示交流“百鸡百钱”问题的不同枚举方式,进一步复习巩固枚举算法
的三要素:枚举对象、范
围和检验条件(如图3)。
Step3:编写、调试程序。学生编写、调试VB程序,运行得出“百鸡百钱”问题的所有可能解。全班展示不同的程序实现,教师着重引导学生分析程序(三重循环、二重循环、一重循环)的循环次数,让学生真实感受到计算机的高速运算能力,体会利用计算机进行枚举的优势。同时,教师对比不同程序循环次数的差异,适当解释枚举算法优化的必要性(如下表)。
运行程序,得到“百鸡百钱”问题的四组解,教师说明其中第二组解的数字(4、18、78)是破解密码的线索一(如图4)。
3.活动二:回作业文件夹“密码”
(1)给出密码线索二。师:在获取线索一(4、18、78)后,许多同学立马去尝试打开作业文件夹,但都失败了。因为,破解密码还需要至关重要的线索二,小组依然需要用10积分换取线索二。线索二描述:密码的首位数字是4,密码的末位数字的三倍是18,密码组成的四位数能被
健康体质回执单家长寄语
78整除。
                                      “百鸡百钱”问题的不同程序实现
(1)
(2)
(3)
循环次数:21×34×101=72114次循环次数:21×34=714次循环次数:
21次
图2 “百鸡百钱”问题方程组
图3 “百鸡百钱”问题不同的枚举方式
图4 “百鸡百钱”问题的第二组解是线索一
(2)利用枚举算法破解作业文件夹密码。
Step1:分析线索,设计算法。
小组根据线索二,讨论枚举的对象、范围和检验条件,写在学案上。这一问题也有不同的枚举方式,鼓励学生有不同的想法,关注算法的多样性(如图5)。
Step2:编写、调试程序。
小组根据确定的枚举对象、范围和检验条件,编写VB程序,调试运行得出可能的密码解(如图6)。
Step3:验证密码,打开作业文件夹。
学生获得解决问题的成就感。
4.知识延伸
笔者通过图灵密码破译机、深蓝、AlphaGo三个实例说明枚举算法是利用计算机的高速运算能力来解决问题。在密码破译领域,暴力枚举本身就是一种重要而基础的方法。1997年战胜国际象棋大师卡斯帕罗夫的“深蓝”,暴力穷举是其算法核心,2017年大热的AlphaGo,其关键就包括蒙特卡洛算法——
一种优化的枚举算法。笔者还特别提及了AlphaGo的硬件构成,让学生直观感受计算机快速运算能力的基础是强大的硬件支撑,并进一步提出了思考问
题:生活中还有哪些运用枚举算法
解决问题的实例?鼓励学生去寻
、发现枚举算法。
5.总结
课堂总结分两部分,一是知
识总结,包括枚举算法的概念、特
征及结构特点,利用枚举算法解决
问题的过程等。二是对小组合作表
现的总结,汇总小组积分,奖励积
分最高小组。
七年级数学教学工作总结● 教学反思
本堂课设计了两个破解密
码的线索,环环相扣,让学生跟随
“破解”作业文件夹的密码这一主
要任务,经历利用枚举算法解决两
个具体问题的过程(分析问题、设
计算法、编写调试程序),充分调
动学生的兴趣,学生参与度很高。
笔者从多角度、多途径突破教
学难点,让学生在破解密码的真实
情境中主动寻解决问题的方法,
灰原哀出现集数
通过讨论、对比手工枚举(计算)与
计算机枚举的差异,让他们直观
感受计算机高速运算速度所带来
的优势。在程序展示部分,笔者分
析了程序的循环次数,再次让学生
感受计算机的高速运算能力。同
时,在知识延伸部分,笔者通过深
蓝、AlphaGo的实例,让学生认识
到枚举算法是利用计算机的高速
运算能力来解决问题。
学生深刻体会到计算机软硬
件相结合的重要性,软件功能的实
现是基于硬件,这一点在枚举算法
上体现得尤其明显。正是由于计算
机硬件的发展,高速的运算能力才
能得到保证,也才让枚举算法有了
用武之地。在知识延伸部分,笔者
让学生认识到枚举算法的重要而
广泛的应用,同时抛出一个思考问
题,让学生带着问题离开课堂,鼓
励他们去发现、观察生活中枚举
算法应用的实例。在解决两个具
体问题的过程中,笔者让学生利用
抽象的方法建立数学模型,设计
奈叶同人之预言之书
算法,编写程序,让计算机自动化
运行以解决具体的问题,以小组
为单位完成算法设计、程序编写、
交流及展示活动,通过积分奖励/
兑换的形式,激励学生,小组合作
庶怎么读
效果较好。
图5 “密码破解”问题不同的枚举方式图6 运行程序求解得到三组密码
算法是计算机解决问题的钥匙,如何配好这把钥匙,是人的智慧。用计算机解决问题,就需要充分认识到计算机的特点并充分运用其特点,发挥计算机的优势。在《枚举算法的应用》一课,学生通过了解图灵在二次世界大战期间破译密码的事例以及自己动手编写解密程序等学习环节,可以很好地达成这一教学目标。
尽管枚举算法是算法学习中一种简单且容易理解的算法,但对初学算法的学习者来说,仍然是枯燥和抽象的。《枚举算法的应用》一课引用“百鸡百
钱”和“文件夹密码破解”相嵌套的问题场景,激发学生的挑战欲和好奇心,在已经掌握运用循环结构实现枚举算法的基础上,完成更复杂问题解决方法的学习任务。
趣味性可以解决枚举算法学习起步时的动机,对《枚举算法的应用》一课教学过程中生成性资源的进一步挖掘可以获得更多的学习动机,因为枚举算法的学习核心不只是有趣,也不是两次枚举算法重叠的简单重复使用,而在于如何将待解决的问题有效地分解为可以重复执行的循环结构以及判别条件
(点评人:华东师范大学  王荣良)
并以程序代码的形式表达出来。在教学过程中,教师所展示的“百鸡百钱”三种不同解决方案为深入研究枚举算法的实施提供了空间,这一方面可以引导多重循环知识技能的学习,另一方面也反映了如何有效发挥计算机优势即平衡计算机执行效率和降低人的智力劳动强度关系的思想方法。与此同时,在解决“百鸡百钱”问题之后,教师同样用枚举算法要求学生解决“文件夹密码破解”,这时教师也可以设定不同的学习目标要求,供不同学习层次的学生练习。
变龙B的值,所以改变的是存储器的值而不是寄存器的值,在Logisim中画出小变龙变的电路图(如第29页图9)。
3.改变颜后发生位移的电路将“A变后的动作”这一列转化成二进制,左是0,右是1,得到“1101”,输入网址“www .32x8/var2.html”,在交互表单中由上至下选中“1101”,按“Submit”,自动得到逻辑电路图(如第29页图10)。
此图表示取A反和B的或运算值。由于这次改变的是位移方向,所以逻辑门的输出结果影响的是控制存储器读写方向的计数器,第29页图11表示的就是计数器,在
Logisim软件中画出电路图(如第29页图12)。
计数器前端加上一个非门,是为了照顾人们从左到右读取数字的习惯,如不加,则存储器中的数据需要从右往左读。
● “造”出一台图灵机(10分钟)
有了上面三张逻辑电路图,就可以“造”出一台图灵机了,可是怎么使用这三张图呢?在画图软件里设置好“透明选择”,然后把三张图重叠在一起就可以得到完整的图灵机的逻辑电路图了。接下来,使用逻辑电路模拟软件Logisim把元件按电路图的样子连接好,就可以运行这台图灵机了!真正运行后可以
发现,
数据的变化规律有点让人意想不到。注意寄存器里的数值代表的是大变龙A的颜,而存储器里的数值代表的是小变龙B的颜。当然也可以用电子元件将电路实际搭出来,可以当作创客的项目。
本文所实现的还只是一台专用图灵机,若要实现通用图灵机,就需要扩展寄存器的数量或存储器的存储数据位数,还要改变进行颜变化的逻辑电路,实现起来要复杂多了,这个难题就留给有兴趣的朋友自行探索吧——虽然说笔者并没有抱太大期望,不过或许哪天就能得到一份意外的惊喜哟!
(上接第29页)

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。