简单枚举算法

大家好，欢迎来到IT知识分享网。

前言

枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件：(1)可预先确定候选答案的数量；(2)候选答案的范围在求解之前必须有一个确定的集合。

枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。

本文收集可以采用枚举算法的一些题例，以供查阅、学习之用。

一、枚举算法基本思想

二、从鸡兔同笼问题说起

1. 《孙子算经》中的鸡兔同笼问题

以上侧重于运用数学思维来解决问题，下面采用计算思维来解决问题，具体而言，就是采用枚举法来解决问题。因为问题非常简单，这里不予分析，读者可以直接阅读代码来体会枚举法的基本思想。

#include<iostream> using namespace std; int main() { 
      unsigned int chickens, rabbits; for(rabbits=1; rabbits<23; rabbits++) { 
      chickens = 35 - rabbits; if(chickens*2 + rabbits*4 == 94) { 
      cout << "rabbits: " << rabbits << " "; cout << "chickens: " << chickens << endl; } } return 0; } 

2. 鸡兔同笼问题的其他版本

2. 其他类似的问题

代码如下：

#include<iostream> using namespace std; int main() { 
      unsigned int chickens, dogs, octopuses; for(chickens=1; chickens<24; chickens++) { 
      for(dogs=1; dogs<24; dogs++) { 
      octopuses = 24 - chickens -dogs; if(chickens*2 + dogs*4 + octopuses*8 == 102) { 
      cout << chickens << " " << dogs << " " << octopuses << endl; } } } return 0; } 

三、其他可以采用枚举法的题例

1. 原材料与各产品生产数量问题

#include<iostream> #include<algorithm> using namespace std; int main() { 
      int m = 800; int a=56, b=64, MAX = -1; //MAX存放最大消耗量 for(int i = 0; i*a<= m; ++i) { 
      for(int j = 0; i*a + j*b <= m; ++j) MAX = max(MAX, i*a+j*b); } for(int i = 0; i*a <= m; ++i) { 
      for(int j = 0; i*a + j*b <= m; ++j) if(MAX == i*a+j*b ) { 
      cout << "A: " << i << " "; cout << "B: " << j << endl; cout << "Material left: " << (m-MAX) << endl; cout << endl; } } return 0; } 

2. ABCD*E=DCBA问题

有这样一个算式：ABCD*E=DCBA 。其中，A、B、C、D、E代表不同的数字(E != 0,E != 1)。编一个程序，找出A、B、C、D、E分别代表什么数字？

#include<iostream> using namespace std; int main() { 
      int A,B,C,D,E; for(unsigned int n=1000; n<9999 ; n++) { 
      A=n/1000; B=n%1000/100; C=n%100/10; D=n%10; for(unsigned int E=2; E<=9; E++) { 
      if(n*E == D*1000+C*100+B*10+A) { 
      cout<<n<<"*"<<E<<"="<<n*E<<endl; break; } } } } 

3. abcde/fghij=n问题

#include<iostream> using namespace std; // 判断两个数是不是由十个数字排列组合而成，数字可以有前导0 // a是一个5位数，b是一个5位数，例如 // 79546/01283=62 // 94763/01528=62 bool judge(int a, int b) { 
      int p[10] = { 
     11}; //设置一个数组，用来存放形参的各个数位数字；初始化数组 int m; for(int i=0; i<5; i++) { 
      //求a的各个数位数字 m = a%10; p[m] = m; //将对应的数字放到数组中对应的位置，如a[2]=2 a /= 10; } for(int j=0; j<5; j++) { 
      //求b的各位数字 m = b%10; p[m] = m; b /= 10; } for(int k=0; k<10; k++) { 
      //判断a和b的各位数字是否有重复 if(p[k] != k) //若有重复，则必有a[n]=11;其中n属于0-9； return false; } return true; //各位数字都不同，返回true } int main() { 
      int n, i; int c=0; //累计次数，并初始化 for(i=2; i<=79; i++) { 
      //求i范围内的循环 for(n=1234; n*i<=98765; n++) { 
     //两个五位数相除变为分母乘以商，并控制循环范围 if(judge(n, n*i)) { 
      //判断两个数是不是0~9十个数字的排列 cout << (n*i) << " / " << n << " = " << i << endl; c++; } } } cout << "c=" << c << endl; return 0; } 

4. 学生列队问题（韩信点兵问题）

（1）某年级的所有同学列队，每9人一排多6人，每7人一排多2人，每5人一排多3人。问该年级至少有多少人？

#include<iostream> using namespace std; int main() { 
      for(int i=5; i<=2000; i++) { 
      if(i%9==6 && i%7==2 && i%5==3) { 
      cout << "The number of students is: " << i << endl; } } return 0; } 

