《挑战程序设计》笔记~~ 初出茅庐之一

川长思鸟来 2021-12-12 23:21 254阅读 0赞

二．初出茅庐——初级篇

2.1 穷竭搜索

穷竭搜索是将所有的可能性罗列出来，在其中寻找答案的方法。主要介绍深度优先搜索和广度优先搜索

1.递归函数

在一个函数中再次调用函数自身的行为叫做递归，这样的函数被称为递归函数。例如下面例子中求阶乘。

#include <iostream>
    using namespace std;
     
    int fact( int n)
    {
        if( n == 0) return 1;
     
        return n * fact(n-1);
    }
     
    int main()
    {
        int result = fact(10);
        cout <<"fact(10): " << result << endl;
        return 0;
    }

递归函数中，比较重要的一点是函数的停止条件是必须存在的。

斐波那契数列的定义A0=0，A1=1以及An = An-1 + An-2 (n > 1)。初项的条件就对应了递归的终止条件。

int fib(int n)
    {
        if(n <= 1) return n;
        return fib(n-1) +fib(n-2);
    }

但是由于上述函数需要依次递归展开，即使求fib(40)这样的n较小的结果时，也花费很长时间。由于fib(n)的n是一定的，无论调用多少次都会得到同样的结果，因此在计算依次之后，可以将数列结果保存，再次使用到时不需要重新计算，便可以优化结果。这种方法出于记忆搜索或者动态规划的思想。

#define MAX_N 40
    int memo[MAX_N+1];
     
    int fib( int n)
    {
        if( n <= 1) return n;
        if(memo[n] != 0) returnmemo[n];
        return memo[n] = fib(n-1)+ fib(n-2);
    }

上述的代码减少了计算的次数，节省时间。

2.栈

栈(Stack)是支持push和pop两种操作的数据结构。最后进入栈的一组数据可以先被取出，也即LIFO：Last In FirstOut，即后进先出

函数调用的过程通常是通过使用栈来实现的，因此递归函数的递归过程也可以改用栈上的操作来实现。

Stack使用例子

#include <iostream>
    #include <stack>
     
    using namespace std;
     
    int main()
    {
        stack<int> s;
        s.push(1);
        s.push(2);
        s.push(3);
        cout << s.top()<< endl;    // 打印栈顶元素 3
        s.pop();                    // 弹出栈顶元素
        cout << s.top()<< endl;
        s.pop();
        cout << s.top()<< endl;
        s.pop();
     
        return 0;
    }

3.队列

队列(Queue)与栈元素一样支持push和pop两个操作，与栈不同的是，pop完成的不是取出最顶端的元素，而是取出最底端的元素。最初放入的元素能够被最先取出，FIFO：First InFirst Out，即先进先出

队列使用例子：

#include <iostream>
    #include <queue>
    using namespace std;
     
    int main()
    {
        queue<int> que;
        que.push(1);
        que.push(2);
        que.push(3);
     
        cout << que.front()<< endl;
        que.pop();
        cout << que.front()<< endl;
        que.pop();
        cout << que.front()<< endl;
        que.pop();
     
        return 0;
    }

4.深度优先搜索

深度优先搜索（DFS， Depth-First Search）是搜索的手段之一。从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他的状态，如此不断反复，直到找到最终的解。

根据深度优先搜索的特点，采用递归函数实现比较简单。

题目1：求部分和问题

给定整数a1，a2，… ，an，判断是否可以从中选出若干个数字，试他们的和恰好为k。

其中：1 <= n <= 20，-10^8 <= ai <= 10^8，-10^8 <= k <= 10^8

输入：

n=4

a=\{1,2, 4, 7\}

k=13

输出

Yes（13= 2 + 4 + 7）

输入：

n=4

a=\{1,2, 4, 7\}

k=15

输出

方法：从a1开始按顺序决定每个数加或者是不加两种情况，在全部n个数都决定后再判断他们的和是否是k即可。

此时的状态数为2^( n+1)个，所以复杂度就为O(2^n)

