算法设计与分析蛮力法

算法分析与设计
3
使用蛮力法的几种情况
• 搜索所有的解空间 • 搜索所有的路径 • 直接计算 • 模拟和仿真
算法分析与设计
4
比较熟悉的蛮力法应用
• 选择排序和起泡排序
– 选择排序：每趟排序在当前待排序序列中选出关键码 最小的记录，添加到有序序列中。
– 起泡排序：两两比较相邻记录关键码，如果反序则交 换，直到没有反序的记录为止。
main( ) { int x,y,z;
枚举尝试20*33=660次
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("the cock number is",x)；
print("the hen number is", y)；
例3 狱吏问题
某国王对囚犯进行大赦，让一狱吏n次通过一排 锁着的n间牢房，每通过一次，按所定规则转动n间牢 房中的某些门锁, 每转动一次, 原来锁着的被打开, 原来打开的被锁上；通过n次后，门锁开着的，牢房 中的犯人放出，否则犯人不得获释。
转动门锁的规则是这样的，第一次通过牢房， 要转动每一把门锁，即把全部锁打开；第二次通过牢 房时，从第二间开始转动，每隔一间转动一次；第k 次通过牢房，从第k间开始转动，每隔k-1 间转动一 次；问通过n次后，哪些牢房的锁仍然是打开的？
算法设计1： 1）一维数组a[n]记录n个锁的状态
1:被锁上 0:被打开
2）对i号锁的一次开关锁可以转化为算术运算：
a[i]=1-a[i]。 3）第一次转动的是1，2，3，……，n号牢房；
第二次转动的是2，4，6，……号牢房； 第i次转动的是i，2i，3i，4i，……号牢 房，是起点为i，公差为i的等差数列。
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两个数符合要求。
• 顺序查找和蛮力字符串匹配
– 顺序查找：从线性表的一端向另一端逐个将关键码与 给定值进行比较，若相等，则查找成功，给出该记录 在表中的位置；若整个表检测完仍未找到与给定值相 等的关键码，则查找失败，给出失败信息。
– 蛮力字符串匹配：即朴素模式串匹配
算法分析与设计
5
蛮力法解题步骤
根据问题中的条件将可能的情况一一列举出 来，逐一尝试从中找出满足问题条件的解。但有 时一一列举出的情况数目很大，如果超过了我们 所能忍受的范围，则需要进一步考虑，排除一些 明显不合理的情况，尽可能减少问题可能解的列 举数目。
4）不做其它的优化，用蛮力法通过循环模拟狱 吏的开关锁过程，最后当第i号牢房对应的数 组元素a[i]为0时，该牢房的囚犯得到大赦。
算法分析与设计
14
算法1如下：
input(n);//输入n
a=new int(n+1);
for (i=1; i<=n;i++)
a[i]=1;
for (i=1; i<=n;i++)
print("the chick number is ",z);} } }
算法分析与设计
10
例2
• 求所有的三位数，它除以11所得的余数等 于它的三个数字的平方和。
解题思路：三位数只有900个，可用枚举 法解决，枚举时可先估计有关量的范围， 以缩小讨论范围，减少计算量。
算法分析与设计
11
• 解：设这个三位数的百位、十位、个位的数字分别为 x，y，z。由于任何数除以11所得余数都不大于10， 所以
if(100==x+y+z&&100==5*x+3*y+z/3) {print("the cock number is",x)； print("the hen number is", y)；
print("the chick number is "，z);} }
算法分析与设计
8
算法分析与设计
9
Z能被3整除时，才会判断“5*x+3*y+z/3=100
for (j=i; j<=n;j=j+i)
a[i]=1-a[i];
for (i=1; i<=n;i++)
if (a[i]=＝0)
print(i,”is free.”);
算法分析：以一次开关锁计算，算法的时间复杂度
用蛮力法解决问题，通常可以从两个方面进行算 法设计：
1）找出枚举范围：分析问题所涉及的各种情况。
2）找出约束条件：分析问题的解需要满足的条件，并用 逻辑表达式表示。
算法分析与设计
6
算法分析与设计
百度文库
7
算法1如下： main( ) 枚举尝试20*34*100=68000次 { int x,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)
– 求an（n为非负整数） – 用连续整数检测算法计算GCD（m,n）
算法分析与设计
1
蛮力法 Brute Force
• 蛮力法不是一个最好的算法（巧妙和高效的算法 很少出自蛮力），但当我们想不出更好的办法时， 它也是一种有效的解决问题的方法。
• 它可能是惟一一种几乎什么问题都能解决的一般 性方法，常用于一些非常基本、但又十分重要的 算法，比如计算n个数字的和，求一个列表的最 大元素等等。
蛮力法 Brute Force
• 蛮力法（枚举法、穷举法，暴力法）要求设计 者找出所有可能的方法，然后选择其中的一种 方法，若该方法不可行则试探下一种可能的方 法。
• 蛮力法是一种直接解决问题的方法，常常直接 基于问题的描述和所设计的概念定义。
• “力”－－指计算机的能力，而不是人的智力。
• 蛮力法常常是最容易应用的方法。
算法分析与设计
2
蛮力法的优点
• 逻辑清晰，编写程序简洁 • 对于一些重要的问题（比如：排序、查找、矩阵
乘法和字符串匹配），可以产生一些合理的算法 • 解决问题的实例很少时，可以花费较少的代价 • 可以解决一些小规模的问题（使用优化的算法没
有必要，而且某些优化算法本身较复杂） • 可以作为其他高效算法的衡量标准