算法第三课

作者: Stark_Dylan | 来源:发表于2016-12-30 17:59 被阅读745次

title: 算法第三课
date: 2016-10-15 16:47:57
tags: 算法
thumbnail: http://img2.imgtn.bdimg.com/it/u=4054526222,762120886&fm=21&gp=0.jpg

枚举

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

口口口+口口口=口口口？

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的全排列呢？使用穷举，我们的想法是：

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个盒子，把牌放入盒子，其实我们发现，每次的操作都是相同的，只不过是把手上剩余的排放入当前的盒子中。所以我们大致的伪代码描述一下这样的思维：

void nextStep(int step) {
  for (int i = 0; i <= n; i ++) {
    if 手上有牌 {
      放入当前的step
      nextStep(step + 1)
    }
  }
}

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

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

其中的核心代码，其实是：

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

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

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

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

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

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

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

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

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表示，然后开始写代码：

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，2与2， 1两个点，接下来2，2这个点都可以到达，所以我们依旧需要标记位来标记点已经被走过避免重复，因为步数是一样的，所以无关紧要了（2个点一步都可以到达另一个点，岂不是步数一样么）。

使用这种扩散的思想，我们很容易想到，既然是一层一层，而且有顺序链式的关系，我们可以使用队列来完成（队列忘了可以去看算法二中的代码），我们来写代码研究一下：

#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)，此时的队列：

head == tail == 1
x:    1
y:    1
step: 0
prev: 0

尝试走到1，2：

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 ++;

此时的队列是：

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

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

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）出栈后

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加入队列中：

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）这个这个点已经扩展结束了，所以移除队列

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，部件4，部件6，部件3
5 = 直管，水平
6 = 直管，竖直
分别对应了上图的部件2，部件1
0 = 障碍物

这里我们给出的测试地图是，（1，1）从左边进水，（5，4）从右边出水为成功：

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

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

1 = 左边进水
2 = 上边进水
3 = 右边进水
4 = 下边进水

所以我们写实现代码，分别用深度与广度实现（建议自己先想一下再看）：

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

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

struct node {
  int x;
  int y;
  int prev;
  int front;
} s[2501];
int head, tail;

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

// 初始化队列
head = 1;
tail = 1;
  
// 加入第一个点
s[tail].x = 1;
s[tail].y = 1;
s[tail].prev = 0;
s[tail].front = 1; // 左边进水
tail ++;

然后

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 ++;
  }

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

算法第三课

枚举

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读