前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯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;
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

可以看出，每次我们进行枚举选择的时候都是从头开始执行一次 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;        // 恢复现场
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
 

因为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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

带分数

题目要求

题目描述：

100 可以表示为带分数的形式：100 = 3 + $\frac{69258}{714}$

还可以表示为：100 = 82 + $\frac{3546}{197}$

注意特征：带分数中，数字 1∼9 分别出现且只出现一次（不包含 0）。

类似这样的带分数，100 有 11 种表示法。

输入格式：

一个正整数。

输出格式：

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围：

1 ≤ N < 10⁶

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

思路分析

我们可以用最暴力的思路：先全排列1 ~ 9，然后进行划分，把排列后的结果划分为三部分：a，b，c.然后根据公式判断是否满足：n = a + $\frac{b}{c}$，如果满足，我们就让 res ++，最终打印输出 res 即可，我们对上述进行一些优化：由 n = a + $\frac{b}{c}$ 可推出：n * c = a * c + b.故我们只需要枚举 a 和 c 的情况就可以计算出 b 的值，然后根据题目中所要求的：1 ~ 9 中所有的数字都必须且只能出现一次去判断是否合法，注意：N 的范围是小于 10⁶ 的，故我们的 a 的大小也必然是小于 10⁶的，故我们的第一个剪枝优化：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的个位数
}

  

 

  
1
  
2
  
3
  
4
  
5
 

那么在上述大框架的前提下，因为我们对于每个 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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122522807