递归实现指数型枚举（递归）
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
|
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> num;
void calc(int u)
{
if(u == n + 1)
{
for(auto a : num) cout << a << ' ';
cout << endl;
return;
}
num.push_back(u);
calc(u + 1);
num.pop_back();
calc(u + 1);
}
int main()
{
cin >> n;
calc(1);
return 0;
}
|
按照朴素做法来思考，每个数字都有选和不选两个方案。共2^n^个数字，所以是指数枚举。
所以，我们可以使用递归，每次枚举”选“和“不选”两个分支。
由于C语言函数调用是通过栈来实现的，所以这个相当于深度优先搜索（DFS）。
即先处理全部不选的情况，然后处理选一个的情况，选完后恢复现场。继续处理其它情况。
这就是递归的强大之处，将问题分为若干小问题，使用一个函数不断调用进行求解。
递归实现组合型枚举（递归）
只需在指数型枚举加入下列条件即可：
1
2
|
if(num.size() > m || num.size() + (n - u + 1) < m) return;
|
这个操作也叫做搜索算法的剪枝，后面会讲解。
即：遇到不可能的答案，直接回溯，不再继续向下递归寻找。
通过这个优化操作，将上面的O(2^n^)降至O($C_n^m$)。
递归实现排序型枚举（递归）
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>
using namespace std;
const int N = 9;
int n, k;
int num[N];
bool choose[N];
void calc(int u)
{
if(u == n + 1)
{
for(int i = 0; i < n; i++) cout << num[i] << ' ';
cout << endl;
return;
}
for(int i = 1; i <= n; i++)
{
if(choose[i]) continue;
choose[i] = true;
num[k++] = i;
calc(u + 1);
k--;
choose[i] = false;
}
}
int main()
{
cin >> n;
calc(1);
return 0;
}
|
一共n!种情况，在每次递归中，把所有可用的数作为下一个数，然后求解剩余n-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
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
|
#include <iostream>
#include <cstring>
using namespace std;
int T;
char g[5][5];
char backUp[5][5];
int dx[5] = { -1, 0, 1, 0, 0 }, dy[5] = { 0, 1, 0, -1, 0 };
void turnOn(int x, int y)
{
for (int i = 0; i < 5; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a > 4 || b < 0 || b > 4) continue;
g[a][b] ^= 1;
}
}
int calc()
{
int ans = 0x3f3f3f3f;
for (int k = 0; k < 32; k++)
{
memcpy(backUp, g, sizeof g);
int step = 0;
for (int i = 0; i < 5; i++)
{
if (k >> i & 1) turnOn(0, i), step++;
}
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 5; j++)
{
if (g[i][j] == '0') turnOn(i + 1, j), step++;
}
}
bool allLight = true;
for (int i = 0; i < 5; i++)
{
if (g[4][i] == '0')
{
allLight = false;
break;
}
}
if (allLight) ans = min(ans, step);
memcpy(g, backUp, sizeof backUp);
}
if (ans > 6) return -1;
else return ans;
}
int main()
{
cin >> T;
while (T--)
{
for (int i = 0; i < 5; i++)
for (int j = 0; j < 5; j++)
cin >> g[i][j];
cout << calc() << endl;
}
return 0;
}
|
比较有意思的一道题。给你一个5x5的矩阵，0代表关灯，1代表开灯。
每次开灯会导致上下左右和中间五个位置的开关变动（0->1，1->0）。
问能不能在6次操作内全部打开，若能，输出最少需要多少步操作。
很容易发现：
若第一行固定，并且第一行某个位置是数字是0，则第二行必定需要点击这个0对应的列的位置。
只有这样，才能在不影响第一行其它位置的情况下，将这个0修改为1。
以此类推，第i行确定，则第i+1行也就能随之确定。
因此，我们可以将第一行所有点击方案枚举出来，共2^5^ = 32种可能。
然后基于第一行每种可能的方案，递归出后一行直至最后一行的值。
此时，只需要判定最后一行是否全为1。
注意：有一个小细节，g[a][b] ^= 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
|
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int d[N], f[N];
int main()
{
d[1] = 1;
for(int i = 2; i <= 12; i++)
{
d[i] = 2 * d[i - 1] + 1;
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
for(int i = 1; i <= 12; i++)
{
for(int j = 0; j < i; j++)
{
f[i] = min(f[i], f[j] * 2 + d[i - j]);
}
}
for(int i = 1; i <= 12; i++) cout << f[i] << endl;
return 0;
}
|
汉诺塔问题，递推思想。简单的汉诺塔是有三个塔组成的。
每次移动的最优方案是：将前n-1个盘子移动到另一座塔，然后将第n个盘子移动，最后将n-1个放至最上面。
也就是说，d[n] = d[n - 1] * 2 + 1。
这道题有四个塔，移动前i个盘子时，是四座塔的问题，移动后n-i个盘子时是三塔问题。
可以先将前i个盘子移走，然后将n-i个盘子在三塔问题下移动，然后把前i个盘子放至最上面。
