屈玫琦
杭州市富阳区场口中学
摘要：如今，在教学中培养和提升学生的计算思维已成了教学中的重中之重。本文主要通过在“百钱百鸡问题”的教学中引导学生对枚举算法进行优化和完善来提升学生的计算思维，并迁移到类似问题中，提高学生解决问题的实际能力。
关键词：计算思维；枚举算法；算法优化
一、计算思维与枚举法概述
1.计算思维简述
计算思维并不是一个新概念，人生而有之。从图灵等人对计算机科学的研究以来，100年的时间，我们进入了信息社会。计算机领域的发展扩大了计算思维的影响范围，使之成为继实证思维和逻辑思维之后被确立的第三种科学思维模式 。从中小学开始，计算思维就在学科教学中被朦朦胧胧的使用，却从没有向如今般受到重视。2006年，周以真提出计算思维（Computational Thinking）的概念在全球的计算机教育届引起了广发的关注。各科学家普遍认为计算思维是计算机领域最具基础性和普遍性，到2050年，每个地球公民都应该掌握计算思维 [1]。
2017年，我国的《普通高中信息技术课程标准》明确指出，计算思维是学科的四大核心素养之一，是个体运用计算机科学领域的思想方法，在形成问题解决方案的过程中产生的一系列思维活动。具备计算思维的学生在具体的信息活动中能够采用计算书能够处理的方式界定问题，抽象特征、建立结构模型合理组织数据，并运用合理的算法解决问题。[2课程标准]
2.枚举法概述
枚举法也称穷举法，是指在有穷的可能解得集合中，逐个搜索集合的每一个元素，用问题给定的检验条件去判断此解是否符合条件，若满足条件，此元素为该问题的一个解。枚举法是浙江信息技术学业水平考试要求掌握的算法，因为其简单、易理解等特点，也作为信息技术程序设计课程的入门算法。适用此算法求解的问题要求，必须是其问题的规模和可能解的规模不是特别大，且解变量的值的变化具有一定的规律。在找不出更高效算法的情况下，可以使用此算法试探性求解问题。该算法充分利用了计算机处理自动化、速度快的特点。
枚举求解的基本步骤：（1）确定可能解得范围。（2）抽象问题特征，得到正确解的形式化表达式。（3）对解对的每个层数的数据范围进行循环遍历。（4）利用条件语句判断正确解。（5）优化程序，缩小枚举范围，循环次数，提高程序的效率。如图1所示，枚举算法的基本模型为：利用for循环一一列举可能的结，利用if语句实现逐个判断可能的解。
.png)
图1
枚举法有很多经典的例子，如：“百钱买百鸡”问题，“密码还原”问题，“水仙花数”问题等都是利用穷举法进行编程的典例。在信息技术课堂教学中教师常以百钱买百鸡”问题的优化来提升学生的计算思维。培养学生形式化描述问题，抽象问题的特征，建立数学模型，利用计算机自动化解决问题的能力。并对已有的算法进行优化和完善，并迁移到类似的问题中。其中“百钱买百鸡”问题描述如下：
公元五世纪末，我国古代数学家张丘建在《算经》中提出了如下的问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何。
二、运用枚举法求解“百钱买百鸡”问题
.png)
1. 暴力枚举——“百钱买百鸡”问题的三层循环解法
运用枚举法构建三层循环逐个检验上述范围内g，m，x是否符合“百钱、百鸡”这两个条件；若符合，则该组合{g, m, x}就是该问题的一个解。Python实现上述算法代码如下图2，输出如图3所示。
。
.png)
3.算法优化二
以上算法都是枚举三种鸡数量（g,m,x）有效范围内所有可能的组合，根据两个条件（百鸡&百钱）筛选出符合条件的解。因此需要采用三层循还（一一枚举）加两条公式（逐个检验）来实现。循环结构是程序运行过程中最耗费时间的结构。教师需要引导学生思考是否可以再次挖掘隐藏的条件，减少循环次数。从题目条件中可以获知若解满足题目要求，必然符合“百鸡”的条件，可直接的到小鸡的数量。或者满足“百钱”的条件，可得小鸡的数量.选择其中一种作为小鸡数量的表达式：
.png)
对比“暴力枚举”与“优化一”可以发现，利用隐藏条件可以有效缩小循环变量的枚举范围从而提高算法效率。将“优化二”、“优化三”与“优化一”对比发现，减少枚举的循环层数可以大幅度优化算法。无论是循环次数，空间复杂度，执行时间都有明显减小。算法“优化四”无论在时间复杂度还是在循环次数上，都达到最优化状态。对于枚举算法，由于其本身的“低效率”特性，应充分利用已知条件，挖掘隐含条件控制枚举的范围与循环层数以优化算法。
培养学生计算思维重点是培养学生抽象问题特征、形式化描述问题并运用合理的算法运用计算机自动化处理问题的能力。马克思认为：“一种科学只有在成功地运用数学时，才算达到了真正完善的地步。”在“百鸡买百钱”问题中教师引导学生利用数学方法作为形式化表达的工具有助于发现问题的隐含的条件，并通过枚举法设计解决算法，编写程序运用计算机自动化执行，通过对算法迭代优化提高执行效率。设计算法解决问题过程中涉及到的抽象能力与自动化方法正是计算思维的本质特征。教师在教学中可利用枚举算法及其优化问题来有效培养和提升学生的计算思维。
[1]教育部高等学校大学计算机课程教学指导委员会.计算思维教学改革宣言[J].中国大学教学 2013