第3章 蛮力法3.1 蛮力法的设计思想 3.2 查找问题中的蛮力法
3.3 排序问题中的蛮力法3.4 组合问题中的蛮力法 3.5 图问题中的蛮力法 3.6 几何问题中的蛮力法 3.7 实验项目——蛮力法的实践
3.1 蛮力法的设计思想蛮力法的设计思想：直接基于问题的描述。
例：计算anan=a×a×…×a
n次
蛮力法所赖的基本技术——扫描技 术
关键——依次处理所有元素 基本的扫描技术——遍历
(1)集合的遍历 (2)线性表的遍历
(3)树的遍历(4)图的遍历
虽然巧妙和高效的算法很少来自于蛮力法，基于 以下原因，蛮力法也是一种重要的算法设计技术：(1)理论上，蛮力法可以解决可计算领域的各种问题。
(2)蛮力法经常用来解决一些较小规模的问题。(3)对于一些重要的问题蛮力法可以产生一些合理的算 法，他们具备一些实用价值，而且不受问题规模的限制。
(4)蛮力法可以作为某类问题时间性能的底限，来衡量 同样问题的更高效算法。
3.2 查找问题中的蛮力法3.2.1 顺序查找3.2.2 串匹配问题
3.2.1 顺序查找顺序查找从表的一端向另一端逐个将元素与给定值进行 比较，若相等，则查找成功，给出该元素在表中的位置；若 整个表检测完仍未找到与给定值相等的元素，则查找失败， 给出失败信息。0 1 2 3 24 4 5 6 7 8 9 55 i
10 15
6 12 35 查找方向
40 98
算法3.1——顺序查找
int SeqSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { 基本语句 ？ i=n; while (i>0 && r[i]!=k) i--; return i; }算法3.1的基本语句是i>0和r[i]!=k,其执行次数为:
1 n 1 n pibi pi ci (n i 1) (n i 1) n 1 O(n) n i 1 n i 1 i 1 i 1
n
n
改进的顺序查找将待查值放在查找方向的尽头处，免去了在查找过 程中每一次比较后都要判断查找位置是否越界，从 而提高了查找速度。0k 哨兵 查找方向
1
2
3
4
5
6
7
8
9
10 15 24 6
12 35 40 98 55 i
算法3.2——改进的顺序查找
int SeqSearch2(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { r[0]=k; i=n; while (r[i]!=k) i --; return i; } 算法3.2的基本语句是r[i]!=k,其执行次数为:
1 n n 1 pi ci (n i 1) O(n) n i 1 2 i 1n
数量级相同， 系数相差一半
一般观点：用蛮力法设计的算法，一般来说，经过适度的 努力后，都可以对算法的第一个版本进行一定程度 的改良，改进其时间性能，但只能减少系数，而数 量级不会改变。
3.2.2 串匹配问题串匹配问题——给定两个串S=“s1s2…sn” 和T=“t1t2…tm”,在 主串S中查找子串T的过程称为串匹配，也称模式匹配。
串匹配问题属于易解问题。 串匹配
问题的特征：(1)算法的一次执行时间不容忽视：问题规模 n 很大， 常常需要在大量信息中进行匹配；(2)算法改进所取得的积累效益不容忽视：串匹配操作 经常被调用，执行频率高。
蛮力法解决串匹配问题——BF算法
基本思想：从主串S的第一个字符开始和模式T的第一个 字符进行比较，若相等，则继续比较两者的后续字符；若不 相等，则从主串 S 的第二个字符开始和模式 T 的第一个字符 进行比较，重复上述过程，若T中的字符全部比较完毕，则 说明本趟匹配成功；若最后一轮匹配的起始位置是n-m,则 主串 S 中剩下的字符不足够匹配整个模式 T ,匹配失败。这 个算法称为朴素的模式匹配算法，简称BF算法。
本趟匹配开始位置 回溯 主串S
i
si…模式T
……
tj回溯
j
设主串s=“ababcabcacbab”,模式t=“abcaci ii i
第 趟
a bajj
acj
b c a
b c
a
c b
a
b
1
bj
i=3,j=3失败； i回溯到2,j回溯到1
第 趟
i
i
a b a b c a b c a c b a bajj i
2 第 趟 3
i=2,j=1失败 i回溯到3,j回溯到1iii i i
a b a b c a b c a c b aa b c a cjj j j j j
b
i=7,j=5失败 i回溯到4,j回溯到1
第 趟
i
i
a b a b c a b c a c b aajji i
b
4
i=4,j=1失败 i回溯到5,j回溯到1
第 趟
a b a b c a b c a c b aajj
b
5
i=5,j=1失败 i回溯到6,j回溯到1
第 趟
i
i
i
i i
i
6
…… 此处隐藏157字 ……
BF C++
设串S长度为n,串T长度为m,在匹配成功的情况下， 考虑最坏情况，即每趟不成功的匹配都发生在串T的最后一 个字符。 例如：S="aaaaaaaaaaab" T="aaab" 设匹配成功发生在si处，则在i-1趟不成功的匹配中共 比较了 (i-1)×m 次，第 i 趟成功的匹配共比较了 m 次，所 以总共比较了i×m次，因此平均比较次数是：n m 1
1 m(n m 2) (i m) pi (i m) 2 i 1 i 1 n m 1
n m 1
3.3 排序问题中的蛮力法3.3.1 选择排序 3.3.2 起泡排序
3.3.1 选择排序选择排序第 i 趟排序从第 i 个记录开始扫描序列，在 n-i+1 (1≤i≤n-1)个记录中找到关键码最小的记录，并和第i个记 录交换作为有序序列的第i个记录。交换
r1 ≤r2 … … ≤ri-1 ri ri+1 … rmin … rn有序区 已经位于最终位置 无序区 rmin为无序区的最小记录