算法第三课

枚举

枚举算法又被称为穷举算法,字面看很暴力,先来看一个例子:

1
口口口+口口口=口口口?

3位数与3位数相加等于一个3位数(使用1~9,不能重复),用穷举来说,就是列举所有的可能。这样写for循环的话,我们要写9个循环嵌套(9个数字,每个都要循环),然后通过一大串的判断语句之后,才能得到我们的答案(答案还需要除以2,173+286与286+173是一样的),有兴趣或者有时间的同学可以用穷举的思想试一下。

接下来,我们再看另外一个例子:123,3个数字全排列,可能是123,132,213,231,321,312;那么1234全排列呢?123456789全排列呢?1~n的全排列呢?使用穷举,我们的想法是:

1
2
3
4
5
6
7
8
9
10
11
int main(int argc, const char * argv[]) {
for (int i = 1; i <=3; i ++) {
for (int j = 1; j <=3; j ++) {
for (int k = 1; k <= 3; k++) {
if ( i != k && i != j && j != k ) {
printf("%d%d%d\n", i, j, k);
}
}
}
}
}

那1234,就是4个for,1~9就是9个for…. 显然,比较傻,我们接着往下想(先剧透一下,本文其实不叫枚举,叫深度搜索):如果现在有3张扑克牌,3个盒子,把牌放入盒子,其实我们发现,每次的操作都是相同的,只不过是把手上剩余的排放入当前的盒子中。所以我们大致的伪代码描述一下这样的思维:

1
2
3
4
5
6
7
8
void nextStep(int step) {
for (int i = 0; i <= n; i ++) {
if 手上有牌 {
放入当前的step
nextStep(step + 1)
}
}
}

按照这样的思维,我们来解决上边的问题:首先准备book数组用来标记所有的扑克牌是否已经使用,然后使用numbox表示盒子,

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
int numbox[10], book[10], count; // 我们假定,输入的范围就是1~9, numbox为盒子, book标记这张扑克还在不在手上
void stepTo(int step);
int main(int argc, const char * argv[]) {
scanf("%d", &count);
stepTo(1); // 从第一步开始
return 0;
}
void stepTo(int step) { // Step表示当前是第几个小盒子的面前,或者说第几步
if ( step == count + 1 ) { // count为盒子数,如果step==count+1意味着count个盒子全部放好了扑克
for (int i = 1; i <= count; i ++) {
printf("%d", numbox[i]); // 依次打印盒子中的数字
}
printf("\n");
return ; // 结束本次流程
}
// 此时,我们需要往盒子中放入扑克牌
for (int i = 1; i <= count; i ++) { // 循环扑克牌
// 判断扑克牌是否在手中(book数组标记位是否为0, 1表示已经用了)
if ( book[i] == 0 ) {
numbox[step] = i; // 当前的盒子放入该扑克牌
book[i] = 1; // 标记为使用
stepTo(step + 1); // 下一步
book[i] = 0; // 将试过的扑克牌置为未使用
}
}
return;
}

其中的核心代码,其实是:

1
2
3
4
5
6
7
8
for (int i = 1; i <= count; i ++) { // 循环扑克牌
if ( book[i] == 0 ) {
numbox[step] = i; // 当前的盒子放入该扑克牌
book[i] = 1; // 标记为使用
stepTo(step + 1); // 下一步
book[i] = 0; // 将试过的扑克牌置为未使用
}
}

基本类似于我们刚才的想法,现在我们来逐行解释一下:

  1. 从1开始,循环每张扑克牌
  2. book数组是我们用来标记扑克牌是否使用的,这里 ==0意味这这张牌没有使用
  3. 将这张牌,放入当前的盒子
  4. 本次循环中,将这张牌标记为已经使用
  5. 在这张牌已经使用的情况下,进行下一步的寻找
  6. 将本次循环使用的牌标记为0,因为后边还需要使用这张牌。

3,4,5,6行代码,可能大家理解起来会很吃力,一定要慢慢的想:

当前的扑克,已经放入了当前的盒子,那么在寻找下一个盒子放什么扑克之前,当前使用了的扑克需要 book[i] = 1
调用了下一步之后,由于这张牌在以后的情况中还会被继续使用,所以我们把book位置为未使用
(这里因为我们是先进入下一步,然后置扑克为未使用,所以对第5行的下一步寻找没有影响,但是如果不置为1,下次循环这张牌就不能使用了。
这是一个链式的思维,一点点在调用下一步的时候减少扑克,递归的思维就不说了哈,如果没想明白,希望大家使用笔模拟一下for的数据变动)

