简单枚举法在信息学竞赛中的应用

杜春玲

摘 要： 枚举法是信息学竞赛中一种最基本的算法，是竞赛中最常见的题型，本文主要介绍信息学竞赛中的枚举法，从枚举算法的优化和判定条件这两个方面探讨如何用枚举法解答信息学竞赛试题。

关键词： 枚举法 信息学竞赛 算法优化 判定条件

信息学竞赛是在具有丰富知识和一定实践能力的基础上，思维与思维的竞赛。优秀的选手往往具有快速、敏捷的思维。因此，我们在不断探讨方法、总结经验的同时，有必要尝试探索系统的思维方法，达到启迪思路的目的，本文就介绍信息学竞赛中的一种思维方法：枚举法。

枚举法（也称穷举法） ，是基于计算机运算速度快这一特性，使用的非常普遍的思维方法。根据问题中可能的情况，一一列举出分析求解的方法，它指在一个有穷的可能的解的集合中，枚举出集合中的每一个元素，用题目给定的约束条件判断其是否符合条件，若满足条件，则该元素即为整个问题的解；否则就不是问题的解。

下面探讨如何用枚举法解题。

一、缩小枚举范围可以优化枚举算法

我们以枚举算法的经典例题：百钱买百鸡，探讨枚举算法的优化。

有个人打算用一百块钱买一百只鸡。到市场一看，大鸡三块钱一只，不大不小的鸡两块钱一只，小鸡一块钱三只。怎样才能用一百块钱买一百只鸡？

算法分析：我们以三种鸡的个数为枚举对象（分别设为x，y，z），以三种鸡的总数（x+y+z）和买鸡用去的钱的总数（x*3+y*2+z）为判定条件，穷举各种鸡的个数。以下是解百鸡问题的程序：

for x∶=0 to 100 do {枚举大鸡所有可能的解}

for y∶=0 to 100 do{枚举不大不小的鸡所有可能的解}

for Z∶=0 to 100 do{枚举小鸡所有可能的解}

if （x+y+z=100）and（x*3+y*2+z div 3=100）and （z mod 3=0） then writeln（x，y，z）；

本题还有优化空间，三种鸡的总只数是100，我们只要枚举两种鸡（x，y），第三种鸡就可以根据约束条件求得（z=100-x-y），这样就缩小了枚举范围，请看下面的程序：

for x：=0 to 100 do

for y：=0 to 100-x do

begin z：=100-x-y；

if （x*3+y*2+z div 3=100）and（z mod 3=0）then writeln（x，y，z）； end；

未经优化的程序循环了101■ 次，优化后的程序只循环了（102*101/2）次。因此，对于枚举算法，找出约束条件，缩小枚举范围，是程序优化的主要考虑方向。

二、解题的关键是设定正确的判定条件

在解题过程中，枚举法的判定条件也很重要，如果约束条件不正确或不全面，就穷举不出正确的结果，请看一元三次方程求解的例子。

ax■+bx■+cx+d=0，该方程各项系数（a，b，c，d均为实数），并设定该方程有三个不同实根（根的范围在-100至100之间，且根与根之差的绝对值>=1）。要求在同一行输出这三个实根，并精确到小数点后两位。

算法分析：根的范围在-100到100之间，保留两位小数，我们将根的值域扩大100倍（-10000<=x<=10000），再以根为枚举对象，枚举范围是-10000到10000，用原方程式一一验证，找出方程的解。

有的同学是这样做的：

for i：=-10000 to 10000 do

begin x：=i/100；

if a*x*x*x+b*x*x+c*x+d=0 then write（x：0：2，）； end；

用这样的方法把程序编写出来，将样例数据代入测试是对的，但这题不完全对。

这种解法为什么有问题呢？通过上面的算法，枚举范围和枚举对象都没有错，但在验证枚举结果时，判定条件用错了。由于要保留两位小数，因此求出来的解不一定是方程的精确根，再代入ax■+bx■+cx+d中，所得的结果就不一定等于0，因此用原方程ax■+bx■+cx+d作为判断条件是不准确的。

我们换一个思路考虑这个问题，该方程f（x）=ax■+bx■+cx+d，假设x为方程的根，一定会有f（x-0.005）*（x+0.005）<0，如果以此为枚举算法的判定条件，问题就会顺利解决。而且，如果f（x-0.005）=0，就说明x-0.005是方程的根，这时四舍五入，方程的根就是x。所以我们用 （f（x-0.005）*f（x+0.005）<0） 和 （f（x-0.005）=0）作为判定条件。

用枚举法解题的最大缺点是运算量比较大，解题效率低，如果枚举范围太大（一般以不超过两百万次为限），就会超出竞赛要求的时限。但枚举算法的思路简单，比赛时容易想到，易于程序编写和调试，因此，如果题目的枚举范围规模不是很大，在规定时限内能够求出正确的解，那么我们最好采用枚举法，而不需要耗用时间想那些更快的算法，这样就可以有更多时间解答其他难题。