找回作业文件夹“密码”

陈珊

● 教学内容分析

枚举算法是一种常用的基础算法。依赖计算机的高速运算能力，枚举算法能解决很多问题，如密码破译、搜索等。利用枚举算法解决问题的关键是通过分析问题，确定枚举对象、范围和检验条件。另外，同一问题的枚举方式可以多样。本节课是枚举算法的应用，要求学生利用枚举算法解决两个具体问题——“百鸡百钱”和密码破解，让他们在分析循环次数的基础上，体会利用计算机的高速运算能力进行枚举解决问题的优势。

● 学情分析

学生已经学习了枚举算法的概念，有利用分支、循环语句编写程序解决问题的经验，但用枚举算法解决具体问题时，枚举对象、范围、检验条件的确定还存在一定困难，对同一问题的不同枚举方式认识不到位，同时对利用计算机的高速运算能力进行枚举解决问题的优势体会不强烈。本节课，笔者利用两个具体问题，在体验、讨论、小组合作的过程中，让学生经历枚举算法解决实际问题的过程，体会枚举算法的价值，了解人解决问题与计算机解决问题的差异。

● 教学目标

知识与技能目标：进一步理解枚举算法的思想，利用枚举算法解决具体问题。

过程与方法目标：在解决“百鸡百钱”、密码破解问题的过程中，體验利用枚举算法解决问题的方法；通过小组合作，经历分析问题、设计算法、编写/调试程序的过程。

情感态度与价值观目标：感受利用计算机进行枚举的优势，愿意用枚举算法去解决生活、实践中的问题。

● 教学重点、难点

重点：利用枚举算法解决问题的一般过程。

难点：认识到枚举算法是利用计算机的高速运算能力来解决问题。

● 教学过程

1.导入环节

（1）情境导入：被“加密”的作业文件夹。

师：许多同学已经发现，今天的作业文件夹竟然被“加密”了。接下来，给大家一分钟时间，亲自动手尝试“找回”作业文件夹的密码。（PPT中1分钟倒计时开始）

学生在紧张、兴奋中开始尝试“破解”作业文件夹密码，1分钟到了，但文件仍未打开（如图1）。

（2）小组讨论：破解密码需要线索。

师：刚才是如何“找”密码的？找回密码存在什么困难？请大家围绕这两个问题开展讨论。

师生互动，确定“找”密码的过程就是枚举，是人工在一一列举所有可能的密码（如“123456”“xinxi”等），逐一输入检验能否打开作业文件夹。由于密码的位数、组成等特征未知，所以猜测密码非常困难。学生要想破解作业文件夹密码，需要一些线索。

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整除。

（2）利用枚举算法破解作业文件夹密码。

Step1：分析线索，设计算法。

小组根据线索二，讨论枚举的对象、范围和检验条件，写在学案上。这一问题也有不同的枚举方式，鼓励学生有不同的想法，关注算法的多样性（如图5）。

Step2：编写、调试程序。

小组根据确定的枚举对象、范围和检验条件，编写VB程序，调试运行得出可能的密码解（如图6）。

Step3：验证密码，打开作业文件夹。

学生获得解决问题的成就感。

4.知识延伸

笔者通过图灵密码破译机、深蓝、AlphaGo三个实例说明枚举算法是利用计算机的高速运算能力来解决问题。在密码破译领域，暴力枚举本身就是一种重要而基础的方法。1997年战胜国际象棋大师卡斯帕罗夫的“深蓝”，暴力穷举是其算法核心，2017年大热的AlphaGo，其关键就包括蒙特卡洛算法——一种优化的枚举算法。笔者还特别提及了AlphaGo的硬件构成，让学生直观感受计算机快速运算能力的基础是强大的硬件支撑，并进一步提出了思考问题：生活中还有哪些运用枚举算法解决问题的实例？鼓励学生去寻找、发现枚举算法。

5.总结

课堂总结分两部分，一是知识總结，包括枚举算法的概念、特征及结构特点，利用枚举算法解决问题的过程等。二是对小组合作表现的总结，汇总小组积分，奖励积分最高小组。

● 教学反思

本堂课设计了两个破解密码的线索，环环相扣，让学生跟随“破解”作业文件夹的密码这一主要任务，经历利用枚举算法解决两个具体问题的过程（分析问题、设计算法、编写调试程序），充分调动学生的兴趣，学生参与度很高。

笔者从多角度、多途径突破教学难点，让学生在破解密码的真实情境中主动寻找解决问题的方法，通过讨论、对比手工枚举（计算）与计算机枚举的差异，让他们直观感受计算机高速运算速度所带来的优势。在程序展示部分，笔者分析了程序的循环次数，再次让学生感受计算机的高速运算能力。同时，在知识延伸部分，笔者通过深蓝、AlphaGo的实例，让学生认识到枚举算法是利用计算机的高速运算能力来解决问题。

学生深刻体会到计算机软硬件相结合的重要性，软件功能的实现是基于硬件，这一点在枚举算法上体现得尤其明显。正是由于计算机硬件的发展，高速的运算能力才能得到保证，也才让枚举算法有了用武之地。在知识延伸部分，笔者让学生认识到枚举算法的重要而广泛的应用，同时抛出一个思考问题，让学生带着问题离开课堂，鼓励他们去发现、观察生活中枚举算法应用的实例。在解决两个具体问题的过程中，笔者让学生利用抽象的方法建立数学模型，设计算法，编写程序，让计算机自动化运行以解决具体的问题，以小组为单位完成算法设计、程序编写、交流及展示活动，通过积分奖励/兑换的形式，激励学生，小组合作效果较好。

点 评

算法是计算机解决问题的钥匙，如何配好这把钥匙，是人的智慧。用计算机解决问题，就需要充分认识到计算机的特点并充分运用其特点，发挥计算机的优势。在《枚举算法的应用》一课，学生通过了解图灵在二次世界大战期间破译密码的事例以及自己动手编写解密程序等学习环节，可以很好地达成这一教学目标。

尽管枚举算法是算法学习中一种简单且容易理解的算法，但对初学算法的学习者来说，仍然是枯燥和抽象的。《枚举算法的应用》一课引用“百鸡百钱”和“文件夹密码破解”相嵌套的问题场景，激发学生的挑战欲和好奇心，在已经掌握运用循环结构实现枚举算法的基础上，完成更复杂问题解决方法的学习任务。

趣味性可以解决枚举算法学习起步时的动机，对《枚举算法的应用》一课教学过程中生成性资源的进一步挖掘可以获得更多的学习动机，因为枚举算法的学习核心不只是有趣，也不是两次枚举算法重叠的简单重复使用，而在于如何将待解决的问题有效地分解为可以重复执行的循环结构以及判别条件并以程序代码的形式表达出来。在教学过程中，教师所展示的“百鸡百钱”三种不同解决方案为深入研究枚举算法的实施提供了空间，这一方面可以引导多重循环知识技能的学习，另一方面也反映了如何有效发挥计算机优势即平衡计算机执行效率和降低人的智力劳动强度关系的思想方法。与此同时，在解决“百鸡百钱”问题之后，教师同样用枚举算法要求学生解决“文件夹密码破解”，这时教师也可以设定不同的学习目标要求，供不同学习层次的学生练习。