AcWing 92. 递归实现指数型枚举
从1～n这n个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。
本题有自定义校验器(SPJ)，各行（不同方案)之间的顺序任意。
数据范围
1≤n≤15
输入样例：
3
输出样例：
3 2 2 3 1 1 3 1 2 1 2 3
方法一：暴力
对于每个数都有选or不选两种，所以有2^n种可能
#include <iostream> using namespace std; int n; int main(){ cin>>n; //1<<n位表示2^n可能 for(int i=0;i<(1<<n);i++){ for(int j=0;j<n;j++){ //获得其第j位的数字，若是1就输出 if(i>>j&1) printf("%d ",j+1); } printf("\n"); } }
方法二：递归
#include <iostream> using namespace std; const int N=20; int n; bool vis[N]; //判断选还是不选 void DFS(int u) //第几层就是筛选第几个数字 { if(u>n) //不可以有等号，如果有等号会少一层递归，即最后一层无法递归 { for(int i=1;i<=n;i++)//从1到n选择 if(vis[i]) //把选择的数打印出来 cout<<i<<" "; cout<<endl; return ; } else { vis[u]=true;//选这个数字 DFS(u+1); vis[u]=false;//不选这个数字 DFS(u+1); } } int main() { cin>>n; DFS(1); //从1开始选择，到n结束，所以不能从0开始； return 0; }
上升序列：
#include<iostream> using namespace std; int n; int a[20]; bool st[20]; //pos为当前枚举到的坑数，start表示只能从start开始找数，一共填tar个坑 void dfs(int pos,int start,int tar) { if(pos==tar+1) { for(int i=1;i<=tar;i++) cout<<a[i]<<" "; cout<<endl; return ; } for(int i=start;i<=n;i++)//start保证升序 { a[pos]=i; dfs(pos+1,i+1,tar); } } int main() { cin>>n; for(int i=0;i<=n;i++) dfs(1,1,i); return 0; }
AcWing 93. 递归实现组合型枚举
从1～n这n个整数中随机选出m个，输出所有可能的选择方案。
输入格式
两个整数n, m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1368前面)。
数据范围n > 0 ，0 <m ≤n ,n＋(n -m)≤25
输入样例：
5 3
输出样例：
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; const int N=30; int n,m; int way[N]; void dfs(int u,int start) { //if (u + n - start < m) return; // 剪枝 if(u==m+1) { for(int i=1;i<=m;i++) cout<<way[i]<<" "; puts(""); return ; } for(int i=start;i<=n;i++) { way[u]=i; dfs(u+1,i+1); way[u]=0; } } int main() { cin>>n>>m; dfs(1,1); return 0; }
AcWing 94. 递归实现排列型枚举
把1 ～n这n个整数排成一行后随机打乱顺序，输出所有可能的次序。输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
输入样例：
3
输出样例：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
递归
#include<iostream> using namespace std; const int N = 10; int path[N];//保存序列 int state[N];//数字是否被用过 int n; void dfs(int u) { if(u > n)//数字填完了，输出 { for(int i = 1; i <= n; i++)//输出方案 cout << path[i] << " "; cout << endl; } for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n { if(!state[i])//如果数字 i 没有被用过 { path[u] = i;//放入空位 state[i] = 1;//数字被用，修改状态 dfs(u + 1);//填下一个位 state[i] = 0;//回溯，取出 i } } } int main() { cin >> n; dfs(1); return 0; }
非递归类型枚举：
C++STL中全排列函数next_permutation
全排列就是一次对对象序列或值序列的重新排列。例如，“ABC”中字符可能的排列是："ABC", "ACB", "BAC", "BCA", "CAB", "CBA"
next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。
另外，需要强调的是，next_permutation（）在使用前需要对欲排列数组按升序排序，否则只能找出该序列之后的全排列数。
#include <bits/stdc++.h> using namespace std; const int N=11; int n,a[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) a[i]=i; do { for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; }while(next_permutation(a+1,a+1+n)); return 0; }
AcWing 1209. 带分数
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
方法一： 暴力
思路：
全排列1到9
将1-9分为三段
#include<iostream> #include<algorithm> using namespace std; int n; int a[10]={1,2,3,4,5,6,7,8,9}; int js(int l,int r) { int sum=0; for(int i=l;i<=r;i++) { sum=sum*10+a[i]; } return sum; } int main() { cin>>n; int cnt=0; do { for(int i=0;i<7;i++) { for(int j=i+1;j<8;j++) { int a=js(0,i); int b=js(i+1,j); int c=js(j+1,8); if(n*c==a*c+b) cnt++; } } }while(next_permutation(a,a+9)); cout<<cnt; return 0; }
方法二：
#include<iostream> using namespace std; const int N = 20; int shu[N];//存放全排列数字 bool st[N];//数字是否出现 int n;//输入一个数字，验证符合的数字个数 int cnt;//符合条件的数字个数 //验证一个排列是否符合 void yan() { int a = 0,b = 0, c = 0; //分成三段 for(int i = 2; i<9 ; i++) { for(int j = i+1 ; j<10 ; j++) { a = 0,b = 0,c = 0;//重新验证新数字 for(int x = 1 ; x < i ; x++) a = a * 10 + shu[x] ; for(int y = i ; y < j ; y++) b = b * 10 + shu[y] ; for(int z = j ; z < 10; z++) c = c * 10 + shu[z] ; //等式要符合，并且要是b和c能整除 if(n == a + (b / c) && b % c == 0) cnt++; } } } void dfs(int u) { //处理边界 if(u == 10) { //进行验证数字 yan(); return ; } //枚举1 - 9 不重复的数字 for(int i = 1 ; i<10 ; i++) { if(!st[i]) { st[i] = true; shu[u] = i; dfs(u+1);//递归 st[i] = false;//恢复现场 } } } int main() { cin>>n; dfs(1);//从1开始 cout<<cnt;//输出符合的个数 return 0; }
AcWing 1208. 翻硬币
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：**oo***oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作。
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。
输出格式
一个整数，表示最小操作步数
数据范围
输入字符串的长度均不超过100。
数据保证答案一定有解。
输入样例1：
********** o****o****
输出样例1：
5
输入样例2：
*o**o***o*** *o***o**o***
输出样例2：
1
#include<iostream> #include<cstring> using namespace std; char ks[110],js[110]; void turn(int i) { if(ks[i]=='*') ks[i]='o'; else ks[i]='*'; } int main() { cin>>ks>>js; int n=strlen(ks); int bs=0; for(int i=0;i<n;i++) { if(ks[i]!=js[i]) { turn(i); turn(i+1); bs++; } } cout<<bs; return 0; }
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)