高中程序设计中的算法优化

摘 要：信息学奥赛以培养学生的学习兴趣为主，让学生的核心素养得以提高。本文通过“百钱买百鸡”问题的教学设计案例分析，在学生已有的数学知识的基础之上，逐步引导学生进行算法优化，有效提高学生的计算思维这一核心素养，培养他们发现问题、分析问题和解决问题的能力。

关键词：百钱买百鸡；计算思维；时间复杂度；算法优化

笔者从事高中信息学奥赛多年，有一点感触——开始学习这门课的学生和动力都很大（因为觉得很好玩，也很简单）没有涉及算法，就是简单输入输出和一些简单的语法，学生可以很轻松地解决一个问题，很有成就感。但是自从接触了循环之后，有些学生已经坚持不了了，我仔细分析了原因：①学生缺少兴趣；②学生没有学习算法的主动性；③学生对算法设计比较厌烦（觉得很枯燥，就是部分学生说的有的算法很烧脑）；④学生的数学知识可能与程序设计的要求不一致（数学知识要滞后）；⑤很有可能是我们的教法过于简单陈旧。所以我们今后要做好这项工作就必须根据具体的情况制定出可行的措施对学生进行施教。为该课程打下较好兴趣基础。

“百钱买百鸡”是一个古老的问题，具体解决的方法可以根据学生自己在初中学到的知识完成程序设计，然后可以在程序运行的时间复杂度上提出相应的要求，让学生不断地修改程序来进行算法的优化，最终达到从1000000次运算优化到4次运算。在这个过程中老师要不断地加以引导，还要不时地与学生进行交流，找到学生理解困难的地方，并及时加以讲解，一步一步地让学生进入自己所预设的操作当中。要对我们预设的效果进行合理合法的算法设计与分析，让学生不断地了解优化算法的重要性（为什么我们同样的程序虽然大家都可以得出正确的答案，但是有的同学写的程序运行效率很高，有些同学编写的程序运行时间很长），从而进一步激发学生学习这门课的兴趣。为信息学奥赛打下良好的基础。

百钱买百鸡的问题描述：公元前五世纪，我国古代数学家张丘建在《算经》一书中提出了“百鸡问题”：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？翻译为现代汉语的意思是：一只公鸡卖5文钱，一只母鸡卖3文钱，三只小鸡卖1文钱，问100文钱

买100只鸡，可以买多少只公鸡？多少只母鸡？多少只小鸡？

教师在引导学生理解了题目意思之后，可以让学生独立完成程序设计，学生的一般写法一般都会用到三重循环和二重循环。当然他们几乎都没有对程序算法进行优化或者说进行了简单的、粗暴的优化。三重循环就没有优化，就是用暴力的循环完成。公鸡、母鸡和小鸡都是从0到100之间，让计算机用穷举法列出符合的结果。简单的初步优化可以考虑100文全买公鸡应该是20，全买母鸡应该是34，最多买100只小鸡。这样对公鸡、母鸡和小鸡进行了初步的模糊范围进行修改优化。三重循环的伪代码如下：

//算法1 三重循环不优化

Void bqmbj1（ ）

{ int x，y，z； //x公鸡数y母鸡数z小鸡数

For（x=0；x<=100；x++）

For（y=0；y<=100；y++）

For（z=0；z<=100；z++）

If（x+y+z==100&&5*x+3*y+z/3==100&&z;%3==0）

Cout<

}

//算法2 三重循环初步优化

Void bqmbj2（ ）

{ int x，y，z； //x公鸡数y母鸡数z小鸡数

For（x=0；x<=20；x++）

For（y=0；y<=34；y++）

For（z=0；z<=100；z++）

If（x+y+z==100&&5*x+3*y+z/3==100&& z%3==0）

Cout<

}

在三重循环基础之上我们进一步分析三个变量之间的关系，第三个变量只要通过前面的两个变量就可以得出，即z=100-x-y；由于减少了变量的个数，所以我们可以写出下面两个算法，算法3就是不优化的二重循环，而算法4就是考虑了公鸡最多买20只，母鸡最多34只。二重循环的伪代码如下：

//算法3 二重循环不优化

Void bqmbj3（ ）

{ intx，y，z； //x公鸡数y母鸡数z小鸡数

For（x=0；x<=100；x++）

For（y=0；y<=100；y++）{

z=100-x-y；

If（x+y+z==100&&5*x+3*y+z/3==100&&z;%3==0）

Cout<

}

//算法4 二重循环初步优化

Void bqmbj3（ ）

{ int x，y，z； //x公鸡数y母鸡数z小鸡数

For（x=0；x<=20；x++）

For（y=0；y<=34；y++）{

z=100-x-y；

If（x+y+z==100&&5*x+3*y+z/3==100&& z%3==0）

Cout<

}

從上面列举的四个算法，虽然伪代码差不多，但是优化之后的程序在时间复杂度上有了质的变化。

我们看IF语句的执行频度，运算量1030301次降到714次，体会到算法优化的优越性，也就告诫我们既要能算法设计，也要有算法优化的理念。尽可能写出最优的算法。

对这个程序我们还可以进一步进行优化，最终实现一重循环。我们在施教程序优化的过程中要注意循序渐进，一步一步把学生引入最优算法。当然这里必须要以学生的数学知识作为基础。否则算法优化只能说一个空中楼阁。大家在平时的施教中灌输算法优化的思想，加强计算思维的训练，为学生的终身发展奠定必要的基础。

参考文献：

[1]胡峰，王国胤.算法分析与设计[J].当代教育理论与实践，2011（12）：72-74.

[2]邓春燕，张长海等.如何有效培养和提高高级语言程序设计学习兴趣[J].计算机教育，2011（8）.

作者简介：凌忠宝，江苏省泰州市，泰州市姜堰区张甸中学。