第
3
章
蛮力法
..3.1概述
蛮力法(又称穷举搜索或完全搜索法)是一种简单的方法,常常直接基于问题
的描述和所涉及的概念定义。蛮力法是一种通用的方法,几乎可以解决任何算
法问题。其思想是生成问题的所有可能解决方案,然后根据问题选择最佳解决
方案。

..3.2 
蛮力法的主要设计思想

3.1 
使用蛮力法的几种情况
2.
如果有足够的时间来处理所有的解决方案,蛮力法会是一种很好的方法,因为
该算法通常很容易实现,并且总是能给出正确的答案。蛮力法可用于以下场景。

(1)一些小规模的问题。当要解决的问题实例不多并且可以接受蛮力法的运
算速度时,蛮力法的设计代价通常较为低廉。
(2)问题找不到一个精确的解决方案。在许多情况下,蛮力法或其变种是唯
一已知可获得精确解决方案的方法。
算法
(
。
3)蛮力法可以为矩阵乘法、排序、搜索、字符串匹配等重要问题提供合理的
2.蛮力法的求解步骤
3.2 
蛮力法包括以下步骤。

(1)用蛮力算法求解问题,需要事先确定问题的特殊性质,通常解是在解组合
对象(如排列、组合或集合的子集)中。
(2)系统地列出问题的所有潜在解决方案。
(3)评估所有潜在的解决方案,取消不可行的解决方案,对于优化问题,跟踪
直到找出最佳的解决方案。
(4)返回最优解。

第3章蛮力法47
..3.3蛮力法示例与分析
3.3.1选择排序
例3.1给定一个大小为n的数组,请将数组中的元素按从小到大进行排序并输出。
解题思路:选择排序算法的思想是,将数组分为已排序部分和未排序部分,每次对未排
序部分进行扫描,找出最小值,将其和未排序部分的第一个元素交换位置,此时这个位置的
元素已经属于已排序部分,经过n-1次这样的操作,数组有序。
对于如图3.1所示的数据,可按照图3.2~图3.6进行选择排序。
图3.1排序过程初始数据图3.2排序过程步骤0
图3.排序过程步骤
1 
图3.排序过程步骤2

34 


图3.排序过程步骤
3 
图3.排序过程步骤4

56 

步骤0:初始状态,所有元素都属于未排序状态。
步骤1:将未排序部分中的最小值1与未排序部分的第一个元素3交换,排序部分元素
个数加1,未排序部分元素个数减1,目前排序部分为{1}, 未排序部分为{5,2,3,4}。
步骤2:将未排序部分中的最小值2与未排序部分的第一个元素5交换,排序部分元素
个数加1,未排序部分元素个数减1,目前排序部分为{1,2}, 未排序部分为{5,3,4}。
步骤3:将未排序部分中的最小值3与未排序部分的第一个元素5交换,排序部分元素
个数加1,未排序部分元素个数减1,目前排序部分为{1,2,3}, 未排序部分为{5,4}。
步骤4:将未排序部分中的最小值4与未排序部分的第一个元素5交换,因为未排序部
分只剩下两个元素,因此交换后整个数组有序。
考虑将选择排序通过代码呈现,将未排序部分起始下标
i 
设为1,重复若干次如下步骤
直至i=。

(1)扫(n) 描未排序部分,找出最小值对应下标mnpos。
(2)将mnpos对应元素与位置
i 
对应元素交换。
(3)未排序部分起始下标i++ 。