#include<iostream>
    using namespace std;
     
    #define MAX_N 4
     
    int a[MAX_N]={1, 2, 4, 7};
    int n, k;
     
    bool dfs(int i, int sum)
    {
        if( i == n)
        {
            return sum == k;
        }
     
        if(dfs(i+1, sum))   // 不加第i个数字的情况
        {
            return true;
        }
     
        if(dfs(i+1,sum+a[i]))  // 加上第i个数字的情况
        {
            return true;
        }
     
        return false;
    }
     
    int main()
    {
        n = MAX_N;
        k = 13;
        int sum = 0;
        if(dfs( 0, sum))
        {
            cout <<"Yes"<< endl;
        }
     
        return 0;
    }

深度优先搜索从最开始的状态出发，遍历所有可以到达的状态。因此对所有的状态也可以进行操作或者列举出所有的状态。

题目2：Lake Counting

有一个大小为N\*M的院子，雨后积起了水。八连通的积水被认为是链接在一起的，请求出院子里总共有多少水洼？（八连通指的是下图中相对W的\*的部分）

\*\*\*

\*w\*

\*\*\*

限制条件： N,M <= 100

N=10，M=20，图如下，W代表积水，’.’代表没有积水

w. . . . . . . . . . . . . . . . ww .

.www . . . . . . . . . . . . . www

.. . . ww . . . . . . . . . . . ww .

.. . . . . . . . . . . . . . . . ww .

.. . . . . . . . . . . . . . . . w. .

.. w . . . . . . . . . . . . . . w. .

.w . w . . . . . . . . . . . . . ww .

w. w . w . . . . . . . . . . . . . w.

.w . w . . . . . . . . . . . . . . w.

.. w . . . . . . . . . . . . . . . w.

输出：

方法：从任意的w开始，不停地把相连接的部分用’.’代替，依次DFS后与初始的这个w链接的所有的W就被替换成了’,’，因此直到途中不再存在w为止，总供进行的次数就是答案。

8个方向共八个状态转移，每个格子的DFS的参数至多被调用依次，所以复杂度为O(8\*N\*M)，即O(N\*M)

#include <iostream>
    using namespace std;
     
    int N = 10;
    int M = 12;
    char field[10][12] =
    {
        {'w', '.', '.', '.', '.','.', '.', '.', '.', 'w', 'w', '.'},
        {'.', 'w', 'w', 'w', '.','.', '.', '.', '.', 'w', 'w', 'w'},
        {'.', '.', '.', '.', 'w','w', '.', '.', '.', 'w', 'w', '.'},
        {'.', '.', '.', '.', '.','.', '.', '.', '.', 'w', 'w', '.'},
        {'.', '.', '.', '.', '.','.', '.', '.', '.', 'w', '.', '.'},
        {'.', '.', 'w', '.', '.','.', '.', '.', '.', 'w', '.', '.'},
        {'.', 'w', '.', 'w', '.','.', '.', '.', '.', 'w', 'w', '.'},
        {'w', '.', 'w', '.', 'w','.', '.', '.', '.', '.', 'w', '.'},
        {'.', 'w', '.', 'w', '.','.', '.', '.', '.', '.', 'w', '.'},
        {'.', '.', 'w', '.', '.','.', '.', '.', '.', '.', 'w', '.'},
    };
     
    void dfs(int x, int y)
    {
        // 将当前的w设置为 .
        field[x][y] = '.';
     
        // 遍历所有的可能方向
        for(int dx = -1; dx <=1; dx++)
        {
            for(int dy = -1; dy<= 1; dy++)
            {
                int nx = x +dx;    // 分别移动dx 和 dy，得到相邻的位置判断是否有水
                int ny = y + dy;
                         // 如果相邻位置有 w，则进行深度遍历
                if( nx >= 0&& nx < N && ny >=0 && ny < M &&field[nx][ny] == 'w')
                {
                    dfs(nx, ny);
                }
            }
        }
    }
     
    int main()
    {
        int res = 0;
        for( int i = 0; i < N;i++)
        {
            for( int j = 0; j <M; j++)
            {
                if(field[i][j] =='w')       // 从第一个为w的开始遍历
                {
                    dfs(i,j);
                    res++;
                }
            }
        }
     
        cout <<"Result: " << res << endl;
        return 0;
    }