#include <iostream> using namespace std; int main() { 
      for(int i = 1; ; i++) { 
      if(i%5==1 && i%6==5 && i%7==4 && i%11==10){ 
      cout << "the number of soldiers: " << i << endl; break; } } return 0; } 

（3）有一个较长的阶梯，若每步上2个台阶，最后剩1阶；每步上3个台阶，最后剩2阶；每步上5个台阶，最后剩4阶；每步上6个台阶，最后剩5阶；每步上7个台阶，最后正好1阶不剩。编写程序，求该阶梯至少有多少阶。

int main() { 
      for(unsigned int n=7; ; n+=7) { 
      if(n%2==1 && n%3==2 && n%5==4 && n%6==5) { 
      cout<<n<<endl; break; } } } 

5. 割羊毛问题

（1）雯雯家养了70只绵羊，每只大羊可剪羊毛1.6kg，每只羊羔可剪羊毛1.2kg。现在总共剪得羊毛106kg，请问大羊和羊羔各有多少只？

int main() { 
      int n = int(106/1.6); // cout << n << endl; // 66 for(int bigsheep=1; bigsheep<=n; bigsheep++) { 
      int sheep = 70 - bigsheep; if(bigsheep*1.6 + sheep*1.2 == 106) { 
      cout << "bigsheep: " << bigsheep << ", "; cout << "sheep: " << sheep << endl; } } return 0; } 

（2）假设1瓶醇酒能喝醉3个人，3瓶醨酒能喝醉1个人。33个客人共喝了19瓶就全醉倒了。请问他们一共喝了几瓶醇酒、几瓶醨酒？

int main() { 
      for(int liquor=1; liquor<=11; liquor++) { 
      int wine = 19 - liquor; if(liquor*3 + wine/3.0 == 33) { 
      cout << "liquor: " << liquor << ", "; cout << "wine: " << wine << endl; } } return 0; } 

5. 百钱百鸡问题

int main() { 
      int x, y, z; for (x=0; x<=20; x++) { 
      //cocks 100/5 for (y=0; y<=33; y++) { 
      //hens 100/3 z = 100-x-y; //chicks if(z>=0 && z%3==0 && 5*x+3*y+z/3 == 100) { 
      //总共100文钱  cout << x << ", " << y << ", " << z << endl; } } } return 0; } 

z>=0 && z%3==0 && 5*x+3*y+z/3 == 100 

但也可以仅仅写成如下形式

5*x + 3*y + z/3.0 == 100 

读者稍微比较一下，应该可以看出，前者的效率要高于后者（当然这里问题的规模很小，基本体现不出来），虽然表达式在形式上要长于后者。

int main() { 
      for(int cattle=0; cattle<=10; cattle++) { 
      for(int cattle2=0; cattle2<=20; cattle2++) { 
      int cattle3 = 100 - cattle - cattle2; if(cattle3%2 != 0) continue; if(10*cattle + 5*cattle2 + 1.0/2*cattle3 == 100) { 
      cout << cattle << ", " << cattle2 << ", " << cattle3 << endl; } } } return 0; } 

（3）用150元钱买3种水果。各种水果加起来一共100个。西瓜10元一个，苹果3元一个，橘子1元1个。设计一个程序，输出每种水果各买了多少个。

int main() { 
      for(int cattle=0; cattle<=10; cattle++) { 
      for(int cattle2=0; cattle2<=20; cattle2++) { 
      int cattle3 = 100 - cattle - cattle2; if(cattle3%2 != 0) continue; if(10*cattle + 5*cattle2 + 1.0/2*cattle3 == 100) { 
      cout << cattle << ", " << cattle2 << ", " << cattle3 << endl; // 1, 9, 90 } } } return 0; } 

总结

枚举属于“暴力解决”的范畴，现实生活中，很多问题都可以“暴力解决”——不用太动脑筋，把所有的可能性都列举出来，然后——实验。尽管这样的方法显得很“笨”，但却常常是行之有效的，尤其是在利用计算机来解决问题时。

本文收集整理的上述枚举算法的一些题例，涉及的都是一些相对简单的内容，例如整数、子串。虽然说是枚举算法（也称“穷举法”），这种方法解决问题相对不用太动脑筋，我们同样要注意程序运行的效率问题。在枚举之前对问题进行一定的分析、简化会让写出的枚举算法更加简洁、高效。特别是在问题的规模很大的情况下，往往我们对程序代码的一个小小的优化和改进，就能显著地提升程序的执行效率。

当然，枚举算法也可以枚举复杂的对象。但从简单的问题着手来掌握枚举的基本思想无疑是首要的。

实际上，枚举算法也是培养计算思维最直接的方式和手段。