48 算法设计与问题求解(第2版·微课版) 
选择排序要经过n(n-1)/2次比较,因此复杂度为O(n2)。
参考代码如下。 
int main() 
{ 
cin >> n; 
for(int i = 1; i <= n; i++) 
cin >> a[i]; 
for(int i = 1; i <= n -1; i++) 
{ 
int mn = a[i], mnpos = i; 
for(int j = i +1; j <= n; j++) 
{ 
if(a[j]<mn) 
{ 
mn = a[j]; 
mnpos = j; 
} 
} 
if(mnpos != i) 
swap(a[i], a[mnpos]); 
} 
}
测试结果如下。 
请输入数组大小: 
5
请输入数组元素值: 
3 5 2 1 4 
输出排序后结果: 
1 2 3 4 5 
3.3.2 旅行商问题
旅行商问题(TravelingSalesmanProblem,TSP)描述:商品推销员要去n 个城市推销
商品,城市从1~n 编号,任意两个城市间有一定距离,该推销员从城市1出发,需要经过所
有城市并回到城市1,求最短总路径长度。
解题思路:把旅行商问题看作一种排列问题,不难想出,这道题的蛮力解法即穷举所有
路线。选定起点有n 种选法,选定起点后的下一个目的地有n-1种选择方法,再下一个有
(n-2)种选择方法,……总共有n!种排列方法,算法复杂度达到O(n!),因此蛮力解法只能
解决小规模问题。
将该题转化为加权图模型,顶点表示城市,边权表示距离,枚举所有路线并取最小值。
例3.2 求解城市数量n=4的TSP问题,其中城市直接连接关系如图3.7所示。

第3章 蛮力法 49 
图3.7 旅行商问题加权图模型
所有的可能路线及总距离如表3.1所示。
表3.1 所有的可能路线及总距离表
路 线总 距 离路 线总 距 离
1,2,3,4,1 3→4不可行1,3,2,4,1 20 
1,2,4,3,1 4→3不可行1,4,2,3,1 20 
1,3,4,2,1 3→4不可行1,4,3,2,1 4→3不可行 
利用深度优先搜索(DeepFirstSearch,DFS)方法进行搜索,得到如图3.8所示的搜
索树。
旅行商
问题
参考代码如下。 
void dfs(int *a, int len, int num, int u) 
//数组记录历经城市的顺序,len 记录总距离,num 记录经过城市个数, 
//u 表示当前在哪个城市
{ 
if(num == n) 
{ 
if(dis[u][1]== -1) 
return; 
len += dis[u][1]; 
ans = min(ans, len); 
return; 
} 
for(int i = 2; i <= n; i++) 
{ 
int flg = 0; 
for(int j = 1; j <= num; j++) 
{

50 算法设计与问题求解(第2版·微课版) 
if(a[j]== i) //排除已经经过该城市的情况 
{ 
flg = 1; 
break; 
} 
} 
if(!flg && dis[u][i]!= -1) //排除无法到达该城市的情况 
{ 
a[num +1]= i; 
dfs(a, len +dis[u][i], num +1, i); 
} 
} 
} 
图3.8 DFS搜索树
最短路径长度为20。
3.3.3 字符串匹配蛮力解决
给定一个文本串s1 和模式串s2,从文本串中找出模式串第一次出现的位置,若不存在, 
输出-1。
解题思路:BF算法的原理就是将文本串的第一个字符和模式串的第一个字符比较,如
果相同,则比较下一个,否则将文本串位置后移,再次尝试和模式串匹配,直至匹配成功。最
多进行nm 次比较(n、m 分别表示文本串长度和模式串长度),算法复杂度达到O(nm )。
例3.3 从文本串为s1=aababc中找出模式串s2=abc第一次出现的位置。

第3章 蛮力法 51 
文本串与模式串匹配过程如下。
(1)文本串位置=0,模式串位置=0,s1[0]=s2[0]='a',匹配成功,模式串位置后移
一位。
(2)文本串位置=0,模式串位置=1,s1[1]=a' ',s2[1]=b' ',匹配失败,模式串位置回到
0,文本串位置后移。
(3)文本串位置=1,模式串位置=0,s1[1]=s2[0]='a',匹配成功,模式串位置后移
一位。
(4)文本串位置=1,模式串位置=1,s1[2]=s2[1]='b',匹配成功,模式串位置后移
一位。
(5)文本串位置=1,模式串位置=2,s1[3]=a' ',s2[2]=c' ',匹配失败,模式串位置回到
0,文本串位置后移。
(6)文本串位置=2,模式串位置=0,s1[2]='b',s2[0]='a',匹配失败,模式串位置保持
0,文本串位置后移。
(7)文本串位置=3,模式串位置=0,s1[3]=s2[0]='a',匹配成功,模式串位置后移
一位。
(8)文本串位置=3,模式串位置=1,s1[4]=s2[1]='b',匹配成功,模式串位置后移
一位。
(9)文本串位置=3,模式串位置=2,s1[5]=s2[1]='c',匹配成功,模式串位置后移
一位。
(10)模式串位置=3,模式串与字符串匹配成功。
参考代码如下。 
int search() 
{ 
int l = 0, p = 0; //l 表示目前匹配的文本串位置,p 表示模式串的位置 
int len = s2.size(); //匹配串的长度 
while(l+p <s1.size()) 
{ 
if(s1[l+p]== s2[p]) //单个字符匹配成功 
{ 
p++; 
if(p == len) //文本串和模式串匹配成功 
return l +1; 
} 
else 
{ 
l++; //匹配失败,匹配下一个元素 
p = 0; //p 回到模式串首 
} 
} 
return -1; 
}

