算法设计与分析 课件 第二章 蛮力法.pptx

计算机算法设计与分析;学习目标;2.1蛮力法概述;2.1蛮力法概述;2.1蛮力法概述;2.2蛮力法的设计思想;为了避免陷入重复验证，应保证验证过的可能解不再被验证。对于线性问题来说，处理次序依次即可，而对于非线性问题，就需要用到一些特定的方法，比如树形结构的前序遍历、中序遍历和后序遍历；图结构的宽度优先有哪些信誉好的足球投注网站和深度优先有哪些信誉好的足球投注网站等。

在设计时一般都是用循环语句和判断语句来实现。使用循环是枚举所有的情况，使用判断是验证当前的状态是否满足问题的所有条件。若满足，则找到问题的一个解，可以结束，如需要求其他解，则继续循环；若不满足，则继续循环验证其他状态。;2.2蛮力法的设计思想;2.2蛮力法的设计思想;2.2蛮力法的设计思想;2.2蛮力法的设计思想;2.2蛮力法的设计思想;2.3蛮力法的典型实例;2.3.1蛮力法的典型实例——0-1背包问题;2.问题分析

确定解的表示形式：每种物品要么装入背包，要么不装入背包，分别用1和0表示，总共有n种物品，因此解的表示形式为n维的0-1向量，解的范围有2n种组合。

穷举方法：当n比较小时，规模不大，使用蛮力法是可行的。用一个0～2n-1中的整数的二进制形式来代表某种组合，二进制对应位数为1的表示装入对应的第i个物品。比如，假设n=5，用6=(00110)2，它的第2，3位为1，则代表装入第2，3种物品。

约束条件：装入的物品重量和要≤背包的承重量C。目标是在满足条件情况下总价值最大。对于每种符合条件的物品组合其总价值可以很方便计算出来，然后判断是否大于前面验证过的组合物品总价值，若是，则将最大值更新，否则，最大值不变。;2.3.1蛮力法的典型实例——0-1背包问题;2.3.1蛮力法的典型实例——0-1背包问题;4.算法效率分析

该算法时间复杂度为，当n的规模较小时，该算法有效。当n较大时，蛮力法比较难以在规定时间内得出结果。当然上述的算法还可以优化，比如当某个物品组合超过承重量C时，那么包含以上组合的肯定都超过C，因此这样的组合就不必验证，直接跳过，这样可以减少一些验证，提高效率。但无论如何，蛮力法求解0-1背包问题总有局限性，其实求解该问题还有更好的方法，比如动态规划法，这个在后续的章节里介绍。;2.3.2蛮力法的典型实例——全排列问题;2.问题分析

算法一：增量法。假设n=3，增量法产生1～3的全排列过程如下：首先初始化数列为[1]，然后将2插入到1的前后两个位置得数列[1,2]和[2,1]，继续将3插入以上两个数列的3个位置得到6个数列[1,2,3]，[1,3,2]，[3,1,2]，[2,1,3]，[2,3,1]，[3,2,1]。过程如下图所示。

虽然增量法思路简单，但需要存储大量的中间结果，所以空间复杂度比较高。

;2.问题分析

算法二：递归法。对于给定的数组，先确定序列的第一个元素，剩余的序列又可以看成是一个不包含第一个元素的全排列。对剩余的序列重复这样的操作，直到剩余序列中只一个元素为止。这样就获得了所有的可能序列。这是一个递归的过程。整个过程如下图所示：

;3.总结递归算法求全排列（蛮力法）

(1)n个元素的全排列=（一个元素作为前缀）+（剩下n-1个元素的全排列）；

(2)结束：如果只有一个元素的全排列，说明已经排完，输出数组；

(3)不断将每个元素放作第一个元素，然后将这个元素作为前缀，并将其余元素继续全排列，等到结束。出去后还需要还原数组。

;2.3.2蛮力法的典型实例——全排列问题;例2.2五星填数。在五星图案结点填上数字1~12，不包括7和11。要求每条直线上数字和相等。如图2.3就是一个恰当的填法。请有哪些信誉好的足球投注网站所有可能的填法有多少种。注意：旋转或镜像后相同的算同一种填法。;分析：上述问题将1～12，不包括7和11，按不同顺序填入圆圈中，其实是一个以上10个数的一种排列，如果验证5条线的数字和相等就是一种正确的填法。把所有的排列一一验证，这样就可以统计出全部正确的填法。所以该问题的核心就是一个全排列的问题。

解：经过上述的分析，整个求解过程分为3步：

①写出1～12不包括7和11的全排列；

②判断每条线上的4个数字和是否相等，若都相等则是正确的填法，其填法的计数加1；

③剔除旋转和镜像，因为五角星旋转和镜像都属于同一种填法，因此，最终应该在全部正确的填法种数上除以10。;具体实现过程如下：

（1）先来定义五星数组，因为全排列中没用到数字0，所以定义数组时下标为0的不用。

intstar[]={0,1,2,3,4,5,6,8,9,10,12};//0不用

（2）定义5条直线数字的和。

#defineA(star[1]+star[3]+star[6]+star[9])

#defineB(star[1]+star[4]+star[7