挖掘题目内涵，注重算法教学中的发散性思维培养

说在前面

本文根据笔者课堂教学实录整理加工而成。原本只打算花几分钟简单点评一下作业，由于不小心多问了几个问题，引发了学生兴趣，结果一发不可收拾，在一个题目上“耗”了整整一节课的时间，学生还意犹未尽，表示课后还要花更多的时间来研究这个问题。

可见给学生足够思考时间、鼓励学生发散思维时，学生会发现很多教师“看不到”的东西；若教师不囿于课前计划、保持课堂的开放性、因势利导，往往可能形成“无心插柳柳成荫”的效果。

本节课的前置内容是“枚举算法”，笔者原计划上新课“算法程序实现的综合应用”。因为上节课的课后练习中有一道题目错误率较高，所以笔者打算先花几分钟讲一下作业。

题目如下：

有如下Python程序段:

s = 0for i in range(1, 20):    j = 2    flag = True    while j <= 4 and flag:        if i % j == 0:            flag = False        j += 1    if flag:        s = s + iprint(s)

执行程序后，变量s的值是           

此题考查枚举算法思想和二重循环的应用，题目涉及变量较多，分析起来头绪纷杂，容易出错。

关于二重循环的处理办法，我要求学生主要注意两点：一是设计表格，跟踪变量变化情况；二是观察变量变化规律，总结程序功能，预测程序运行结果。

我先让学生使用表格法跟踪程序运行，看看能否找到规律；同时把代码发给学生，允许他们通过上机调试程序来寻找规律。

我们可以设计如下表格，跟踪变量值的变化情况：

简单跟踪几轮循环，可以发现内层循环变量j的取值范围是[2,4]，变量flag用来判断i是否能被j整除，若j不是i的因数，则将i累加到s中。

由此可知程序的功能是计算s = 1 + 5 + 7 + 11 + 13 + 17 + 19，故答案为73。

也有学生在代码s = s + i之前加了一条输出语句print(i)，看看都有哪些i值被筛选出来了，由此也观察出了i值的规律：都是不能被2和3整除的整数。

找到答案以后，我做了简单总结：程序的功能是筛选出[1,19]范围内不能被2和3整除的整数，并累加到变量s中，这是枚举算法的典型应用。

然后，我又问了一连串问题：为什么这么简单的结论我们很多同学一开始都没有看出来？题目的难点究竟在哪里？你能否对程序进行改进，写出简明易懂的代码？

同学们纷纷表示主要是对二重循环不熟悉，思路不够清晰；一看到大段代码和多个变量就慌了神，没有耐心去跟踪程序、记录变量的变化情况。

明确了程序功能以后，编写代码的难度就大大降低了。几位平时表现比较出色的同学很快给出了他们的代码。其中一个如下：

s = 0for i in range(1, 20):    if i % 2 == 0 or i % 3 == 0 or i % 4 == 0:        continue    s += iprint(s)

程序运行结果完全正确，同学们都表示赞赏。

然后有人提出条件表达式可以写得更简单些，因为i % 4 == 0是多余的。也有人表示可以去除continue语句，只要在条件表达式前面加个not就行了，代码如下：

s = 0for i in range(1, 20):    if not (i % 2 == 0 or i % 3 == 0):        s += iprint(s)

还有人表示在条件表达式前面加not不太习惯，可以把not (i % 2 == 0 or i % 3 == 0)改成i % 2 != 0 and i % 3 != 0。赢得了一片赞赏声。

讨论到这里就告一段落了，通过此题我们复习了枚举算法的思考方法和程序框架，并对条件表达式的写法有了进一步认识。

在成功引导学生展开讨论和改进代码以后，我不禁有些沾沾自喜，心想这节课开局不错，可以顺利地进入下一步了。

突然有一个声音响起：“我觉得原题的代码也很好。使用二重循环是为了方便表示更多的可能性，当j的取值范围比较大时，使用条件表达式反而更麻烦。例如当j的取值范围是[1,10]时，条件表达式要写做i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0。这样还不如使用二重循环来得方便。”

