算法设计与分析蛮力法.pptx

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