蛮力法复习进程.ppt

《蛮力法复习进程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、蛮力法1蛮力法BruteForce蛮力法（枚举法、穷举法，暴力法）是指基于计算机运算速度快这一特性，在解决问题时不经过（或者说经过很少）思考，把问题的所有情况或所有过程交给计算机去一一尝试，从中找出问题的解。蛮力法是一种直接解决问题的方法，常常直接基于问题的描述和所设计的概念定义。“力”－－指计算机的运算能力，而不是人的智力。2蛮力法的优点逻辑清晰，编写程序简洁对于一些重要的问题（比如：排序、查找、矩阵乘法和字符串匹配），可以产生一些合理的算法解决问题的实例很少时，可以花费较少的代价可以解决一些小规模的问题（使用优化的算法没有必要，而且某

2、些优化算法本身较复杂）可以作为其他高效算法的衡量标准3蛮力法主要应用选择排序和起泡排序选择排序：每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。起泡排序：两两比较相邻记录关键码，如果反序则交换，直到没有反序的记录为止。顺序查找和蛮力字符串匹配顺序查找：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。蛮力字符串匹配：即朴素模式串匹配4根据问题中的条件将可能的情况一一列举出来，逐一尝试从中找出满足问题条件的解

3、。但有时一一列举出的情况数目很大，如果超过了我们所能忍受的范围，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。用蛮力法解决问题，通常可以从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。蛮力法解题步骤5例1百钱百鸡问题。中国古代数学家张丘建在他的《算经》中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?算法设计1：通过对问题的理解，可能会想到列出两个三元一次方程，去解

4、这个不定解方程，就能找出问题的解。这确实是一种办法，但这里我们要用“懒惰”的枚举策略进行算法设计：设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=1006算法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

5、;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次7算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了此时约束条件只有一个：5*x+3*y+z/3=100算法2如下：8main(){ intx,y,z;    for(x=1;x<

6、=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=1009例2求所有的三位数，它除以11所得的余数等于它的三个数字

7、的平方和。解题思路：三位数只有900个，可用枚举法解决，枚举时可先估计有关量的范围，以缩小讨论范围，减少计算量。10解：设这个三位数的百位、十位、个位的数字分别为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两个数符合要求。11例3解数字迷ABCAB×

8、ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9,B：0——9,C：0——9六位数表示:A*10000+B*1000+C*100+A*10+B,尝试700次。2)约束条件为：每