递归与递推

本文最后更新于:7 个月前

递归主要在以下三种题型有所体现

  1. 递归实现指数型枚举
  2. 递归实现排列型枚举
  3. 递归实现组合型枚举

分析问题-提取模型-方法尝试-代码实现

这四步是解决递归问题的基本流程。


一. 递归实现指数型枚举

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

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

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

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

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

数据范围

1≤ n≤ 15

输入样例:

1
3

输出样例:

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

首先理清题意,可以将问题简化为计算n元集的子集,所以关键在于考虑每个位置上的数是否存在,由于数有一定顺序,所以我们可以判别这是一个递归问题。

递归问题的关键在于实现一个递归搜索树,所以在明确本题要求后,我们可以进行一个逻辑推演,在白纸上画出如下树状图:

有了树状图的帮助,我们可以更便捷地得出每个位置上的数的选择规律。这有助于我们确定深度搜索算法的body部分。

代码如下:

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

using namespace std;

int n; // 全局变量,表示数的范围
const int N = 16; // 确定数组容量
int st[N]; // 状态判断数组,指数型枚举问题的关键在于确定某个数存在与否所以我们只需用一个状态判别数组对数的状态进行确定,第i个数即对应数i

void dfs(int u) // 深度优先搜索,u表示当前需要确定的数的位置
{
if(u > n) // 底层判别(即当前位置已经越界)
{
for(int i = 1; i <= n; i++)
{
if(st[i] == 1) printf("%d ", i); // 如果枚举已经到了尽头,我们就将所有存在的数依次输出
}
puts(""); // 代表换行
return;
}

// 如果枚举没到尽头,对当前叶子层进行分类讨论
st[u] = 1; // 若当前位置对应数存在
dfs(u+1); // 进入u+1层判别
st[u] = 0; // 恢复现场, 这也体现了枚举的关键——“彼此独立,组成完整”。

st[u] = 2; // 若当前位置对应数不存在
dfs(u+1);
st[u] = 0;
}

int main()
{
cin >> n;
dfs(1); // 从第1个位置数开始确定
return 0;
}

二. 递归实现排列型枚举

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

输入格式

一个整数 n。

输出格式

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

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

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

数据范围

1≤ n≤ 9

输入样例:

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

相比指数型枚举,排列型枚举有了顺序的要求,对位置的讨论便成了关键。由此我使用两个数组作为主要操作工具,分别记录每种方案的排序方式和已经使用过的数。整体代码逻辑并没有太大变化——即每一层的操作+结果操作。

代码如下:

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

using namespace std;

const int N = 11;
int n, way[N], st[N];

void dfs(int u)
{
if(u > n)
{
for(int i = 1; i <= n; i++) printf("%d ", way[i]);
puts(""); // 相当于回车
return;
}

for(int i = 1; i <= n; i++)
{
if(!st[i]) // 从小到大遍历,如果该数没有被用过,则纳入该层讨论范围
{
st[i] = 1;
way[u] = i;
dfs(u+1);
st[i] = 0;
}
}
}

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

三. 递归实现组合型枚举

从 1∼n这 n个整数中随机选出 m 个,输出所有可能的选择方案。

输入格式

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

输出格式

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

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

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

数据范围

n>0 ,
0≤m≤n ,
n+(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

组合型枚举的关键在于组合的种类,不能存在重复。实现的主要工具为一个状态判断数组。

由于每一层可选的数有不同的变化,所以需要添加一个参数start来确定计数起点。

代码如下:

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

using namespace std;

int m, n;
const int N = 30;
int way[N];

void dfs(int start, int u)
{
if(u > m)
{
for(int i = 1; i <= m; i++) printf("%d ", way[i]);
puts("");
return;
}

if(m + start - u <= n) // 剪枝操作,去掉无效分支
{
for(int i = start; i <= n; i++)
{
way[u] = i;
dfs(i+1, u+1);
}
}
}

int main()
{
scanf("%d%d", &n, &m);
dfs(1, 1);
return 0;
}