机试小课堂丨C++ 搜索，简化问题规模的利器！

2021-01-24 19:13 作者:苏世考研 0人读过 | 我要投稿

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

/ 写在前面的话 /

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研苏世计算机考研

搜索是什么？

搜索是利用计算机的高性能来有目的地穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种办法。

利用搜索能干什么？

在大规模实验环境中，通常在搜索前，根据条件降低搜索规模；并根据问题的约束条件进行剪枝；再利用搜索过程中的中间解，避免重复计算这几种方法进行优化。

搜索常用内容介绍

1

暴力枚举

1.1 概念

暴力枚举，也叫穷举法。就是将所有的情况都列举出来，依次判断是否符合题目条件，合适就保留这一项，不合适就放弃这一项，最终得出一般结论。利用计算机运算精确度高、速度快的特点，对该问题的所有可能情况挨个逐次检验，从而筛选出符合题目要求的答案。其最大难点是应该从一个什么样的维度来进行暴力枚举。

1.2 基本条件

（1）时间方面：一般来说主流OJ中，1000ms时间限制下可以运行操作数是10的7次方以内的运算，所以在枚举的时候先看一下数据范围，确保整个程序的执行操作数不会超过这个量级，如果超过就要更换枚举维度或者使用其他算法。

注意：当范围特别大的时候，用枚举法明显会超时。

（2）编程实现方面：一般需要枚举范围连续。如果离散，比较难用循环枚举出所有状态，也就不能保证解的完整性，但有些数据看似离散，实际上可以经过处理变得连续，比如构造数组。也需要枚举内容已知，不能在枚举到某个地方的时候发现未知。

1.3 方法步骤

（1）确定枚举变量、枚举范围（尽量缩小）和枚举条件；

（2）根据题目要求循环检验每一个解（尽量剪枝）。

1.4 典型例题

题目描述：

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和

比如：5 = 0^2 + 0^2 + 1^2 + 2^2

比如：7 = 1^2 + 1^2 + 1^2 + 2^2（^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对4个数排序：0 <= a<= b <= c <= d

并对所有的可能表示法按a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

样例输入：5

样例输出：0 0 1 2

样例输入：12

样例输出：0 2 2 2

样例输入：773535

样例输出：1 1 267 838

输入：程序输入为一个正整数N(N<5000000)

输出：要求输出4个非负整数，按从小到大排序，中间用空格分开

本题思路：

第一眼看上去可以用四层循环暴力求解，但会超时，最后一层可以通过开平方求出来，可以省一层，5000000开平方大于2236，所以循环的最大值就设置为2237。

代码实现：

运行结果：

2

递归及其应用

2.1 概念

递归是直接或者间接调用自身，是一种解决问题的方法，具体来说就是把规模大的原问题分解为规模小的相似的子问题，持续分解，直到小到可以用非常简单直接的方式来解决。

2.2 基本条件

从概念中我们可以得到递归的基本条件：

（1）原问题可以分解为子问题。

（2）调用自身：通过递归调用来缩小问题的规模，并且子问题和原问题有相同的形式。

（3）子问题有穷，就是说分解次数是有限的。

（4）存在一种情况可以使递归退出，使问题得到解决。

2.3 怎么更好地理解递归

比如我们收到一个礼物盒，我们打开后发现又是一个礼物盒，打开后发现还是一个礼物盒，然后我们不断地打开更小的礼物盒......直到发现一张纸条，上面写着：若想考研成功，请把礼物盒包回到它最原始的状态。然后我们又一层一层地把礼物盒包回去。

这个过程就是递归的完整过程，不断地缩小问题规模，直到遇到一个情境或者边界使问题结束，然后依次退出。

2.4 经典问题

（1）斐波那契数列

0,1,1,2,3,5,8,13,21,34,55,89,144....

这样的数列就是斐波那契数列，总之就是第N(N>2)个数等于第(N-1)个数和第(N-2)个数的和。

fib(N) = fib(N-1)+fib(N-2)

递归算法实现和运行结果：

（2）阶乘

阶乘得到的是一个整数从1连续乘到它本身的结果。

比如：2的阶乘为2! = 2 * 1

比如：5的阶乘为5! = 5 * 4 *3 * 2 * 1

递归算法实现和运行结果：

3

广度/宽度优先搜索

3.1 概念

广度优先搜索（宽度优先搜索）又称为BFS（Breadth First Search），是最简便的图的搜索算法之一，是连通图的一种遍历策略，属于一种盲目搜寻法，简言之就是系统地展开并检查图中的所有节点以找寻结果。主要用到队列这一数据结构。

3.2 算法思想

使用队列来实现，整个过程可以看做一个倒立的树形：

（1）把根节点放在队列的末尾。

（2）每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾，并把这个元素记为它下一级元素的前驱。

（3）找到所要找的元素时程序结束。

（4）如果遍历整个树还没有找到，结束程序。

3.3 典型例题

题目描述

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

（’#’、’.’、‘S’、'G’分别表示墙壁、通道、起点、终点）

样例输入

样例输出

代码实现

运行结果

4

深度优先搜索

4.1 概念

深度优先搜索又称DFS（Depth First Search），是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。换句话说，就是找一个起始结点，沿着这个起始结点一直找下去，直到找到最后一个满足条件的分节点，然后再寻找另一条路径，沿着一条路走不满足时会自动返回上一层节点继续进行判断。

4.2 基本方法

（1）访问顶点v；

（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历，直至图中和v有路径相通的顶点都被访问；

（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

4.3 典型例题

题目描述

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

输入

输入含有多组测试数据。每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。n <= 8 , k <= n当为-1 -1时表示输入结束。随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

输出

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

样例输入