5. 宽度优先搜索

宽度优先搜索（BFS，Breadth-FirstSearch）也是搜索的手段之一。与深度搜索类似，从某个状态出发搜索所有可以到达的状态。

宽度优先搜索总是先搜索距离初始状态近的状态，也就是说按照开始状态->只需要一次转移就可以到达的所有状态->只需要2次转移就可以到达的状态-> … 以这样的方式进行搜索。宽度优先搜索只经过一次，因此复杂度为O(状态数\*转移方式)

深度优先搜索隐式地利用栈进行计算，而宽度优先搜索则利用队列。所有状态都是按照初始状态，由近及远的顺序被遍历。

题目1：迷宫的最短路径

给定一个大小为N\*M 的迷宫，迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四个格的通道移动。请求出从起点到终点所需要的最小步数，请注意，本体假设从起点一定可以移动到终点。

限制条件：N,M <= 100

输入：

\#S\#\#\#\#\#\#. \#

.. . . . . \# . . \#

.\# . \#\# . \#\#.\#

.\# . . . . . . . .

\#\#.\#\# . \#\#\#\#

.. . . \# . . . .\#

.\#\#\#\#\#\#\#. \#

.. . . \# . . . . .

.\#\#\#\# . \#\#\# .

.. . . \# . . .G\#

输出

方法：宽度优先搜索按照距离开始状态由近及远的顺序进行搜索，因此可以很容易地求出最短路径，最少操作之类问题的答案。本问题中，状态仅仅是目前所在位置的坐标，因此可以构成pair或者编码为int来表达。

转移的方向分为四个方向，状态数与迷宫的大小相等，复杂度为O(4\*M\*N)

宽度优先搜索中，只要将已经访问过的标记管理起来，就可以很好地做由近及远的搜索。这个问题中要求最短距离，不妨用d\[N\]\[M\]数组来保存最短距离

#include <iostream>
    #include <queue>
     
    using namespace std;
     
    #define MAX_N 10
    #define MAX_M 10
     
    const int INF = 100000000;
     
    typedef pair<int ,int> P;
     
    char maze[MAX_N][MAX_M+1] =
    {
        { '#', 'S', '#' , '#','#', '#', '#', '#', '.', '#'},
        { '.', '.', '.' , '.','.', '.', '#', '.', '.', '#'},
        { '.', '#', '.' , '#','#', '.', '#', '#', '.', '#'},
        { '.', '#', '.' , '.','.', '.', '.', '.', '.', '.'},
        { '#', '#', '.' , '#','#', '.', '#', '#', '#', '#'},
        { '.', '.', '.' , '.','#', '.', '.', '.', '.', '#'},
        { '.', '#', '#' , '#','#', '#', '#', '#', '.', '#'},
        { '.', '.', '.' , '.','#', '.', '.', '.', '.', '.'},
        { '.', '#', '#' , '#','#', '.', '#', '#', '#', '.'},
        { '.', '.', '.' , '.','#', '.', '.', '.', 'G', '#'},
    };
     
    int N = 10, M = 10;
    int sx = 0;
    int sy = 1;
    int gx = 9;
    int gy = 8;
    int d[MAX_N][MAX_M];
    int dx[4] = {1, 0, -1, 0}, dy[] = { 0, 1, 0, -1};
     
    int bfs()
    {
        queue<P> que;
        // 初始化所有距离为INF
        for( int i = 0; i < N;i++)
        {
            for( int j = 0; j <M; j++)
            {
                d[i][j] = INF;
            }
        }
     
        // 将起点加入队列，并将这一点的距离设置为0
        que.push(P(sx, sy));
        d[sx][sy] = 0;
        while( que.size())
        {
            P p = que.front();que.pop();
            if(p.first == gx&& p.second == gy)
                break;
     
            // 向四个方向循环
            for( int i = 0; i <4; i++ )
            {
                // 移动之后的坐标
                int nx = p.first +dx[i];
                int ny = p.second+ dy[i];
     
                // 判断是否可以移动以及是否已经访问过(d[nx][ny] != INF即已经访问过)
                if(0<= nx&& nx < N && 0 <= ny && ny < M &&maze[nx][ny] != '#' && d[nx][ny] == INF)
                {
                    // 可以移动的话，将它加入队列，并且到达该位置的距离确定为到p的距离+1
                    que.push(P(nx,ny));
                    d[nx][ny] = d[p.first][p.second]+ 1;
                }
            }
        }
     
        return d[gx][gy];
    }
     
    int main()
    {
     
        int res = bfs();
     
        cout <<"Result: " << res << endl;
        return 0;
    }

