第 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), 表示各个元素。