52算法设计与问题求解(第2版·微课版) 
3.3.40-1背包问题
有n种物品,第i种物品的质量为Wi,价值为Vi,有一个存放质量为C的背包,怎样选
取物品,使得在物品总质量不超过C的情况下总价值最大。
解题思路:要在所有可行情况下找到最大总价值,要枚举所有可行情况,把每个物品看作
一个元素,即枚举出所有可行的子集,子集生成可以通过深度优先实现。对于每个物品,选择
和不选择两种状态,因此,n个元素的子集数量达到2n,算法的时间复杂度为O(2n) 。
例3.4有4个物品,物品的质量W=[1,3,5,7], 价值V=[4,6,9,13], 背包容量为
12,求背包所能存放物品的最大价值。
表3.2列出了问题的所有可行子集。
表3.2所有可行子集表
子集总质量总价值
Φ0 0 
1 1 4 
2 3 6 
1,2 4 10 
3 5 9 
1,3 6 13 
2,3 8 15 
2,3 9 19 
4 7 13 
1,4 8 17 
2,4 10 19 
1,2,4 11 23 
3,4 12 21 
1,3,4 13 不可行
2,3,4 15 不可行
1,2,3,4 16 不可行
深度优先(DFS)搜索树如图3.

9所示。

0-1背包问题


图3.深度优先搜索树

9 


第3章 蛮力法 53 
参考代码如下。 
void dfs(int num, int sumw, int sumv) 
//num 表示当前是第几个物品,sumw 表示当前的总质量,sumv 表示当前价值
{ 
if(num == n +1) 
{ 
ans = max(ans, sumv); 
return; 
} 
if(sumw +w[num]<= c) //如果放得下该物品 
dfs(num +1, sumw +w[num], sumv +v[num]); //递归构造子集 
dfs(num +1, sumw, sumv); //不放该物品的情况,递归构造子集
}
所以,当选取1、2、4这3个物品时,背包中存放物品的价值之和达到最大,为23。
.. 3.4 能力拓展
3.4.1 连续数和 
给定数字n,试求能否将n 分解为几个连续正整数之和,如果有多种结果,输出连续整
数中最小值最大的那一组结果。如果无解,输出-1。
解题思路:假设存在正整数a 使得n=a+a+1+a+2+…+a+k。不难想到枚举a, 
因为至少要分解成两个数的和,所以a<n/2,但枚举a 后k 仍然不确定,还要依次枚举k 判
断是否为问题的解,因此,问题的复杂度为O(n2),复杂度较高。
进一步分析可知,由于n=(2a+k)×(k+1)/2,且a 为正整数,所以2a+k>k+1,代
入得n>(k+1)2/2。移项后得k< 2n -1,所以k 的最大值不超过 2n 。
而a 的值也可以通过移项获得,即a=((n×2)/(k+1)-k)/2。当存在k、a 的值为正
整数时有解,并且k 越小,a 越大,从小到大枚举k,第一个可行解即满足题目要求的解,时
间复杂度优化到了O( n )。由此可见,就算是蛮力枚举,枚举的值不同也会对时间复杂度
产生显著影响。
例3.5 当n=10时,输出连续数和。
该问题的求解过程如表3.3所示。
表3.3 连续数和求解过程
k a k a 
1 9/2 3 1 
2 7/3

