当前位置：首页 > 枚举-递归-回溯
一、暴力求解法（枚举法 / 穷举法）
概念：什么是枚举法？
在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法。即，把所要解决问题的所有可能性都列举出来，一一试验。
枚举应用简单举例：求1~100之间的素数；求水仙花数；鸡兔同笼问题；百元买百鸡问题；整数（分数）拆分问题；排列问题??
枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点： 1、得到的结果肯定是正确的；
2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。 3、通常会涉及到求极值（如最大，最小，最重等）。
4、数据量大的话，可能会造成时间崩溃。
采用枚举算法解题的基本思路：
（1） 确定枚举对象、枚举范围和判定条件； （2） 一一枚举可能的解，验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。
例1：百元买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？ 算法分析：
我们以三种鸡的个数为枚举对象（分别设为x,y,z），以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z/3)为判定条件，穷举各种鸡的个数。 （1） 基本算法：
for (x=0;x<=100;x++)
for (y=0;y<=100;y++)
for(z=0;z<=100;z++)
if (x+y+z==100 && z%3==0 && x*3+y*2+z/3==100) 输出
x,y,z
（2） 优化算法：只需要枚举2种鸡x（x<=33）和y（y<=50)，第3种根据约束
条件100-x-y可得:
1
for (x=0;x<=33;x++)
小结：对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。
1. 枚举对象的选择问题：
在枚举算法中，枚举对象的选择是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：
例2：将1,2...9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1:2:3的比例，试求出所有满足条件的三个三位数。例如：三个三位数192，384，576满足以上条件。
我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围将大大缩小。 例3. 五猴分桃：五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分.一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份 ,结果多了一个,就将多的这个吃了,并拿走其中的一份.一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份.接着来的第3,第4,第5只猴子都是这样做的.......,
根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?
算法分析：我们设总的桃子数为S0，五子猴子分得的桃子数分别为S1，S2，S3，S4，S5，则有以下关系式：S0 = 5*S1 + 1； 4*S1 = 5*S2 + 1； 4*S2 = 5*S3 + 1； 4*S3 = 5*S4 + 1； 4*S4 = 5*S5 + 1；
我们可以枚举桃子总数S0，从5开始直到满足条件，此时S0的值就是最少的总桃子数。对应程序如下： int main(void) {
int s[6] = {0}; int i;
for(s[0]=5; ;s[0]++) {
s[1] = s[0] - 1;
if (s[1]%5) // （s[0] – 1）要能被5整除
2
for (y=0;y<=50;y++) {
Z=100-x-y;
if (z%3==0 && x*3+y*2+z/3==100) 输出x,y,z
continue; else
s[1] /= 5;
s[2] = 4 * s[1] - 1; if (s[2]%5)
continue; else
s[2] /= 5;
s[3] = 4 * s[2] - 1; if (s[3]%5)
continue; else
s[3] /= 5;
s[4] = 4 * s[3] - 1; if (s[4]%5)
continue; else
s[4] /= 5;
s[5] = 4 * s[4] - 1; if (s[5]%5)
continue; else
s[5] /= 5;
break; //很关键，什么时候结束枚举
}
printf(\摘了%d个桃子, 剩下%d个桃子\\n\for (i=0; i<6; i++) printf(\return 0; }
程序输出：摘了3121个桃子, 剩下765个桃子。
根据程序结果我们知道循环体执行了3116次，同时我们可以知道第5个猴子分得255个桃子，所以如果枚举S5，则循环体只需执行了255次。对应程序如下： #include
int main(void) {
int s[6] = {0}; int i;
for(s[5]=1; ;s[5]++) {
s[4] = 5 * s[5] + 1; if (s[4]%4)
3
// （4 * s[1] - 1）要能被5整除
continue; else
s[4] /= 4;
s[3] = 5 * s[4] + 1; if (s[3]%4)
continue; else
s[3] /= 4;
s[2] = 5 * s[3] + 1; if (s[2]%4)
continue; else
s[2] /= 4;
s[1] = 5 * s[2] + 1; if (s[1]%4)
continue; else
s[1] /= 4;
s[0] = 5 * s[1] + 1; break;
}
printf(\摘了%d个桃子, 剩下%d个桃子\\n\return 0; }
我们可以发现求S4，S3，S2，S1的表达式完全是一样的，所以我们可以用一个函数或者循环来表示，改进后的程序如下： #include
int main(void) {
int s[6] = {0}; int i;
for(s[5]=1; ;s[5]++) {
for (i=4; i>0; i--) {
s[i] = 5 * s[i+1] + 1; if (s[i]%4)
break; else
s[i] /= 4;
}
if (i == 0) {
s[0] = 5 * s[1] + 1; break; } }
4
本文作者：...共分享92篇相关文档