以上的代码,被称为深度搜索(Depth First Search,DFS),关键的思想就是当下该如何做,以后的做法和当下是一样的。深度搜索的基本模型是:

1
2
3
4
5
void dfs(int step) {
判断边界
尝试每一种可能
继续下一步
}

现在我们利用这种思维来解决开篇那个使用穷举需要9个循环嵌套的问题:首先是9个盒子,然后9张牌:

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
int book[10], numbox[10];
void dfs(int box) {
if ( box == 10 ) { // box == 9 + 1, 意味着走过了9个放数字的步骤
// 口口口 + 口口口 = 口口口
int numberA = numbox[1] * 100 + numbox[2] * 10 + numbox[3];
int numberB = numbox[4] * 100 + numbox[5] * 10 + numbox[6];
int results = numbox[7] * 100 + numbox[8] * 10 + numbox[9];
if ( numberA + numberB == results ) {
printf("%d%d%d + %d%d%d = %d%d%d", numbox[1], numbox[2], numbox[3], numbox[4], numbox[5], numbox[6], numbox[7], numbox[8], numbox[9]);
printf("\n");
}
return; // 结束本次流程
}
for (int i = 1; i <= 9; i ++) {// 循环数字
if ( book[i] == 0 ) { // 未使用的数字
numbox[box] = i;
book[i] = 1;
dfs(box + 1); // 下一步
book[i] = 0;
}
}
return;
}
int main(int argc, const char * argv[]) {
dfs(1); // 从第一个盒子开始放入
return 0;
}

是不是相当的简单,接下来的去重,就大家自己做吧,我们接着往下看:最短路径问题(其实也不算,最短路径后边有自己的算法…,这里起名阻塞了)。

我们来看迷宫问题,假如有一个迷宫,迷宫中存在障碍物,我们如何能从起点找到到达目标点的最短步数呢?解决这个问题,首先我们要用一个二维数组来表示迷宫,默认全为0,迷宫中的障碍物用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
80
81
82
83
84
85
int book[51][51]; // 标记走过的点
int minStep = 9999999;
struct Maze {
int map[51][51];
int n; // 行
int m; // 列
};
struct StartPoint {
int x;
int y;
};
struct EndPoint {
int x;
int y;
};
struct Maze maze;
struct StartPoint sPoint;
struct EndPoint ePoint;
void dfs(int x, int y, int step);
int main(int argc, const char * argv[]) {
scanf("%d %d", &maze.n, &maze.m);
for (int i = 1; i <=maze.n ; i ++) {
for (int j = 1; j <= maze.m; j ++) {
scanf("%d", &maze.map[i][j]);
}
}
sPoint.x = 1, sPoint.y = 1; // 设置起点
book[sPoint.x][sPoint.y] = 1; // 防止后边重复走起点
printf("输入结束地址: ");
scanf("%d %d", &ePoint.x, &ePoint.y);
dfs(1, 1, 0); // 初始步是0
printf("%d\n", minStep);
return 0;
}
void dfs(int x, int y, int step) {
// 4个方向,右、下、左、上
int next[4][2] = {
{1, 0},
{0, 1},
{-1, 0},
{0, -1}
};
int tx, ty;
if ( x == ePoint.x && y == ePoint.y ) { // 到了目标点
if (step < minStep) {
minStep = step; // 更新最小的步数
}
return;
}
// 思考下一步可能的位置点
for (int i = 0; i < 4; i ++) { // 4中方向可能走
tx = x + next[i][0];
ty = y + next[i][1];
// 判断是否越界
if ( tx < 1 || tx > maze.n || ty < 1 || ty > maze.m ) {
continue;
}
// 判断是否为障碍物或者是已经走过的点
if ( maze.map[tx][ty] == 0 && book[tx][ty] == 0 ) {
book[tx][ty] = 1;
dfs(tx, ty, step + 1);
book[tx][ty] = 0;
}
}
return;
}

简单的,解决了迷宫最短路径问题。但是仅仅是这样么,并不是,接下来介绍一种叫做广度优先搜索的方法,简称BFS(Breadth First Search)。用言语描述,2个方法的区别就是,深度搜索是每次都走到极致,然后在下一次,而广度则是每次都往外同时扩张一层:我们继续使用迷宫的例子去寻找到达目的地的最短距离:

  1. 从1,1开始,我们可以到达的点是 1,2与2, 1两个点,接下来2,2这个点都可以到达,所以我们依旧需要标记位来标记点已经被走过避免重复,因为步数是一样的,所以无关紧要了(2个点一步都可以到达另一个点,岂不是步数一样么)。
