2.2 比较“笨”的枚举算法思想
之所以说枚举方法比较“笨”，是因为在面对问题时它会去尝试每一种情况。打一个比方，假设有两个小朋友A和B在玩捉迷藏的游戏，规定只能藏在树上、屋顶上和墙角。A比较聪明，他在找之前会先考虑到B恐高，所以他推测出B只能藏在角落处；而B比较笨，他不会考虑A会不会爬树，他会随便选一个地方找，如果发现这个地方没有，他会去寻找另外一个地方。如果可以藏的地方有多个，B会挨个地方寻找，直到找到A为止。上述B挨个地方寻找的做法就和枚举算法思想的原理一样。
再看枚举思想的定义：在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么该结论是可靠的，这种归纳方法叫做枚举法。由此可见，上面例子中B的寻找过程就属于枚举思想的范畴。
2.2.1 枚举算法基础
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下所示：
（1）确定枚举对象、枚举范围和判定条件。
（2）逐一枚举可能的解，验证每个解是否是问题的解。
枚举算法一般按照如下3个步骤进行：
（1）题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。
（2）判断是否是真正解的方法。
（3）使可能解的范围降至最小，以便提高解决问题的效率。
枚举算法的主要流程如图2-1所示。
图2-1 枚举算法流程图
2.2.2 实践演练
为了说明枚举算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解枚举算法思想在编程中的基本应用。
根据上述问题描述，我们用枚举算法解决了上述两个问题。首先解决实例1的问题，根据“百钱买百鸡”的枚举算法分析，我们编写实现文件xiaoji.c，具体实现代码如下所示。
#include <stdio.h>
int main()
{
int x,y,z;//定义3个变量，分别表示公鸡、母鸡和小鸡的个数
for(x=0;x<=20;x++)
{
for(y=0;y<=33;y++)
{
z=100-x-y;
if (z%3==0 &&x＊5+y＊3+z/3==100) //3种鸡一共100只
printf("公鸡：%d,母鸡：%d,小鸡：%d\n",x,y,z);
}
}
getch();
return 0;
}
执行后的效果如图2-2所示。
图2-2 执行效果
一个实例不能说明枚举算法思想的基本用法，接下来开始解决“举一反三”中的问题，根据“填写运算符”的枚举算法分析，编写实现文件yunsuan.c，具体实现代码如下所示。
#include <stdio.h>
int main()
{
int j,i[5]; //循环变量，数组i用来表示4个运算符
int sign; //累加运算时的符号
int result; //保存运算式的结果值
int count=0; //计数器，统计符合条件的方案
int num[6]; //保存操作数
float left,right; //保存中间结果
char oper[5]={' ','+','-','＊','/'}; //运算符
printf("输入5个数，之间用空格隔开：");
for(j=1;j<=5;j++)
scanf("%d",&num[j]);
printf("输入结果：");
scanf("%d",&result);
for(i[1]=1;i[1]<=4;i[1]++) //循环4种运算符，1表示+，2表示-，3表示＊，4表示/
{
if((i[1]<4) || (num[2]!=0)) //运算符若是/，则第二个运算数不能为0
{
for(i[2]=1;i[2]<=4;i[2]++)
{
if((i[2]<4) || (num[3]!=0))
{
for(i[3]=1;i[3]<=4;i[3]++)
{
if((i[3]<4) || num[4]!=0)
{
for(i[4]=1;i[4]<=4;i[4]++)
{
if((i[4]<4) || (num[5]!=0))
{
left=0;
right=num[1];
sign=1;
//使用case语句，将4种运算符填到对应的空格位置，并进行运算
for(j=1;j<=4;j++)
{
switch(oper[i[j]])
{
case '+':
left=left+sign＊right;
sign=1;
right=num[j+1];
break;
case '-':
left=left+sign＊right;
sign=-1;
right=num[j+1];
break;//通过f=-1实现减法
case '＊':
right=right＊num[j+1];
break;//实现乘法
case '/':
right=right/num[j+1];//实现除法
break;
}
}
//开始判断，如果运算式的结果和输入的结果相同，则表示找到一种算法，并输出这个解
if(left+sign＊right==result)
{
count++;
printf("%3d：",count);
for(j=1;j<=4;j++)
printf("%d%c",num[j],oper[i[j]]);
printf("%d=%d\n",num[5],result);
}
}
}
}
}
}
}
}
}
if(count==0)
printf("没有符合要求的方法！\n");
getch();
return 0;
}
在上述代码中，定义了left和right两个变量，left用于保存上一步的运算结果，right用于保存下一步的运算结果。因为“×”和“÷”的优先级高于“+”和“-”，所以计算时先计算“×”和“÷”，再计算“+”和“-”。执行后的效果如图2-3所示。
图2-3 执行后的效果
高手真经——什么时候选择使用枚举法
也许很多读者觉得枚举（enumeration）有点“笨”，很多人称其为“暴力算法（brute force enumeration）”；但是枚举却又总是我们面对算法问题时最先被想起的。
在任何情况下，都需要选准最合适的对象，无论是枚举还是其他算法思想，这是最关键的。选准（枚举）对象的根本原因在于优化，具体表现为减少求解步骤，缩小求解的解空间，或者是使程序更具有可读性和易于编写。有时候选好了枚举对象，确定了枚举思想解决问题，问题就迎刃而解了。有的时候，当题目逼着你用枚举思想解题时，需要考虑的往往是从众多枚举对象中选择最适合的，这需要辨别的智慧。
运用枚举思想思考时需要面对的问题如表2-1所示。
表2-1 运用枚举法时需要面对的问题
用枚举法解题的最大缺点是运算量比较大，解题效率不高。如果枚举范围太大（一般以不超过200万次为限），则由于效率低的问题而会在时间上难以承受。但枚举算法的思路简单，无论是程序编写还是调试都很方便。所以如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法，而无须太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。