《算法设计与分析》蛮力法.ppt

算法分析与设计,1,蛮力法,算法分析与设计,2,蛮力法 Brute Force,蛮力法（枚举法、穷举法，暴力法）要求设计者找出所有可能的方法，然后选择其中的一种方法，若该方法不可行则试探下一种可能的方法。蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所设计的概念定义。“力”指计算机的能力，而不是人的智力。蛮力法常常是最容易应用的方法。求an（n为非负整数）用连续整数检测算法计算GCD（m,n）,算法分析与设计,3,蛮力法 Brute Force,蛮力法不是一个最好的算法（巧妙和高效的算法很少出自蛮力），但当我们想不出更好的办法时，它也是一种有效的解决问题的方法。它可能是惟一一种几乎什么问题都能解决的一般性方法，常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素等等。,算法分析与设计,4,蛮力法的优点,逻辑清晰，编写程序简洁对于一些重要的问题（比如：排序、查找、矩阵乘法和字符串匹配），可以产生一些合理的算法解决问题的实例很少时，可以花费较少的代价可以解决一些小规模的问题（使用优化的算法没有必要，而且某些优化算法本身较复杂）可以作为其他高效算法的衡量标准,算法分析与设计,5,使用蛮力法的几种情况,搜索所有的解空间搜索所有的路径直接计算模拟和仿真,算法分析与设计,6,比较熟悉的蛮力法应用,选择排序和起泡排序选择排序：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。起泡排序：两两比较相邻记录关键码，如果反序则交换，直到没有反序的记录为止。顺序查找和蛮力字符串匹配顺序查找：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。蛮力字符串匹配：即朴素模式串匹配,算法分析与设计,7,根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用蛮力法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。,蛮力法解题步骤,【例1】百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围120之间；同理，y的取值范围在133之间，z的取值范围在1100之间。约束条件：x+y+z=100 且 5*x+3*y+z/3=100,算法分析与设计,9,算法1如下：main()int x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=34;y=y+1)for(z=1;z=100;z=z+1)if(100=x+y+z,枚举尝试20*34*100=68000次,算法分析与设计,10,算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了此时约束条件只有一个：5*x+3*y+z/3=100算法2如下：,算法分析与设计,11,main()int x,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)z=100-x-y;if(z%3=0,枚举尝试20*33=660次,Z能被3整除时，才会判断“5*x+3*y+z/3=100,算法分析与设计,12,例2,求所有的三位数，它除以11所得的余数等于它的三个数字的平方和。解题思路：三位数只有900个，可用枚举法解决，枚举时可先估计有关量的范围，以缩小讨论范围，减少计算量。,解：设这个三位数的百位、十位、个位的数字分别为x，y，z。由于任何数除以11所得余数都不大于10，所以x2+y2+z210，从而1x3，0y3，0z3。所求三位数必在以下数中：100，101，102，103，110，111，112，120，121，122，130，200，201，202，211，212，220，221，300，301，310。不难验证只有100，101两个数符合要求。,例3 狱吏问题 某国王对囚犯进行大赦，让一狱吏n次通过一排锁着的n间牢房，每通过一次，按所定规则转动n间牢房中的某些门锁,每转动一次,原来锁着的被打开,原来打开的被锁上；通过n次后，门锁开着的，牢房中的犯人放出，否则犯人不得获释。转动门锁的规则是这样的，第一次通过牢房，要转动每一把门锁，即把全部锁打开；第二次通过牢房时，从第二间开始转动，每隔一间转动一次；第k次通过牢房，从第k间开始转动，每隔k-1 间转动一次；问通过n次后，哪些牢房的锁仍然是打开的？,算法分析与设计,15,算法设计1：1）一维数组an记录n个锁的状态 1:被锁上 0:被打开2）对i号锁的一次开关锁可以转化为算术运算：ai=1-ai。3）第一次转动的是1，2，3，n号牢房；第二次转动的是2，4，6，号牢房；第i次转动的是i，2i，3i，4i，号牢 房，是起点为i，公差为i的等差数列。4）不做其它的优化，用蛮力法通过循环模拟狱吏的开关锁过程，最后当第i号牢房对应的数组元素ai为0时，该牢房的囚犯得到大赦。,算法分析与设计,16,算法1如下：input(n);/输入n a=new int(n+1);for(i=1;i=n;i+)ai=1;for(i=1;i=n;i+)for(j=i;j=n;j=j+i)ai=1-ai;for(i=1;i=n;i+)if(ai=0)print(i,”is free.”);算法分析：以一次开关锁计算，算法的时间复杂度为n(1+1/2+1/3+1/n)=O(nlogn)。,问题分析：转动门锁的规则可以有另一种理解，第一次转动的是编号为1的倍数的牢房；第二次转动的是编号为2的倍数的牢房；第三次转动的是编号为3的倍数的牢房；则狱吏问题是一个关于因子个数的问题。令d(n)为自然数n的因子个数，这里不计重复的因子，如4的因子为1，2，4共三个因子，而非1，2，2，4。则d(n)有的为奇数，有的为偶数，见下表:表1 编号与因数个数的关系,算法分析与设计,18,数学模型1：上表中的d(n)有的为奇数，有的为偶数，由于牢房的门开始是关着的，这样编号为i的牢房，所含1i之间的不重复因子个数为奇数时，牢房最后是打开的，反之，牢房最后是关闭的。,算法分析与设计,19,算法设计2:1）算法应该是求出每个牢房编号的不重复的因子个数，当它为奇数时，这里边的囚犯得到大赦。2）一个数的因子是没有规律的，只能从1n枚举尝试。算法2如下：input(n);for(i=1;i=n;i+)s=1;for(j=2;j=i;j=j+)if（ij=0）s=s+1;if（s2=1）print(i,”is free.”);,算法分析与设计,20,算法分析：算法1中狱吏开关锁的主要操作是ai=1-ai;共执行了n*(1+1/2+1/3+1/n)次，时间近似为复杂度为O（n log n）。使用了n个空间的一维数组。算法2没有使用辅助空间，但由于求一个编号的因子个数也很复杂，其主要操作是判断i mod j是否为0，共执行了n*(1+2+3+n)次，时间复杂度为O（n2）。仔细观察表1,算法分析与设计,21,数学模型2：观察表1，发现当且仅当n为完全平方数时,d(n)为奇数；这是因为n的因子是成对出现的,也即当n=a*b且ab时，必有两个因子a，b;只有n为完全平方数，也即当n=a2时,才会出现d(n)为奇数的情形。算法设计3：这时只需要找出小于n的平方数即可。,算法分析与设计,22,算法3如下：input(n);for(i=1;i=n;i+)if（i*i=n）print(i,”is free.”);else break;注意：在对运行效率要求较高的大规模的数据处理问题时，必须多动脑筋找出效率较高的数学模型及其对应的算法。,算法分析与设计,23,例4 假金币,N个金币（编号为1N）中有一枚重量不同的假金币（真金币重量相同），利用唯一的一台天平将金币分组称量可以找出假金币。输入：第一行输入2个空格隔开的整数N和K，N是金币的总数（21000），K是称重的次数（1100）。随后2K行记录称量的情况和结果，连续2行记录一次称量：第1行首先是Pi(1N/2)，表示两边托盘放置的金币数目，随后是左边托盘中Pi个金币编号和右边托盘中Pi个金币编号，所有数之间都由空格隔开；第2行用和=记录称量结果。,算法分析与设计,24,输出输出假金币的编号。如果称量记录无法确定假金币，输出0输入样例：5 32 1 2 3 41 1 41 2 5,输出样例：3,算法分析与设计,25,搜索过程,依次假设i号金币是假的对称量的记录进行比较，如果假设与所有的记录都不矛盾，则有可能是假的如果可能的假金币只有1个，输出他的编号，否则，输出0,算法分析与设计,26,Int jd(int j,int*s,char c)/函数判断假设j金币是假的与称量结果是否矛盾/s是称量结果，其第一个元素是左托盘中金币的个数，c是称量结果m=2*s0;for(i=f=1;i=m,算法分析与设计,27,int main()int num1001000;char s1000;/输入内容for(i=1,count=0;i1)break;/不止一枚假金币 no=i;if(count!=1)printf(“0”);else printf(“%d”,no);,算法分析与设计,28,例5：用蛮力法解决凸包问题,凸包问题：S是平面上的一个点集，封闭S中所有顶点的最小凸多边形，称为S的凸包。凸包问题就是为一个n个点的集合构造凸包的问题。对于一个n个点集合中的两个点pi和pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时，它们的连线是该集合凸包边界的一部分。例6 最近对问题找出一个包含n个点的集合中距离最近的两个点。,算法分析与设计,29,1、某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：A、B至少有一人作案；A、E、F三人中至少有两人参与作案；A、D不可能是同案犯；B、C或同时作案，或与本案无关；C、D中有且仅有一人作案；如果D没有参与作案，则E也不可能参与作案。试设计算法将作案人找出来。,练习,算法分析与设计,30,2、将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数 Tip：如果我们不假思索地以每一个数位为枚举对象，一位一位地去枚举，枚举次数就有9次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为9，在细节上再进一步优化，枚举范围就更少了。,