1
2
3
4
5
6
7
8
迷宫:
00 1 0
↓ ↓
0 00 0
↓ ↓
0 0 1 0
0 1 0 0
0 0 0 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <stdio.h>
struct node {
int x; // 横坐标
int y; // 纵坐标
int prev; // 如果需要输出路径的话,可以用来标记父节点在队列中的编号
int step; // 步数
};
int main(int argc, const char * argv[]) {
int map[51][51] = {0}; // 地图
int book[51][51] = {0};// 标记
int next[4][2] = {
{1, 0},
{0, 1},
{-1, 0},
{0, -1}
}; // 4个方向,右、下、左、上
struct node queue[2501]; // 50 * 50的地图范围
int head, tail; // 队列的使用方式
int n, m; // 分别表示地图的行列
int ex, ey; // 目标点
// 初始化地图与目标点
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
scanf("%d", &map[i][j]);
}
}
printf("输入目标点: ");
scanf("%d %d", &ex, &ey);
// 初始化队列
head = 1;
tail = 1;
// 插入起点
queue[tail].x = 1;
queue[tail].y = 1;
queue[tail].prev = 0;
queue[tail].step = 0;
tail ++;
// 标记起点1, 1为走过的点
book[1][1] = 1;
int flag = 0; // 标记是否到达目标点, 0表示没有到达,1表示到达
int tx, ty; // 临时变量
while (head < tail) { // 对队列进行遍历操作
// 4个方向的操作
for (int i = 0; i < 4; i ++) {
tx = queue[head].x + next[i][0];
ty = queue[head].y + next[i][1];
// 是否越界
if ( tx < 1 || tx > n || ty < 1 || ty > m ) {
continue;
}
// 是否障碍物或者走过的点
if ( map[tx][ty] == 0 && book[tx][ty] == 0 ) {
book[tx][ty] = 1;
// 插入新的点到队列中, 这里由于我们是扩展,所以用过的点就不会在用了,也就不需要把标记位清0
queue[tail].x = tx;
queue[tail].y = ty;
queue[tail].prev = head; // 每一个点都是从head扩展出来的,所以上一个就是head的位置
queue[tail].step = queue[head].step + 1;// 步数等于head的步数加1
tail ++;
}
if ( tx == ex && ty == ey ) {
// 如果是目标点,标记一下,结束
flag = 1;
break;
}
}
if (flag == 1) {
break;
}
head ++; // 当前点已经寻找完了,继续从头部扩散
}
printf("Step: %d", queue[tail - 1].step);
int prev = queue[tail - 1].prev;
while (prev) {
// prev node
struct node prevNode = queue[prev];
printf("{%d, %d} ", prevNode.x, prevNode.y);
prev = prevNode.prev;
}
}

我们大致的模拟一下,从(1,1)点开始,先尝试往右找到了(1,2),此时的队列:

1
2
3
4
5
head == tail == 1
x: 1
y: 1
step: 0
prev: 0

尝试走到1,2:

1
2
3
4
5
6
7
8
9
10
tx = queue[head].x;
ty = queue[head].y + 1;
// 判断越界、标记省略了 ...
book[tx][ty] = 1;
// 插入新的点到队列中
queue[tail].x = tx;
queue[tail].y = ty;
queue[tail].prev = head;
queue[tail].step = queue[head].step + 1;
tail ++;

此时的队列是:

1
2
3
4
5
head == 1, tail == 2
x: 1 1
y: 1 2
step: 0 1
prev: 0 1

接着还要尝试往其他方向走,我们发现从(1,1)一步还可以走到(2,1),所以也加入队列

1
2
3
4
5
head == 1, tail == 3
x: 1 1 2
y: 1 2 1
step: 0 1 1
prev: 0 1 1

扩展完(1,1)后,这个点就没用了,所以while中的head++让(1,1)出栈后

1
2
3
4
5
head == 2, tail == 3
x: 1 1 2
y: 1 2 1
step: 0 1 1
prev: 0 1 1

变成了这样,head变为了2,所以接下来要从点(1,2)开始扩展。我们发现(1,2)这个点可以到达(2,2),所以将2,2加入队列中:

1
2
3
4
5
head == 2, tail == 4
x: 1 1 2 2
y: 1 2 1 2
step: 0 1 1 2
prev: 0 1 1 2