大家都愣了一下，然后群起鼓掌！

然后又有一个声音响起：“使用二重循环是很好，但是j的值不应该递增，这样会出现重复判断，例如若i不能被2整除，则肯定也不能被2的倍数整除，就没必要再重复判断了。我发现j只需要取质数，我们把这些质数存储到列表中，再遍历列表就行了”。

例如我们可以扩大j的取值范围，编写这样一段代码：

s = 0a = [2, 3, 5, 7]for i in range(1, 20):    flag = True    for j in a:        if i % j == 0:            flag = False            break    if flag:        s += iprint(s)

同学们纷纷表示这段代码不错，但涉及变量有点多，理解起来还是有一定困难。

然后有人说他可以把变量flag去掉。因为flag的作用是记录内层循环中是否执行了break语句，这个功能可以由Python自身的for…else语法来实现。代码如下：

s = 0a = [2, 3, 5, 7]for i in range(1, 20):    for j in a:        if i % j == 0:            break    else:        s += iprint(s)

代码少了2行，看上去果然简明了一些。大家都非常满意，讨论的声音渐渐平息下来。

同学们满意了，我却高兴不起来，因为时间已经过去快20分钟了，这节课的教学任务肯定完不成了，总不能新课上到一半就结束吧。我该怎样混过剩下的20分钟呢？

我随意翻了翻作业本，看看能不能再拿几道题目出来讲一讲。

看到题目旁边红笔写着的s = 1 + 5 + 7 + 11 + 13 + 17 + 19，我突然灵光闪现——质数！被筛选出来的i除了1以外全部都是质数。又想起刚才学生说的可以把质数存储到列表中——那我们就可以改造这段代码，用它来生成质数表。

我心中顿时有了主张。

我先问了同学们一个问题：在刚才的程序中，存储在列表a中的元素有什么特征？

学生回答：它们都是质数。

教师继续发问：这些质数是人工设置的还是程序自动生成的？

学生回答：人工设置的。

这时候我才抛出真正的问题：能否让程序自动生成一个质数列表？提示，观察被筛选出来的i值的特征。

有个学生很聪明，他很快领会了我的意图：难道是利用已有的质数来筛选新的质数？

没错，每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。例如6=2*3，60=2*2*3*5。根据分解质因数的原理，我们可以利用小质数筛选出更大的质数：先初始化质数表中只有一个质数2，然后把筛选出来的质数添加到质数表中；再利用新的质数表筛选出更大的质数，如此循环往复，就可以获得所需的质数表了。

有了算法思想的指导，我让学生分组讨论，改造原有程序代码，实现生成[2,50]范围内质数列表的功能。

程序有一定难度，几乎所有的学生都遇到了困难。在我的点拨之下，总算有一个小组完成了任务。代码如下：

a = [2]for i in range(3, 51):    for j in a:        if i % j == 0:            break    else:        a.append(i)print(a)

我请学生上台演示程序并介绍了算法原理，同学们给予了热烈的掌声。

我大声地表扬了该学生及其学习小组，对他们的程序给予了高度评价，认为他们发现了一种构造质数表的新方法——后来才发现其实这就是经典的欧拉筛法。

我要求所有学生都做好笔记，并为代码添加注释。由于有了之前的铺垫，大多数学生都理解了算法原理和每一行代码的含义，甚至有学生发现可以初始化a为空列表，只要修改i的取值范围为[2,50]，程序也能得到正确的结果。

学生们都很兴奋，意犹未尽。我一看距离下课还有不到10分钟，心想再继续讲解新的内容意思不大，还不如在质数问题上深挖一下。我告诉学生历史上最著名的构造质数表的方法是筛法求质数，并开放外网让学生上网查询关于筛法求质数的资料，要求他们理解算法思想后编写代码实现程序功能。

为了规范学生的编程行为，并体现模块化编程思想，我要求学生把程序功能抽象成一个自定义函数，并提供了函数头注释如下：

函数功能：质数又称素数，指在大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。根据输入的正整数n，返回最大值不大于n的质数表。

函数名：prime_list(n: int) -> list

