资源描述：
《机算法设计与分析基础第三章蛮力法2.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第三章蛮力法1第3章蛮力法概述枚举法选择排序冒泡排序顺序查找字符串匹配最近对凸包穷举查找本章习题2蛮力法概述前面介绍了效率分析的框架与方法。本章开始，讨论算法设计技术蛮力法——一种最简单、最直接的算法设计方法（直接基于问题本身）——直接干吧！（最容易想到）一个简例已知：数字a和非负整数n，要求：设计计算an值的算法蛮力算法：策略：直接基于问题定义来设计算法——把a和a相乘n次其他蛮力策略应用——选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配——比较常用还有枚举法、盲目搜索算法等。3蛮力法特点——算法设计简单直接，相对容易——算法效率一般
2、不高，高效算法很少源于蛮力法蛮力法应用——仍是一种重要的算法设计方法1.解决各种问题的一般方法。常用于一些很基本又重要的算法——计算n个数的和。——求列表的最大元素，……2.对于一些重要算法（如排序、查找、矩阵乘法、字符串匹配），蛮力法可产生一些合理的算法，多少具有一些实用价值。3.规模不大的问题，蛮力法的速度又可以接受时，要设计一种高效算法所付出的代价很可能不值得（必要性）4.蛮力法可作为尺度，去衡量解决同样问题的其他算法的效率41枚举法枚举法（穷举法）是蛮力策略的一种表现形式，根据问题中条件将可能情况一一列举出来，逐一尝试从中找出满足问题条件
3、的解。但有时一一列举出的情况数目很大，则需要进一步考虑，排除一些明显不合理的情况，尽可能减少问题可能解的列举数目。通常从两个方面进行算法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示。5【例3-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<=34;y=y+1) for(z=1;z<=100;z=z+1) if(100=x+y+zand100=5*x+3*
5、y+z/3) {print("thecocknumberis",x)；print("thehennumberis",y)；print("thechicknumberis",z);} }算法分析：此算法需要枚举尝试20*34*100=68000次。算法的效率显然太低。7算法设计2：在公鸡（x）、母鸡（y）的数量确定后，小鸡的数量z就固定为100-x-y，无需再进行枚举了。此时约束条件只有一个：5*x+3*y+z/3=100.8main() {intx,y,z; for(x=1;x<=20;x=x+1)
6、 for(y=1;y<=33;y=y+1){ z=100-x-y; if(zmod3=0and5*x+3*y+z/3=100) {print("thecocknumberis",x)；print("thehennumberis",y)；print("thechicknumberis",z);} } }算法分析：以上算法只需枚举尝试20*33=660次。实现时约束条件限定Z能被3整除时，才
7、判断“5*x+3*y+z/3=100”。这样省去了z不整除3时的算术运算和条件判断，进一步提高了算法效率。9【例】解数字迷ABCAB×ADDDDDD算法设计1：按乘法枚举1)枚举范围为：A：3——9,B：0——9,C：0——9六位数表示:A*10000+B*1000+C*100+A*10+B,尝试800次。2)约束条件为：每次尝试，先求六位数与A的积，再测试积的各位是否相同，若相同则找到了问题的解。测试积的各位是否相同比较简单的方法是，从低位开始，每次都取数据的个位，然后整除10，使高位的数字不断变成个位，并逐一比较。A=1,2时积不会得到六位数
8、10算法1如下：main（）{intA,B,C,D,E,E1,F,G1,G2,i;for(A=3;A<=9;A++)for(B=0;B<