这样,(1,2)这个这个点已经扩展结束了,所以移除队列

1
2
3
4
5
head == 3, tail == 4
x: 1 1 2 2
y: 1 2 1 2
step: 0 1 1 2
prev: 0 1 1 2

现在head变为了(2,1)点,我们继续扩展下去。接下来的模拟过程,大家自己来思考一下。

你们先看,我去拉屎~

回来了,接着写,拉了屎后轻松了许多,放空了思维,我们来解一道叫做水管工的题,先看个彩色的图:

想必读者都玩过这个游戏。水管分为直的水管,弯的水管,把他们连起来,形成一条通道,如果有通道的话,输出链接的点(使用广度搜索或者深度搜索)。我们先来分析一下组成的部件:

这是水管的全部状态,直管2种状态,弯管4种状态。当然,我们还可以在地图中加入障碍物,用0代替,水管的状态分别用数字指定:

1
2
3
4
5
6
7
8
9
1 = 弯管,右上角
2 = 弯管,右下角
3 = 弯管,左下角
4 = 弯管,左上角
分别对应了上图的部件5,部件4,部件6,部件3
5 = 直管,水平
6 = 直管,竖直
分别对应了上图的部件2,部件1
0 = 障碍物

这里我们给出的测试地图是,(1,1)从左边进水,(5,4)从右边出水为成功:

对数组我喜欢从下标1开始叫,这样不用思考

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

并且我们注意到,每个管子进水的方向也可能是不同的,所以我们规定

1
2
3
4
1 = 左边进水
2 = 上边进水
3 = 右边进水
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
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
int map[6][6]; // 地图
int book[50][50]; // 标记
int n, m; // 行 列
int flag; // 结果标记
void dfs(int x, int y, int front);
int main(int argc, const char * argv[]) {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
scanf("%d", &map[i][j]);
}
}
dfs(1, 1, 1);
if ( flag == 1 ) {
printf("成功了!");
} else {
printf("不能连通");
}
}
void dfs(int x, int y, int front) {
if (x == n+1 && y == m && front == 1) {// 为什么n+1,因为水流出去才行,而不是到了(n,m)结束,动脑子想想,我们的题目要求从右下角的右边出水
flag = 1;
return ;
}
// 越界处理
if ( x < 1 || x > n || y < 1 || y > m ) {
return;
}
if ( book[x][y] == 1 ) {
return;
}
book[x][y] = 1;
// 当水管是直管的时候
if ( map[x][y] == 5 || map[x][y] == 6 ) {
// 左边进水
if ( front == 1 ) {
dfs(x + 1, y, 1);
}
// 上边进水
if ( front == 2 ) {
dfs(x, y + 1, 2);
}
// 右边进水
if ( front == 3 ) {
dfs(x - 1, y, 3);
}
// 下边进水
if ( front == 4 ) {
dfs(x, y - 1, 4);
}
}
// 当水管是弯管的时候
if ( map[x][y] >= 1 && map[x][y] <= 4 ) {
if ( front == 1 || front == 3) {
dfs(x, y+1, 2);
dfs(x, y-1, 4);
}
// 上、下
if ( front == 2 || front == 4) {
dfs(x-1, y, 3);
dfs(x+1, y, 1);
}
}
book[x][y] = 0;
return;
}

然后我们用广度的思想也想一下,首先我们需要一个队列

1
2
3
4
5
6
7
struct node {
int x;
int y;
int prev;
int front;
} s[2501];
int head, tail;

初始化队列之后,然后我们需要一个while循环:

1
2
3
4
5
6
7
8
9
10
// 初始化队列
head = 1;
tail = 1;
// 加入第一个点
s[tail].x = 1;
s[tail].y = 1;
s[tail].prev = 0;
s[tail].front = 1; // 左边进水
tail ++;

然后

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
while (head < tail) {
// 结果判断
// 越界判断
// 是否为已经走过的管道
// 标记
int pipes = map[s[head].x][s[head].y];
if (pipes == 5 || pipes == 6) {
struct node tNode;
// 加入队列
if (s[head].front == 1) {
} else if (s[head].front == 2) {
} else if (s[head].front == 3) {
} else {
}
s[tail] = tNode;
tail ++;
} else {
struct node rNode, lNode;
// 加入队列
if (s[head].front == 1 || s[head].front == 3) {
} else {
}
s[tail] = rNode;
tail ++;
s[tail] = lNode;
tail ++;
}
head ++;
}

兄弟,自己写吧~ 我也看的头晕。

评论