文章目录
一、递归实现指数型枚举
1、1 题目描述
1、2题解关键思路与解答
二、递归实现排列型枚举
2、1题目描述
2、2 题解关键思路与解答
三、递归实现组合型枚举
3、1题目描述
3、2题解关键思路与解答
四、带分数
4、1题目描述
4、2题解关键思路与解答
五、费解的开关
5、1题目描述
5、2题解关键思路与解答
六、总结
标题：蓝桥杯——递归与递推习题训练
作者：@Ggggggtm
寄语：与其忙着诉苦，不如低头赶路，奋路前行，终将遇到一番好风景
蓝桥杯比赛只有四十天左右啦，最近会按照模块更新一些有关蓝桥杯算法题。学习算法不仅仅是为了参见比赛，更是以后找工作的一个敲门砖。废话不多说，我们直接看题。
一、递归实现指数型枚举
1、1 题目描述
题目来源：《算法竞赛进阶指南》
题目难度：简单
题目描述：
从1∼n这n个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式：
输入一个整数n。
输出格式：
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围：
1≤ n≤ 15
输入样例：
3输出样例：
322 311 31 21 2 3
1、2题解关键思路与解答
由于上述题目是要求递归，我们可以通过开一个数组纪录是否选择该数组（0表示还没对该数字进行操作，1表示选择该数字，2表示不选择该数字）。这样通过递归，我们就可以很好的枚举出每一种情况。我们结合代码一起理解一下。
#includeusing namespace std;const int N=16;int n;int state[N];void dfs(int a){ if(a>n) { for(int i=1;i>n; dfs(1); return 0;}二、递归实现排列型枚举
2、1题目描述
题目来源：《算法竞赛进阶指南》
题目难度：简单
题目描述：
把1∼n这n个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式：
一个整数n。
输出格式：
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围：
1≤n≤9
输入样例：
3输出样例：
1 2 31 3 22 1 32 3 13 1 23 2 1
2、2 题解关键思路与解答
这个题的关键就在于是排列。通过递归枚举的方法实现排列，我们需要开两个数组：一个数组是记录还数字是否被使用过（0是未被使用，1是已经使用），另一个数组记录所排序的数字。题目中还要求了字典序，正常从小到大递归就已经是字典序较小的排在前面。我们直接看代码。
#includeusing namespace std;const int N=10;int n;int state[N];int used[N];void dfs(int a){ if(a>n) { for(int i=1;i<=n;i++) printf("%d ",state[i]); puts(""); return; } for(int i=1;i>n; dfs(1); return 0;}三、递归实现组合型枚举
3、1题目描述
题目来源：《算法竞赛进阶指南》
题目难度：简单
题目描述：
从1∼n 这n个整数中随机选出m个，输出所有可能的选择方案。
输入格式：
两个整数n,m,在同一行用空格隔开。
输出格式：
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如
1 3 5 7排在1 3 6 8前面）。数据范围:
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
3、2题解关键思路与解答
组合与排列十分相似，但又有些不同。组合特殊的是 1，2，3 与 2，1，3 与 3，2，1相同的，算是一种组合类型。题目中要求的同一行内的数升序排列。怎么定义升序呢？我们可以人为的选数字为升序。我们可以把整体的升序看成局部的升序，只要是满足后一个数比前一个数大即可。
#include#include#includeusing namespace std;int n,m;const int N=26;int way[N];void def(int a,int start){ if(a-1+n-start+1<m) //剪枝 return; if(a==m+1) { for(int i=1;i<=m;i++) { printf("%d ",way[i]); } printf("\n"); return; } for(int i=start;i>n>>m; def(1,1); return 0;}四、带分数
4、1题目描述
题目来源：第四届蓝桥杯省赛C++B/C组
题目难度：中等
题目描述：
100可以表示为带分数的形式：100=3+69258 / 714
还可以表示为：100=82+3546 / 197
注意特征：带分数中，数字1∼9 分别出现且只出现一次（不包含0）。
类似这样的带分数，100有 11种表示法。
输入格式:
一个正整数。
输出格式:
输出输入数字用数码1∼9不重复不遗漏地组成带分数表示的全部种数。
数据范围:
1≤N<106
输入样例1：
100输出样例1：
11输入样例2：
105输出样例2：
6
4、2题解关键思路与解答
我们可以把带分数的形式看成一个公式：n = a +b / c 。也就是a、b和c 的数字 中1∼9 分别出现且只出现一次。那我们就可以想枚举a和c的情况，然后通过公式 b = c*n-c*a 计算出b的值。再把b的每一位拿出来看看时候符合题目所要求的情况。我们直接结合代码一起理解一下。
#include#include#include#includeusing namespace std;const int N=12;int n,ans;bool st[N],backup[N];bool check(int a,int c){ long long b=n*(long long)c-a*c; memcpy(backup,st,sizeof(st)); while(b) { int x=b%10; b/=10; if(!x || backup[x]) return false; backup[x]=true; } for(int i=1;i9) return; if(check(a,c)) ans++; for(int i=1;i=n) return; if(a) dfs_c(u,a,0); for(int i=1;i>n; dfs_a(0,0); cout<五、费解的开关
5、1题目描述
题目来源：《算法竞赛进阶指南》
题目难度：中等
题目描述：
你玩过“拉灯”游戏吗？
25盏灯排成一个5×5 的方形。
每一个灯都有一个开关，游戏者可以改变它的状态。
每一步，游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字1表示一盏开着的灯，用数字0表示关着的灯。
下面这种状态：
1011101101101111000011011在改变了最左上角的灯的状态后将变成：
0111111101101111000011011再改变它正中间的灯后状态将变成：
0111111001110011010011011给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。
输入格式：
第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。
以下若干行数据分为n组，每组数据有5行，每行5个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式：
一共输出n行数据，每行有一个小于等于66的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出−1。
数据范围：
0<n≤500
输入样例：
3001110101110001110101110011101111011111011111111110111111111111111111111111输出样例：
32-1
5、2题解关键思路与解答
由于每个灯是数字1表示一盏开着的灯，用数字0表示关着的灯，我们就一行一行就行看。一行有五个灯，我们把代表灯的状态的数字看作一个数的二进制位。也就是一行有32种情况。整体的思路就是下一行影响上一行，我们需要做的是首先枚举第一行的32种情况，接着调整完前四行，最后看第五行是否为全亮即可。我们直接看代码：
#include#include#includeusing namespace std;const int N=6;char g[N][N],backup[N][N];int dx[5]={-1,0,1,0,0},dy[5]={0,0,0,-1,1};void turn(int x,int y){ for(int i=0;i<5;i++) { int a=x+dx[i],b=y+dy[i]; if(a4 || b4) continue; g[a][b]^=1; }}int main(){ int n; cin>>n; while(n--) { int res=10; for(int i=0;i>g[i]; for(int op=0;op<32;op++) { int step=0; memcpy(backup,g,sizeof(g)); for(int i=0;i>i&1) { step++; turn(0,i); } } for(int i=0;i<4;i++) { for(int j=0;j<5;j++) { if(g[i][j]=='0') { step++; turn(i+1,j); } } } bool back=false; for(int i=0;i6) res=-1; cout<<res<<endl; } return 0;}六、总结
通过上面的习题练习，我们发现用递归去枚举也很简单。同时，我们也要掌握上面的递归枚举的思路和方法。在很多情况下，我们可以多开数组来进行记录或者操作，会给我们带来很大的便利。
递归与递推的练习就到这里，希望以上内容对你有所帮助。