蓝桥杯之递归与递推

递归

1. 递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

输入样例：

1
3

输出样例：

1
2
3
4
5
6
7
3
2
2 3
1
1 3
1 2
1 2 3

AC

一共 n 个数，即可以利用填坑的方法进行，从填 1 个坑到填 n 个坑。

选择填哪个坑都可以，比如第 1 个坑填入了 2 之后，第 2 个坑可以填 1（即非升序），也可填 3（即升序）

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 16;

int n;
int st[N]; // 状态，记录每个位置当前的状态：0表示还没考虑，1表示选它，2表示不选它

void dfs(int u) {
    if (u > n) {
        for (int i = 1; i <= n; i++) {
            if (st[i] == 1) {
                printf("%d ", i);
            }
            
        }
        puts("");
        return;
    }
    
    st[u] = 2;
    dfs(u + 1); // 第一个分支：不选
    st[u] = 0; // 恢复现场
    
    st[u] = 1;
    dfs(u + 1); // 第二个分支：选
    st[u] = 0;
}

int main() {
    cin >> n;
    
    dfs(1);
    
    return 0;
}

2. 递归实现排列型枚举

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

输入样例：

1
3

输出样例：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

AC

依然是选择填坑的方式，但后一个坑所填之数需要大于前一个坑里的数，因为题目要求字典较小的排在前面

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10;

int n;
int st[N]; // 0 表示还没方数，1~n表示放了哪个数
bool used[N]; // true表示已用过，false表示还未用过

void dfs(int u) {
    if (u > n) { // 边界
        for (int i = 1; i <= n; i++) { // 打印
            printf("%d ", st[i]);
        }
        puts("");
        
        return;
    }
    
    // 依次枚举每个分支，即当前位置可以填哪些数
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            st[u] = i;
            used[i] = true;
            dfs(u + 1);
            
            // 恢复现场
            st[u] = 0;
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    
    dfs(1);
    
    return 0;
}

3. 递归实现组合型枚举

从 1∼n1∼n 这 nn 个整数中随机选出 mm 个，输出所有可能的选择方案。

输入格式

两个整数 n,mn,m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(n−m)≤25

输入样例：

1
5 3

输出样例：

1
2
3
4
5
6
7
8
9
10
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

AC

依然选择填坑式，按从小到大的顺序填入。

例如，第一个坑填 1，则第二个坑可以填 2~5；若第二坑填 2，则第三个坑可以 3~5；

递归到第一个坑填 3 时，则第二个只能填 4，第三个只能填 5；

当第一个坑填 4 时，后续可用的数字不够，则结束。

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
#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) { // 已选购、够 m 个数
        for (int i = 1; i <= m; i++) { // 打印
            printf("%d ", 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;
}

4. 带分数

100100 可以表示为带分数的形式：

还可以表示为：

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

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

输入格式

一个正整数。

输出格式

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

数据范围

输入样例1：

1
100

输出样例1：

1
11

输入样例2：

1
105

输出样例2：

1
6

AC

将题目等式抽象成

依次递归从 1 开始递归 a，然后在递归 a 的同时，递归 c，b 则可以通过等式变形计算出来：

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10;

int n;
bool st[N], backup[N];
int ans;

bool check(int a, int c) {
    long long b = n * (long long )c - a * c; // 计算b
    
    if (!a || !b || !c) {
        return false;
    }
    
    // 因为我们要对这个判断是否出现的数组进行修改，但是原数组又不能变化，所以我们额外开一个数组进行使用，这样就可以达到判断且不会改变原数组的目的
    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; i <= 9; i++) { // 遍历一下，判断每个数
        if (!backup[i]) {
            return false;
        }
    }
    
    return true;
}

void dfs_c(int u, int a, int c) { // u表示我们已经用了几个数组
    if (u > 9) { // 如果已经把9个数用过了
        return;
    }
    
    if (check(a, c)) { // 如果满足要求
        ans++;
    }
    
    for (int i = 1; i <= 9; i++) { // 将c枚举一遍1~9
        if (!st[i]) {
            st[i] = true;
            dfs_c(u + 1, a, c * 10 + i); // 如果这个数没用过，那么我们就把它放在c的后面,继续dfs下一层
            st[i] = false;
        }
    }
}

void dfs_a(int u, int a) {
    if (a >= n) {
        return;
    }
    
    if (a) { // 如果a满足条件
        dfs_c(u, a, 0); // 递归一下c
    }
    
    for (int i = 1; i <= 9; i++) { // 枚举一下a
        if (!st[i]) {
            st[i] = true;
            dfs_a(u + 1, a * 10 + i); // 如果这个数没有被用过，那么我们就加上它，并且dfs下一层
            st[i] = false; // 恢复现场，回溯
        }
    }
}

