《《算法设计与分析》蛮力法》由会员分享，可在线阅读，更多相关《《算法设计与分析》蛮力法（30页珍藏版）》请在金锄头文库上搜索。
1、蛮力法1算法分析与设计蛮力法 Brute Force蛮力法（枚举法、穷举法，暴力法）要求设计者 找出所有可能的方法，然后选择其中的一种方法 ，若该方法不可行则试探下一种可能的方法。蛮力法是一种直接解决问题的方法，常常直接基 于问题的描述和所设计的概念定义。“力”指计算机的能力，而不是人的智力。蛮力法常常是最容易应用的方法。求an（n为非负整数）用连续整数检测算法计算GCD（m,n）2算法分析与设计蛮力法 Brute Force蛮力法不是一个最好的算法（巧妙和高效的算法 很少出自蛮力），但当我们想不出更好的办法时， 它也是一种有效的解决问题的方法。它可能是惟一一种几乎什么问题都能解决的一般 性方
2、法，常用于一些非常基本、但又十分重要的算 法，比如计算n个数字的和，求一个列表的最大元素等等。3算法分析与设计蛮力法的优点逻辑清晰，编写程序简洁对于一些重要的问题（比如：排序、查找、矩阵 乘法和字符串匹配），可以产生一些合理的算法解决问题的实例很少时，可以花费较少的代价可以解决一些小规模的问题（使用优化的算法没 有必要，而且某些优化算法本身较复杂）可以作为其他高效算法的衡量标准4算法分析与设计使用蛮力法的几种情况搜索所有的解空间 搜索所有的路径 直接计算 模拟和仿真5算法分析与设计比较熟悉的蛮力法应用选择排序和起泡排序选择排序：每趟排序在当前待排序序列中选出 关键码最小的记录，添加到有序序列中
3、。起泡排序：两两比较相邻记录关键码，如果反 序则交换，直到没有反序的记录为止。 顺序查找和蛮力字符串匹配顺序查找：从线性表的一端向另一端逐个将关 键码与给定值进行比较，若相等，则查找成功，给 出该记录在表中的位置；若整个表检测完仍未找到 与给定值相等的关键码，则查找失败，给出失败信 息。蛮力字符串匹配：即朴素模式串匹配 6算法分析与设计根据问题中的条件将可能的情况一一列举出 来，逐一尝试从中找出满足问题条件的解。但有 时一一列举出的情况数目很大，如果超过了我们 所能忍受的范围，则需要进一步考虑，排除一些 明显不合理的情况，尽可能减少问题可能解的列 举数目。用蛮力法解决问题，通常可以从两个方面进
4、行算 法设计：1）找出枚举范围：分析问题所涉及的各种情况。2）找出约束条件：分析问题的解需要满足的条件，并用 逻辑表达式表示。蛮力法解题步骤7算法分析与设计【例1】百钱钱百鸡问题鸡问题 。中国古代数学家张张丘建在他 的算经经中提出了著名的“百钱钱百鸡问题鸡问题 ”：鸡鸡翁 一，值钱值钱 五；鸡鸡母一，值钱值钱 三；鸡雏鸡雏 三，值钱值钱 一；百 钱买钱买 百鸡鸡，翁、母、雏雏各几何? 算法设计1：通过对问题的理解，可能会想到列出两个三元一次方程， 去解这个不定解方程，就能找出问题的解。这确实是一种 办法，但这里我们要用“懒惰”的枚举策略进行算法设计 ：设x，y，z分别为公鸡、母鸡、小鸡的数量。
5、尝试范围：由题意给定共100钱要买百鸡，若全买公鸡最多 买100/5=20只，显然x的取值范围120之间；同理，y的取 值范围在133之间，z的取值范围在1100之间。约束条件： x+y+z=100 且 5*x+3*y+z/3=100 8算法分析与设计算法1如下：main( ) int x,y,z;for(x=1;x和=记录称量结果。23算法分析与设计输出 输出假金币的编号。如果称量记录无法 确定假金币，输出0 输入样例： 5 3 2 1 2 3 4 1) break; /不止一枚假金币no=i; if(count!=1) printf(“0”); else printf(“%d”,no);
6、27算法分析与设计例5：用蛮力法解决凸包问题凸包问题：S是平面上的一个点集，封闭S中所 有顶点的最小凸多边形，称为S的凸包。凸包问题 就是为一个n个点的集合构造凸包的问题。 对于一个n个点集合中的两个点pi和pj，当且仅当 该集合中的其他点都位于穿过这两点的直线的同 一边时，它们的连线是该集合凸包边界的一部分 。例6 最近对问题 找出一个包含n个点的集合中距离最近的两个点。28算法分析与设计1、某地刑侦大队对涉及六个嫌疑人的一桩 疑案进行分析： A、B至少有一人作案； A、E、F三人中至少有两人参与作案； A、D不可能是同案犯； B、C或同时作案，或与本案无关； C、D中有且仅有一人作案； 如果D没有参与作案，则E也不可能参与作 案。 试设计算法将作案人找出来。练习29算法分析与设计2、将1,2.9共9个数分成三组,分别组成三个三 位数,且使这三个三位数构成1:2:3的比例,试求出 所有满足条件的三个三位数 Tip：如果我们不假思索地以每一个数位为枚举对 象，一位一位地去枚举，枚举次数就有9次，如 果我们分别设三个数为x,2x,3x，以x为枚举对象 ，穷举的范围就减少为9，在细节上再进一步优 化，枚举范围就更少了。30算法分析与设计
