个人主页:仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客
专题分栏:算法_仍有未知等待探索的博客-CSDN博客
目录
一、前言
二、递归指数型枚举
1、题目信息
题目描述
输入格式
输出格式
样例
提示
2、解析
3、代码
一、前言
之前进行枚举的时候,都是进行暴力枚举的策略,将所用可能性都枚举一遍以获得最优解,但是枚举全部元素的效率如同愚公移山,无法应付数据范围稍大的情形。其算法的主要策略是跳过一些无效状态,降低问题的规模。
二、递归指数型枚举
1、题目信息
题目链接:U127142 指数型枚举 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
样例
样例输入
```
3
```样例输出
```
1 2 3
1 2
1 3
1
2 3
2
3
```提示
1≤n≤15
2、解析
如下图是整个程序的思路,n=3,代表要求 n = 3 的方案数。首先我们要先选第一个数,用一个数组进行存储这位数到底选还是不选。如果选的话,就接着往下一位数进行继续判断,知道要判断的位数大于n,代表结束。然后开始进行回溯。
下图我只对前一半的运行步骤进行了标号,另一半和这个一样。
3、代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 20;
int n;//枚举的位数
int st[N];//存储枚举的位数的信息(某位数是否进行了选择)
void bfs(int x){
//如果x>n的话,说明枚举选择结束,接着就是输出所选的组合
if(x>n){
//选n位数,所以循环n次
for(int i=1;i<=n;i++){
//如果为1,代表该数选上了,i下标其实就是要存储的数
if(st[i]==1){
printf("%d ",i);
}
}
printf("\n");
return;
}
//选x位的数
st[x]=1;//1代表选上了
bfs(x+1);//进行接着往下递归
//其实不写也没事,不过写上的话思路更加的完整
st[x]=0;//回溯,把存储状态的数组进行恢复
//不选x位的数
st[x]=2;//2代表了没选上
bfs(x+1);//进行接着往下递归
//其实不写也没事,不过写上的话思路更加的完整
st[x]=0;//回溯,把存储状态的数组进行恢复
}
int main(){
cin>>n;
bfs(1);
return 0;
}
谢谢大家的支持!