蛮力法

1蛮力法2蛮力法BruteForce蛮力法（枚举法、穷举法，暴力法）是指基于计算机运算速度快这一特性，在解决问题时不经过（或者说经过很少）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所设计的概念定义。“力”－－指计算机的运算能力，而不是人的智力。3蛮力法的优点逻辑清晰，编写程序简洁对于一些重要的问题（比如：排序、查找、矩阵乘法和字符串匹配），可以产生一些合理的算法解决问题的实例很少时，可以花费较少的代价可以解决一些小规模的问题（使用优化的算法没有必要，而且某些优化算法本身较复杂）可以作为其他高效算法的衡量标准4蛮力法主要应用选择排序和起泡排序选择排序：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。起泡排序：两两比较相邻记录关键码，如果反序则交换，直到没有反序的记录为止。顺序查找和蛮力字符串匹配顺序查找：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。蛮力字符串匹配：即朴素模式串匹配5根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用蛮力法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。蛮力法解题步骤例1百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，可能会想到列出两个三元一次方程，去解这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设x，y，z分别为公鸡、母鸡、小鸡的数量。尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多买100/5=20只，显然x的取值范围1~20之间；同理，y的取值范围在1~33之间，z的取值范围在1~100之间。约束条件：x+y+z=100且5*x+3*y+z/3=1007算法1如下：main(){intx,y,z;for(x=1;x=20;x=x+1)for(y=1;y=33;y=y+1)for(z=1;z=100;z=z+1)if(100==x+y+z&&100==5*x+3*y+z/3){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberis，z);}}枚举尝试20*33*100=66000次8算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了此时约束条件只有一个：5*x+3*y+z/3=100算法2如下：9main(){intx,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&&5*x+3*y+z/3==100){print(thecocknumberis,x)；print(thehennumberis,y)；print(thechicknumberis,z);}}}枚举尝试20*33=660次Z能被3整除时，才会判断“5*x+3*y+z/3=10010例2求所有的三位数，它除以11所得的余数等于它的三个数字的平方和。解题思路：三位数只有900个，可用枚举法解决，枚举时可先估计有关量的范围，以缩小讨论范围，减少计算量。解：设这个三位数的百位、十位、个位的数字分别为x，y，z。由于任何数除以11所得余数都不大于10，所以x2+y2+z2≤10，从而1≤x≤3，0≤y≤3，0≤z≤3。所求三位数必在以下数中：100，101，102，103，110，111，112，120，121，122，130，200，201，202，211，212，220，221，300，301，310。不难验证只有100，101两个数符合要求。12例3解数字迷ABCAB×ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9,B：0——9,C：0——9六位数表示:A*10000+B*1000+C*100+A*10+B,尝试700次。2)约束条件为：每次尝试，先求5位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。13算法1如下：main（）{intA,B,C,D,E,E1,F,G1,G2,i;for(A=3;A=9;A++)for(B=0;B=9;B++)for(C=0;C=9;C++){F=A*10000+B*1000+C*100+A*10+B;E=F*A；E1=E;G1=E1mod10;for(i=1;i=5;i++){G2=G1;E1=E1/10;G1=E1mod10;if(G1G2)break;}if(i=6)print(F，”*”，A，”=”，E);}}14算法设计2：将算式变形为除法：DDDDDD/A=ABCAB。此时只需枚举A：3——9D：1——9，共尝试7*9=63次。每次尝试，测试商的万位、十位与除数是否相同，千位与个位是否相同，都相同时为解。15main（）{intA,B,C,D,E,F;for(A=3;A=9;A++)for(D=1;D=9;D++){E=D*100000+D*10000+D*1000+D*100+D*10+D;if(EmodA=0)F=E\A;if(F\10000=Aand(Fmod100)\10=A)and(F\1000=Fmod10)print(F，”*”，A，”=”，E);}}16总结蛮力法不是一个巧妙和高效的算法，但当我们想不出更好的办法时，它也是一种有效的解决问题的方法。它可能是惟一一种几乎什么问题都能解决的一般性方法，常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素等等。蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。