2.1 枚举算法思想
知识点讲解：光盘：视频讲解\第2章\枚举算法思想.avi
枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。
2.1.1 枚举算法基础
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。
① 确定枚举对象、枚举范围和判定条件。
② 逐一列举可能的解，验证每个解是否是问题的解。
枚举算法一般按照如下3个步骤进行。
① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。
② 判断是否是真正解的方法。
③ 使可能解的范围降至最小，以便提高解决问题的效率。
枚举算法的主要流程如图2-1所示。
图2-1 枚举算法流程图
2.1.2 实战演练——百钱买百鸡
为了说明枚举算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解枚举算法思想在编程中的基本应用。
实例2-1 使用枚举法解决“百钱买百鸡”问题
源码路径 光盘\daima\2\xiaoji.c
问题描述：我国古代数学家在《算经》中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意为：公鸡每只5元，母鸡每只3元，小鸡3只1元。用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少？
算法分析：根据问题的描述，可以使用枚举法解决这个问题。以3种鸡的个数为枚举对象（分别设为 mj、gj和xj），以3种鸡的总数（mj+gj+xj=100）和买鸡用去的钱的总数(xj/3+mj×3+gj×5=100)作为判定条件，穷举各种鸡的个数。
具体实现：根据上述问题描述，用枚举算法解决实例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 “百钱买百鸡”问题执行效果
2.1.3 实战演练——解决“填写运算符”问题
一个实例不能说明枚举算法思想的基本用法，在下面的实例中将详细解使用枚举法解决“填写运算符”的问题。
实例2-2 使用枚举法解决“填写运算符”问题
源码路径 光盘\daima\2\yunsuan.c
问题描述：在下面的算式中，添加“+”“-”“×”“÷”4个运算符，使这个等式成立。
5 5 5 5 5 = 5
算法分析：上述算式由5个数字构成，一共需要填入4个运算符。根据题目要求，知道每两个数字之间的运算符只能有4种选择，分别是“+”“-”“×”“÷”。在具体编程时，可以通过循环来填入各种运算符，然后再判断算式是否成立。并且保证当填入除号时，其右侧的数不能是0，并且“×”“÷”运算符的优先级高于“+”“-”。
具体实现：根据上述“填写运算符”的枚举算法分析，编写实现文件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语句，将四种运算符填到对应的空格位置，并进行运算
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 “填写运算符”问题执行效果