54 算法设计与问题求解(第2版·微课版) 
n=10时的连续数为1、2、3、4。
参考代码如下。 
int main() 
{ 
cin >> n; 
int flag = 0; 
for(int i = 1; i * i <= 2 * n; i++) 
{ 
int a = ((n * 2) / (i +1) -i) / 2; 
if(a > 0 && (2 * a +i) * (i +1) / 2 == n) 
{ 
flag = 1; //标记找到解 
for(int j = 0; j <= i; j++) 
{ 
cout <<a +j <<" "; 
} 
break; 
} 
} 
if(!flag) 
cout <<-1; 
} 
3.4.2 矩形个数
给定n×n 的矩阵,矩阵中有0和1两个数字,现要求矩阵中只包含0的矩形的数量。
解题思路:枚举矩形左上角坐标i、j,矩形右边界k,在i、j、k 一定的情况下能得到的
满足条件的矩形个数和能向下扩展的高度有关,在k 增加的过程中不断更新可扩展的
高度。例
3.6 给定n=4,矩阵中数字如表3.4所示,求矩阵中只包含0的矩形的数量。
表3.4 例3.6矩阵
0 0 1 0 
1 1 0 1 
0 1 0 0 
0 1 0 1 
该问题的蛮力搜索过程如下所示。
(1)首先搜索第一行,如图3.10所示。
①i=1,j=1,k=1,无法再向下扩展,得到一个矩形。

第3章 蛮力法 55 
图3.10 搜索矩阵第一行
图3.11 搜索矩阵第二行
②i=1,j=1,k=2,无法再向下扩展,得到一个矩形。
③i=1,j=2,k=2,无法再向下扩展,得到一个矩形。
④i=1,j=4,k=4,无法再向下扩展,得到一个矩形。
(2)其次搜索矩阵第二行,如图3.11所示。
i=2,j=3,k=3,可以向下扩展两层,得到3个矩形。
(3)再次搜索矩阵第三行,如图3.12所示。
①i=3,j=1,k=1,可以向下扩展一层,得到两个矩形。
图3.12 搜索矩阵第三行
②i=3,j=3,k=3,可以向下扩展一层,得到两个矩形。
③i=3,j=3,k=4,无法再向下扩展,得到一个矩形。
④i=3,j=4,k=4,无法再向下扩展,得到一个矩形。
(4)最后搜索矩阵第四行,如图3.13所示。
图3.13 搜索矩阵第四行
①i=4,j=1,k=1,无法再向下扩展,得到一个
矩形。②i=4,j=3,k=3,无法再向下扩展,得到一个
矩形。因
此,只要预处理出每个位置能向下扩展的最高
高度h[i][j],再在枚举k 的时候取min{h[i][j], 
h[i][j+1],…,h[i][k]},即可得到矩形的个数。
参考代码如下。 
for(int i = n; i >= 1; i--) //从下到上预处理每个位置可以向下扩展的最高高度
{ 
for(int j = 1; j <= n; j++) 
{ 
if(mp[i][j]) 
h[i][j]= 0; 
else

56 算法设计与问题求解(第2版·微课版) 
h[i][j]= h[i+1][j]+1; 
} 
}i
nt ans = 0; 
for(int i = 1; i <= n; i++) 
{ 
for(int j = 1; j <= n; j++) 
{ 
int hei = h[i][j]; //可扩展的高度 
for(int k = j; k <= n; k++) 
{ 
hei = min(h[i][k], hei); //可扩展的高度由最小值决定 
ans += hei; 
} 
} 
}
最终求得问题所示的矩阵中包含15个矩形。
.. 习 题
1.探囊取物 
小明有一个空的背包,容量为T ,他可以将两种数量无限的物品放入背包,物品a的体
积为A ,物品b的体积为B。小明可以按任意顺序将任意数量的两种物品放入包中,并且在
放的过程中他可以对物品进行一次体积压缩,可以在任意时刻使用,使得放入物品的总体积
从x 变为
x2
,小明在不超过背包容量的情况下能装的最大体积是多大。
输入描述:1行,3个整数T 、A 、B (1≤T ≤5000000,1≤A ,B ≤T ),分别表示背包容
量、物品a的体积、物品b的体积。
输出描述:1个正整数,不超过背包容量的情况下能装的最大体积。
2.数位乘积
给定一个n,求1~n 每一个数字每一位乘积的最大值。如1~234中最大的数位乘积
是199的数位乘积(1×9×9=81)。
输入描述:1行,1个正整数n(1≤n≤109)。
输出描述:1个正整数,表示最大数位乘积。
3.使其相等
给定一个数组,每次可以对数组中的一个数做以下操作中的一种。
(1)使x 变为
x2
。