参数表：n -- 一个规定了质数范围的正整数。

返回值：一个列表，存储了所有不大于n的质数。

示例：输入n=10，返回[2,3,5,7]。

虽然学生对质数有一定了解，也做过相关题目，但由于本题题目过于开放，学生不太适应。再加上时间不够充裕，大多数学生只来得及阅读相关资料和理解算法原理，没时间编写代码上机调试程序了，只好把问题带回去，留待课后思考。

当然，也有个别学生水平比较高，找到了合适的资料，快速理解算法并编写程序进行了调试。该学生使用的是经典的埃拉托色尼筛选法，简称埃氏筛法。它利用素数p只有1和p这两个约数，并且一个数的约数一定不大于自身的特征，对素数进行筛选。

筛选过程：把正整数从小到大顺序排列，1不是素数，首先把它筛掉；剩下的数中选择最小的数2是素数，然后去掉它的倍数；剩下的数中选择最小的数3是素数，然后去掉它的倍数；剩下的数中选择最小的数5是素数，然后去掉它的倍数；依次类推，直到序列为空时结束。

参考代码如下：

def prime_list(n: int) -> list:    lib = [True] * (n+1)    a = []    for i in range(2, n+1):        if lib[i]:#若i未被筛出，说明它是素数，将其添加到列表a中，并筛出i的倍数            a.append(i)             for j in range(i**2, n+1, i):#筛出i的倍数                lib[j] = False    return a

埃氏筛法虽然简明易懂，效率也很高，但是它有一个缺陷：对于一个合数，有可能被筛多次。例如 30=2*15=3*10=5*6……那么如何确保每个合数只被筛选一次呢？

我们只要用它的最小质因子来筛选即可，这便是欧拉筛法。欧拉筛法在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。参考代码如下：

def prime_list2(n: int) -> list:    lib = [True] * (n+1)    a = []    for i in range(2, n+1):        if lib[i]:#若i未被筛出，说明它是素数            a.append(i)        for j in a: #将当前素数表中素数j的i倍筛出。            if i*j <= n:                lib[i*j] = False                if i % j == 0:#为保证每个合数只被它的最小质因子筛选一次，当i是j的倍数时跳出循环                    break            else: #i*j大于n则不再处理                break    return a

仔细阅读欧拉筛法的代码及注释，我们发现课堂上学生给出的代码其实就是欧拉筛法的另一种实现方式，它不需要设置列表lib，直接根据列表a中的元素筛选出满足条件的i，大大节省了空间，代码也更为简明。参考代码如下：

def prime_list3(n: int) -> list:    a = []    for i in range(2, n+1):        for j in a: #遍历已有素数表，利用最小质因子排除合数            if i % j == 0: #若i为合数，跳出循环                break        else: #未执行break语句，说明i是素数            a.append(i)    return a

二重循环程序运行过程较为复杂，跟踪代码难度高，是编程初学者的一个拦路虎。当涉及变量较多时，学生容易产生畏难情绪，往往轻易放弃思考。

笔者在做题时会习惯性地思考如何改进代码，使其更简明易懂，以降低思维难度和节省阅读时间。在备课时，笔者考虑了简化代码的几种方法，也取得了预期的效果。但笔者急于消除原题代码中的内层循环和多余变量，忽略了二重循环的优点，没有做进一步挖掘。

幸好有学生发现了这个问题，又幸好笔者的课堂风格比较开放和民主，没有强行把教学进程拉到既定轨道，允许学生做了进一步讨论，发现了一些有趣的东西。更幸运的是笔者对质数相关算法比较熟悉，竟然在电光火石之间看到了该段代码蕴含的重要功能——生成质数表。

能够引导学生发现这段美妙的代码，有很大的运气成分，同时与教师的经验和教学风格分不开。我希望自己能够继续保持这种灵活开放的教学风格，在做好充分准备的前提下，给学生足够的思考时间、鼓励学生发散思维、因势利导，争取在课堂中能够遇到更多“精彩一刻”，撷取更多“意外收获”。

需要本文word文档、源代码和课后练习答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类