宽度优先搜索和深度优先搜索是一样的，都会生成所有能够遍历到的状态，因此需要所有状态进行处理时也可以选择宽度优先。由于递归函数可以写得很简短，而且状态的管理业更加简单，所以大多数情况下还是用深度优先算法。

求最短路径时深度优先搜索需要反复经过同样的状态，所以使用宽度优先搜索为好。

另外一种类似宽度优先搜索的状态转移顺序，并且注重节约内存的迭代加深深度优先搜索(IDDFS，IterativeDeepening Depth-First Search)

6.特殊状态枚举

生成可行解空间多数采用深度优先，但是在状态空间比较特殊时，可以很简短地实现。

C++的标准库提供了next\_permutation()方法，用于把n个元素共n！种不同的排列生成出来。

或者通过使用位运算，可以枚举从n个元素中取出k个的共C(k,n)中状态，或是某个集合的全部子集等。

#include <iostream>
    #include <algorithm>
    using namespace std;
     
    #define MAX_N 4
     
    bool used[MAX_N];
    int perm[MAX_N];
     
    // 生成0,1,2,3,4.... n-1的n！中排列
    void permutation1( int pos, int n)
    {
        if(pos == n)
        {
            for( int i = 0; i <MAX_N; i++)
            {
                cout <<perm[i] << " ";
            }
            cout << endl;
            return ;
        }
     
        // 针对perm的第pos个位置，究竟使用0- n-1中的哪一个进行循环
        for( int i = 0; i < n;i++)
        {
            if(!used[i])
            {
                perm[pos] = i;
                used[i] = true;
               permutation1(pos+1, n);
                used[i] = false;
            }
        }
     
        return ;
    }
     
    // 即使有重复的元素也会生成所有的排列
    // next_permutation是按照字典序来生成下一个排序的
    int perm2[MAX_N];
     
    void permutation2(int n)
    {
        for(int i = 0; i < n;i++)
        {
            perm2[i] = i;
        }
     
        do{
            for( int i = 0; i <MAX_N; i++)
            {
                cout <<perm2[i] << " ";
            }
            cout << endl;
       }while(next_permutation(perm2, perm2 + n));
        // 所有的排列生成后，next_permutation会返回false
        return ;
    }
     
    int main()
    {
        cout <<"permutation1:" << endl;
        for(int i = 0; i <MAX_N; i++)
        {
            perm[i] = i;
            used[i] = false;
        }
        permutation1( 0, MAX_N);
     
     
        cout <<"permutation2:" << endl;
        permutation2(MAX_N);
        return 0;
    }

7.剪枝

穷竭搜索会把所有的可能都检查一遍，当空间非常大时，复杂度会相应地变大。深度优先时，如果已经明确了当前状态无论如何转移都不会存在解，在这种情况下就不再继续搜素，而是直接跳过，这种方法称为剪枝。

如部分和中，如果某一个节点处，sum > k，则跳过本节点以后的搜索，再搜索也不会出现sum == k的情况了。

专栏：

栈内存在程序启动时统一分配，此后不再扩大，这一区域是有上限的，因此函数的递归深度也有上限。不过一般情况下，C和C++中进行上万次递归是可以实现的。

By Andy @ 2013-7-28