优化枚举算法提升计算思维-以百鸡百钱问题为例.docx

??

?

??

优化枚举算法提升计算思维——以“百鸡百钱问题”为例

?

??

?

?

?

?

?

?

?

???

?

?

?

?

?

摘要：如今，在教学中培养和提升学生的计算思维已成了教学中的重中之重。本文主要通过在“百钱百鸡问题”的教学中引导学生对枚举算法进行优化和完善来提升学生的计算思维，并迁移到类似问题中，提高学生解决问题的实际能力。

关键词：计算思维；枚举算法；算法优化

一、计算思维与枚举法概述

计算思维简述

计算思维并不是一个新概念，人生而有之。从图灵等人对计算机科学的研究以来，100年的时间，我们进入了信息社会。计算机领域的发展扩大了计算思维的影响范围，使之成为继实证思维和逻辑思维之后被确立的第三种科学思维模式。从中小学开始，计算思维就在学科教学中被朦朦胧胧的使用，却从没有向如今般受到重视。2006年，周以真提出计算思维（ComputationalThinking）的概念在全球的计算机教育届引起了广发的关注。各科学家普遍认为计算思维是计算机领域最具基础性和普遍性，到2050年，每个地球公民都应该掌握计算思维[1]。

2017年，我国的《普通高中信息技术课程标准》明确指出，计算思维是学科的四大核心素养之一，是个体运用计算机科学领域的思想方法，在形成问题解决方案的过程中产生的一系列思维活动。具备计算思维的学生在具体的信息活动中能够采用计算书能够处理的方式界定问题，抽象特征、建立结构模型合理组织数据，并运用合理的算法解决问题。[2课程标准]

枚举法概述

枚举法也称穷举法，是指在有穷的可能解得集合中，逐个有哪些信誉好的足球投注网站集合的每一个元素，用问题给定的检验条件去判断此解是否符合条件，若满足条件，此元素为该问题的一个解。枚举法是浙江信息技术学业水平考试要求掌握的算法，因为其简单、易理解等特点，也作为信息技术程序设计课程的入门算法。适用此算法求解的问题要求，必须是其问题的规模和可能解的规模不是特别大，且解变量的值的变化具有一定的规律。在找不出更高效算法的情况下，可以使用此算法试探性求解问题。该算法充分利用了计算机处理自动化、速度快的特点。

枚举求解的基本步骤：（1）确定可能解得范围。（2）抽象问题特征，得到正确解的形式化表达式。（3）对解对的每个层数的数据范围进行循环遍历。（4）利用条件语句判断正确解。（5）优化程序，缩小枚举范围，循环次数，提高程序的效率。如图1所示，枚举算法的基本模型为：利用for循环一一列举可能的结，利用if语句实现逐个判断可能的解。

for……#一一列举

if……#逐个检验

……

图1

枚举法有很多经典的例子，如：“百钱买百鸡”问题，“密码还原”问题，“水仙花数”问题等都是利用穷举法进行编程的典例。在信息技术课堂教学中教师常以百钱买百鸡”问题的优化来提升学生的计算思维。培养学生形式化描述问题，抽象问题的特征，建立数学模型，利用计算机自动化解决问题的能力。并对已有的算法进行优化和完善，并迁移到类似的问题中。其中“百钱买百鸡”问题描述如下：

公元五世纪末，我国古代数学家张丘建在《算经》中提出了如下的问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何。

二、运用枚举法求解“百钱买百鸡”问题

设鸡翁、鸡母、鸡雏的个数分别g，m，x只。引导学生用计算思维抽象问题特征：公鸡每只5钱，母鸡每只3钱，小鸡每只1/3元。形式化描述问题如下：

且

用100钱买100只鸡，若全买公鸡最多买100/5只，得：

公鸡数量：

同理，母鸡数量：

小鸡数量：

且

1.暴力枚举——“百钱买百鸡”问题的三层循环解法

运用枚举法构建三层循环逐个检验上述范围内g，m，x是否符合“百钱、百鸡”这两个条件；若符合，则该组合{g,m,x}就是该问题的一个解。Python实现上述算法代码如下图2，输出如图3所示。

。

图2图3

分析图2代码可知最内层循环结构执行次数为21*34*101=72114次，即需要验证72114种不同的g，m，x的组合解。教师应当让学生自己实现以上算法并引导学生发现问题。根据图3可知正确的解一共有四组，其中有72110次判断是多余的消耗时间，导致最后程序运行时间平均值约为0.07s。教师引导学生挖掘隐藏的条件以此优化算法，进而提升学生算法思维，培养学生计算思维。

算法优化一

教师不应满足于简单的的解决问题，而要引导学生优化算法，挖掘隐藏的条件：在暴力枚举求解过程中，并没有考虑到公鸡数量g的改变将影响母鸡数量m的取值范围。且小鸡数量一定为3的倍数。所以优化过程中可以减少第二层循环的次数，形式化描述各变量的变化范围如下所示：

公鸡数量：

母鸡数量：

小鸡数量：

且

优化算法后用Python实现“百鸡买百钱”问题程序代码如图4所示。从图5中程序运行结果可以看出优化过后的算法无论是