int main() {
    cin >> n;
    
    dfs_a(0, 0); // 第一个0表示我们已经用了多少个数字,后面那个0表示我们当前的a是多少
    
    cout << ans << endl;
    
    return 0;
}

递推

1. 简单斐波那契

以下数列 0 1 1 2 3 5 8 13 21 ... 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0<N<46

输入样例：

1
5

输出样例：

1
0 1 1 2 3

AC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;

int main() {
    int a = 0, b = 1;
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cout << a << " ";
        
        int c = a + b;
        a = b;
        b = c;
    }
    
    return 0;
}

2. 费解的开关

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

1
2
3
4
5
10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

1
2
3
4
5
01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

1
2
3
4
5
01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

1
2
3
3
2
-1

AC

首先，每一行的暗灯都需要由下一行的灯去点亮。

枚举第一行的灯的所有情况，一共 2^5 = 32 种情况，不需要在意第一行的灯是灭是暗，只需把第一行的按法枚举一遍，也就是我们说的 “操作”，每个位置都有两种选择，按(用1表示)或者不按(用 0 表示)，遍历这 32 种操作引发的情况，每一次再通过 res = min(res, step); 把最小步数存一下，就能找到最优解

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
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 6;

char g[N][N], backup[N][N];
int dx[N] = {-1, 0, 1, 0, 0}, dy[N] = {0, 1, 0, -1, 0};

// 将 (x, y) 以及上下左右的灯都变成相反的状态：开->关，关->开
void turn(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int a = x + dx[i], b = y + dy[i];
        
        // 如果越界，则直接忽略
        if (a < 0 || a >= 5 || b < 0 || b >= 5) {
            continue;
        }
        
        g[a][b] ^= 1;
    }
}

int main() {
    int n;
    cin >> n;
    
    while (n--) {
        for (int i = 0; i < 5; i++) { // 按行输入
            cin >> g[i];
        }
        
        int res = 10;
        
        // 这里我们枚举了第一行的32种按法，不用管是亮是灭，把第一行所有情况都按一遍
        // 按每种情况的第一行，去遍历接下来的行
        // 枚举32种第一行的按法只是可能会减少步数，如果直接从第二行开始答案一定是固定的了，找不到最优解或者可能没有解

        for (int op = 0; op < 32; op++) {
            memcpy(backup, g, sizeof g); // 先备份，好还原进行下一次
            
            int step = 0;
            
            for (int i = 0; i < 5; i++) { // 先按一遍第一行（1表示按了，0表示没按）
                if (op >> i & 1) { // 数字2对应 00010，表示第2个位置的按了一下
                    step++;		   // 00010 >> 1 & 1 是1，所以 turn(0, 1)即第一行第二个位置
                    turn(0, i);
                }
            }
            
            for (int i = 0; i < 4; i++) { // 在第一行按过后，按2，3，4行
                for (int j = 0; j < 5; j++) { 
                    if (g[i][j] == '0') { // 如果第一行的某个位置的灯是关的
                        step++;
                        turn(i + 1, j);
                    }
                }
            }
            
            bool dark = false;
            for (int j = 0; j < 5; j++) { // 判断最后一行的灯状态
                if (g[4][j] == '0') { // 如果有关着的，直接break
                    dark = true;
                    break;
                }
            }
            
            if (!dark) { // 如果最后一行全亮
                res = min(res, step); // res取上次res和此次按开关的次数的最小值
            }
            memcpy(g, backup, sizeof g); // 复原
        }
        
        if (res > 6) { // 如果超过6次
            res = -1;
        }
        cout << res << endl;
    }
    
    return 0;
}

3. 翻硬币

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1：

1
2
**********
o****o****

输出样例1：

1
5

输入样例2：

1
2
*o**o***o***
*o***o**o***

输出样例2：

1
1

AC

从左向右依次遍历，与最终目标状态进行比较，只要不同就翻转当前和下一个相邻的硬币

设定翻转相邻的硬币为自身和下一个硬币，也不可反转两次，否则等于未操作，无意义。设定向右翻转的原因是该题的解法是唯一的，不存在多种情况，只需挨个遍历就行。

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

char orgin[N], aim[N];

void turn(int i) {
    if (orgin[i] == '*') { // 若当前为*，则需要翻转成o
        orgin[i] = 'o';
    }
    else { // f
        orgin[i] = '*';
    }
}

int main() {
    cin >> orgin >> aim; 
    
    int n = strlen(orgin); // 获取长度
    
    int res = 0;
    for (int i = 0; i < n; i++) { // 依次遍历
        if (orgin[i] != aim[i]) { // 如果不同
            turn(i), turn(i + 1); // 翻转当前的位置和下一个位置的硬币
            res++; // 次数+1
        }
    }
    
    cout << res << endl;
    
    return 0;
}