枚举法的使用

喜欢ヅ旅行 2024-04-01 09:02 69阅读 0赞

#### 一、介绍 ####

枚举法，也称为列举法、穷举法，是暴力策略的具体体现。枚举法的基本思想是: 逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。

#### 二、枚举模式 ####

1）区间枚举

对于有明确范围要求的实际案例，通过枚举循环的上下限控制枚举区间，而在循环体中完成各个运算操作，然后根据所求解的具体条件，应用选择结构实施判别与筛选，求得所要求的解。

n = 0
    
    for(k = 区间下限;k <= 区间上限;k++){
    
        运算操作序列
    
        if(约束条件){
    
              print(满足要求的解);
    
              n++;
    
        }
    
    }
    
    print(解的个数);

2) 递增枚举

有些问题没有明确的范围限制，可根据问题的具体情况试探性地从某一起点开始增值枚举，对每个数进行操作与判别，若满足条件则输出结果；

k = 0;
    
    while(true){
    
        k++;
    
        运算操作序列
    
        if(约束条件){
    
            print(满足要求的解);
    
            return;
    
        }
    
    }

枚举的实施步骤:  
1) 根据问题的具体情况确定枚举量(简单变量或数组)  
2) 根据问题的具体清空确定枚举范围，设置枚举循环  
3) 根据问题的具体要求确定筛选(约束)条件  
4) 设计枚举程序并运行、调试，对运行结果进行分析与讨论。

#### 三、实例 ####

问题描述：在下面的算式中，添加“+”、“-”，“\*”，“/”,4个运算符，使得这个式子成立。  
5 5 5 5 5=5  
算法分析：  
上述式子左侧有5个数字，一共需要4个运算符。根据题目要求，两个数字之间的运算符只能有4种选择。在具体编程时，可以通过循环来填入各种运算符，然后再判断算式左侧的值是否等于右侧的值。并保证，当填入的是除号时，则右侧的数不能为0，并且乘除的优先级高于加减的优先级。

这道题使用的是暴力法，也就是枚举，让我们填入四个运算符，并且根据运算符的先后顺序进行运算求解最后的答案

第一步：要枚举出所有符合条件的运算符号，这里最主要的是/号，后面那个数字不得为0，筛选出运算符号的组合放入数组中，这里应当用数字来代替四个运算符号 1-4分别代表+ - \* /

第二步：首先得话定义左和右两个值，这里注意的是应当设置浮点型，可能中途运算会有小数存在，避免像1/5得到结果为0，实际为0.2

左右两个值分别代表的是前一次的左右值，其中最巧妙的是进行判断当前运算符的时候，前面那次运算会在这次碰到的运算符的时候进行对应的操作  
有三个数 x y z  
例如：left，right分别保存着x,y,此时运算到y和z中间是 \* 运算符，这时候会先进行y和z的运算，left并不动 ，此时left = x,right = x\*y

若是y和z之间是加减运算符时，left = x±y right = z  
left 和right起到了根据运算符分别进行不同的操作

第三步：四次运算符都结束时，还是会有剩余的left和right左右两部分，所以 额外还要将left和right运算一次，最后在进行判断是否等于要求的值，并且打印出来  
题解：

#include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    {
    	int i[5],num[6];  //每个坐标下范围为1-4,1->+  2->-  3->* 4->/ 
    	char op[5] = {' ','+','-','*','/'};  //这里存放的+，-，*，/   从下标1开始 
    	int count=0,result;
    	
    	printf("请输入5个带空格的数：");
    	for(int j=1;j<=5;j++)
    		scanf("%d",&num[j]);
    	printf("输入结果：");
    	scanf("%d",&result);   //结果 
    	
    	for(i[1]=1;i[1]<=4;i[1]++){    //四种情况 
    		if(i[1]<4||num[2]!=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){
    							
    							float left=0;   //初始左边值为0 
    							float right = num[1]; //右边的值为第一个数 
    							int sign = 1; //表示前一个符号的正负
    							
    							//此时进行遍历存放四个运算符的i数组
    							for(int j=1;j<=4;j++){
    								switch(op[i[j]]){
    									case '+':
    										//如果是正的话，用前一个left进行运算，之后right等于后面的值
    										left = left+sign*right;
    										sign = 1;   
    										right = num[j+1];
    										break;
    									case '-':
    										//如果是负的话，也是用前一个left运算，之后left为
    										left = left+sign*right;
    										sign = -1;
    										right = num[j+1];
    										break;
    									case '*':
    										right = right*num[j+1];
    										break;
    									case '/':
    										right = right/num[j+1];
    										break;
    								}
    							}
    							//判断最后运算是否等于结果，打印输出
    							if(left+sign*right == result){
    								count++;
    								printf("%d:",count);
    								for(int j=1;j<=4;j++){
    									printf("%d%c",num[j],op[i[j]]);
    								}
    								printf("%d",num[5]);
    								printf("=%d\n",result);
    							} 
    							
    						}
    					}
    				}
    		} 
    		}
    	}
    	if(count == 0){
    		printf("没有符合的式子!"); 
    	} 
    	return 0;
    }

![bb5dec41258a4ded8292238d82e2789f.png][]

参考：

[八大算法思想（一）------------------枚举算法\_M李丽的博客-CSDN博客\_枚举算法][------------------_M_-CSDN]

[填写运算符问题 暴力枚举\_长路 ㅤ   的博客-CSDN博客\_填写运算符问题][_ _-CSDN]

[基础算法枚举法\_刘阿怪的博客-CSDN博客\_枚举法的基本步骤][-CSDN]

[bb5dec41258a4ded8292238d82e2789f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f4a3f25fd0e4449cad632532ef3f871b.png
[------------------_M_-CSDN]: https://blog.csdn.net/qq_32211827/article/details/72970404?spm=1001.2101.3001.6650.2&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-2-72970404-blog-101211788.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~Rate-2-72970404-blog-101211788.pc_relevant_default&utm_relevant_index=5
[_ _-CSDN]: https://changlu.blog.csdn.net/article/details/104843693
[-CSDN]: https://blog.csdn.net/weixin_42166771/article/details/101211788