掌握蛮力法的基本思想，了解排序和查找问题的 蛮力算法。
4
选择排序
A[min]
5
算法 BubbleSort(A[0..n-1])
//该算法用冒泡排序对数组A[0..n-1]排序 //输入：一个可排序的数组A //输出：非降序排列的数组
for i0 to n-2 do for j0 to n-2-i do if A[j+1]<A[j] swap A[j] and A[j+1]
凸包问题是为一个n个点的集合构造凸包的问题。 极点：对于任何一集合中的点为端点的线段来说，它们不
是这种线段的中点。
对于一个n个点集合中的两 个点Pi和Pj，当且仅当该集 合中的其他点都位于穿过 这两点的直线的同一边时 它们的连线是该集合凸包 边界的一部分。 直线方程：ax+by=c a=y2-y1 , b=x1-x2, c=x1y2-y1x2
蛮力法的主要优点是它广泛的适用性和简单性； 它的主要缺点是大多数蛮力算法的效率都不高。
除了相关问题的一些规模非常小的实例，穷举查 找法几乎是不实用的。
16
习题3.2-10 找词游戏
习题3.2-11海战游戏
习题3.4-9 幻方
幻方是我国古代的一种智力游戏， 它是在N × N 的矩阵方格中填入 1...N 2 的正整数， 使得其每行每 列及对角线的和相等。
常常直接基于问题的描述和所涉及的概念 定义。
2
蛮力法的优点
可以用来解决广阔领域的问题 对于一些重要的问题，它可以产生一些合理的
算法 解决问题的实例很少时，它让你花费较少的代
价 可以解决一些小规模的问题 可以作为其他高效算法的衡量标准
3
教学内容
选择排序和冒泡排序 顺序查找和蛮力字符串匹配 最近对核凸包问题的蛮力算法 穷举查找 要求
15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11
习题3.4-10
12
旅行商问题
穷举查找
13
背包问题
穷举查找
14
穷举查找
分配问题
N个任务分配给n个人，任务j分配给人i的成本是C[I,j]
任务1
任务2
任务3
任务4
人员1
9
2
7
8
人员2
6
4
3
7
人员3
5
8
1
8
人员4
7
6
9
4
15
小结
蛮力法是一种简单直接地解决问题的方法，通常 直接基于问题的描述和所涉及的概念定义。
算法分析与设计
Analysis and Design of Computer Algorithms
第三章 蛮力法 Brute Force
蛮力法
就像宝剑不是撬棍一样，科学也很少使用 蛮力。——Edward Lytton
认真做事常常是浪费时间。——Robert Byrne
蛮力法是一种简单直接地解决问题的方法，
冒泡排序
6
顺序查找
7
蛮力字符串匹配
8
蛮力字符串匹配
Θ(n+m)=Θ(n)
9
最近对问题
10
凸包问题
定义 对于平面上的一个点集合（有限或无限），如果以 集合中任意两点P和Q为端点的线段都属于这个集合，则
这个集合是凸的。
定义 一个点集合S的凸包是包含S的最小凸集合。
11
凸包问题
定理 任意包含n>2个点（不共线）的集合S的凸包是以S 中的某些点为顶点的凸多边形。
很明显，这个和对某一阶幻方是一
个定值。设此值为SN ，则不难解
出：SN = N 2 ·(N 2 +1)/2N= N ·(N 2 +1) /2。
492 357 816
wk.baidu.com 外延法(由巴谢提出)构造奇阶幻方
H·Coxeter构造幻方的方法
首先在正方形最上面一 行的正中间的小方格内 填写1，然后到它的左 上方的小格内填写下一 个数(注意：我们认为正 方形的同一行或同一行 的头尾是相连的)。如果 走到某个小方格，而该 格已填了数，那末就改 走到原方格的下面一个 方格。