第3章蛮力法57(2)使x变为2x。
问最少多少次操作可以使数组中的元素都相等。
输入描述: 
第一行1个整数n(1≤n≤105), 表示元素个数。
第二行n个用空格隔开的数ai(1≤ai≤105), 表示第i个元素的值。
输出描述:1行,1个整数,表示最少操作次数。
4.完美图
定义一个无向图为完美图,当且仅当对于其中每一条边(v,u)有v和u互质(即u、v的
最大公约数为1) 。当两个顶点之间没有边时不需要考虑。顶点从1开始标号。现给出n
个顶点和m条边,是否能建立一个无重边且连通的完美图? 
输入描述:1行,2个数n、m,表示顶点个数和边数(1≤n,m≤105) 。
输出描述:如果不存在答案输出-1。否则输出m行,每行输出vi,ui(1≤vi,ui≤n, 
vi≠ui) 。
5.统计数字
统计某个给定范围[L,R]的所有整数中,1~9分别出现了几次。
例如给定范围[1,11], 数字1在数1中出现了1次,在数10 中出现1次,在数11 中出

现
2 
次,所以数字1在该范围内一共出现了6次。
1≤L≤R≤10000 )。输入描述:输入共1行,2个正整数
L 
和R(
输出描述:1行,9个数,中间用逗号隔开,第
i 
个数表示数字
i 
在范围内出现的次数。

6. 
日期计算
小明给你一个日期,他想知道在该日期基础上经过
a 
天后的日期。
输入描述:1行,4个整数y、、d、a,分别表示给定日期的年、月、日和经过的天数。
输出描述:每组数据输出1行,1(m) 个结果,每行按yyyy-mm-dd 的格式输出。
数据范围: 
1000≤y≤3000 。
1≤m≤12 。
1≤d≤31 。
1≤a≤106。
保证输入日期合法。

7.01 
串
现有一个由0,01,011,0111,…组成的无限长01 串0010110111…, 试求第
n 
位上的是

0还是1。
输入描述:1行1个整数n(1≤n≤109)。
输出描述:1个数0或1,表示第
i 
位上的数为0还是1。


58算法设计与问题求解(第2版·微课版) 
8.迷宫问题
先给定一个n×n大小的迷宫,迷宫中有m处障碍和一处宝藏点(xp,yp) 。现给定起
点(xs,ys)和终点(xe,ye) 。
每个格子最多经过一次,有多少种从起点经过宝藏点到达终点的方案? 
每次选上、下、左、右中一个方向走一格,保证起点没有障碍。
输入描述: 
第一行,2个正整数n、m(1≤n≤5,1≤m≤n2) 。
第二行,起点坐标(xs,ys), 终点坐标(xe,ye), 宝藏点(xp,yp) 。
接下来m行,每行为障碍坐标。
输出描述:1个正整数,表示答案。
9.ABC成比例
先给定10 个数字0~9,从中取出9个数分成3组,分别组成3个3位数。让3个数的
比例为A∶B∶C,试求出所有满足的3个3位数,若无解输出NO 。
输入描述:1行,3个整数A、B、C(A<B<C) 。
输出描述:若干行,每行3个数字,按每行第一个数升序排列。
10. 
最大乘积
给定1个数字,请找到一个乘积最大的连续子序列。
输入描述: 
第一行1个数n(1≤n≤15), 表示数组长度。
第二行
n 
个数ai(-10≤ai≤10), 表示各个元素。