前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第一讲：递归【习题】
递归【例题】讲解见博客：蓝桥杯第一讲–递归【例题】
本篇博客所包含习题有：
👊递归实现组合型枚举
👊带分数
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
递归实现组合型枚举
题目要求
题目描述：
从 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
思路分析
我们在例题中讲过使用递归去实现全排列，本题是去实现组合，如何从全排列变成组合呢？我们来观察一下全排列的核心代码：
for (int i = 1; i <= n; i ++ ) if (!used[i]) // 如果数字i没有被用过 { used[i] = true; state[u] = i; dfs(u + 1); // 恢复现场: used[i] = false; state[u] = 0; }
可以看出，每次我们进行枚举选择的时候都是从头开始执行一次 for 循环，去判断是否有遗漏的情况，比如我们第一位选择的是 9，那么显然第二位可以选择：1，2，3.故我们每次 for 循环都是从1开始枚举，但是对于组合的情况，1 2 9 和 9 1 2是一种情况，故我们在枚举的时候就不能每次 for 循环还是和排列一样从头开始，而是从 start 开始：
for (int i = start; i <= n; i ++ ) { state[u] = i; dfs(u + 1, i + 1); state[u] = 0; // 恢复现场 }
因为start 是单调增加的：start从1开始直至n，故这样处理之后就会舍弃掉冗余。
下述代码还涉及到剪枝操作来优化代码的执行效率，不进行剪枝也是可以AC的，剪枝部分的解释详见代码。
代码
#include <iostream> #include <algorithm> using namespace std; const int N = 30; int state[N]; int n, m; void dfs(int u, int start) // 目前该选第u个数,可供挑选的数字从start开始 { if (u - 1 + n - start + 1 < m) return; //剪枝 //当前该选第u个数,故已选u - 1个数,从start到n共n - start + 1个数 //如果u - 1 + n - start + 1都要小于m的话,证明无解 //按照题目例子说明:4作为开头第一个数不可能有符合题意的答案 //因为把4之后所有的数:5(仅有5)全部选择上也只有两位数小于三位数 if (u > m) { for (int i = 1; i <= m; i ++ ) cout << state[i] << ' '; puts(""); return; } for (int i = start; i <= n; i ++ ) { state[u] = i; dfs(u + 1, i + 1); state[u] = 0; // 恢复现场 } } int main() { cin >> n >> m; dfs(1, 1); return 0; }
带分数
题目要求
题目描述：
100 可以表示为带分数的形式：
还可以表示为：
注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
输入格式：
一个正整数。
输出格式：
输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围：
1 ≤ N < 106
输入样例1：
100
输出样例1：
11
输入样例2：
105
输出样例2：
6
思路分析
我们可以用最暴力的思路：先全排列1 ~ 9，然后进行划分，把排列后的结果划分为三部分：a，b，c.然后根据公式判断是否满足：n = a +b/c,如果满足，我们就让 res ++，最终打印输出 res 即可，我们对上述进行一些优化：由 n = a +b/c,可推出：n * c = a * c + b.故我们只需要枚举 a 和 c 的情况就可以计算出 b 的值，然后根据题目中所要求的：1 ~ 9 中所有的数字都必须且只能出现一次去判断是否合法，注意：N 的范围是小于 106 的，故我们的 a 的大小也必然是小于 106的，故我们的第一个剪枝优化：if (a >= n) return;，显然 a 不可能是0（因为数字只能是从1 ~ 9），故我们的第二个剪枝：if (a) dfs_c(u + 1, a, 0);我们在递归的过程之中计算 a 和 c 的值，比如我们当前的值为 a，现在给数字 a 增加一个单位长度，选择的数为 i，故 a = a * 10 + i，c 也同理：c = c * 10 + i，最终判断 b 是否合法，需要把 b 的每一位都拆下来，这一步骤的代码需要读者牢记：
while (b) { int x = b % 10; // x就是b的个位数 b /= 10; // 删除b的个位数 }
那么在上述大框架的前提下，因为我们对于每个 b 都需要进行终值判断，故判断前先拷贝一份 used 数组（因为会对 used 数组进行修改），如果 b 中含有数字 0 或者 b 中的某个数字在 used 数组中已经被用过了，就返回 false，否则将该数加入到拷贝数组 back 中，最后需要判断是否 1 ~ 9 都使用过了，如果有没有使用过的数，就返回false，最终返回true
代码
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 10; typedef long long LL; int n, res; bool used[N], back[N]; bool check(int a, int c) { LL b = (LL)c * n - (LL)a * c; memcpy(back, used, sizeof used); while (b) { int x = b % 10; b /= 10; if (!x || back[x]) return false; back[x] = true; } for (int i = 1; i <= 9; i ++ ) if (!back[i]) return false; return true; } void dfs_c(int u, int a, int c) { if (u > 9) return; if (check(a, c)) res ++; for (int i = 1; i <= 9; i ++ ) if (!used[i]) { used[i] = true; dfs_c(u + 1, a, c * 10 + i); used[i] = false; } } void dfs_a(int u, int a) { if (a >= n) return; if (a) dfs_c(u + 1, a, 0); for (int i = 1; i <= 9; i ++ ) if (!used[i]) { used[i] = true; dfs_a(u + 1, a * 10 + i); used[i] = false; } } int main() { cin >> n; dfs_a(1, 0); //从第一个位置开始,a的初始值为0 cout << res << endl; return 0; }
