2020/4/28
成都学院计算机系
-6-
（1）集合的遍历 按照元素序号的顺序依次处理每个元素。 （2）线性表的遍历 元素序号，如数组是按元素的下标来处理。 （3）树的遍历 先序、中序、后序
2020/4/28
成都学院计算机系
-7-
三、采用穷举法的原因
理论上可以解决可计算领域的各种问题。 经常用来解决一些较小规模的问题。 对一些重要问题（排序、查找、字符串匹配等） 有一些实用价值，且不受问题规模的限制。 可作为某类问题时间性能下限，进行高效算法的 比较。
第4章 穷举法
4.1 穷举法的设计思想 4.2 渐近表示法 4.3 算法分析
2020/4/28
成都学院计算机系
-2-
主要知识点
掌握好算法的评价标准; 了解影响程序运行时间的因素; 掌握算法的评价标准:时间复杂度和空间复杂度 的概念; 掌握渐近时间复杂度的几种表示方式; 掌握常见时间复杂度渐近表示之间的关系.
{ index=i; for ( j=i+1;j<=n;j++)//找最小记录 if (r[j]<r[index]) index=j; if (index!=i) r[j]>r[index]; }
}
2020/4/28
成都学院计算机系
-16-
基本语句 内层循环中的r[j]<r[index]，其执 行次数为：
2020/4/28
成都学院计算机系
-18-
Void Bubblesort(int r[],int n) { for (i=1;i<=n-1;i++)
for ( j=1;j<=n-i;j++)//找最小记录 if (r[j]<r[j+1]) r[j]>r[j+1];
}
2020/4/28
成都学院计算机系
2020/4/28
成都学院计算机系
-3-
4.1 穷举法思想
一、穷举法定义
是一种简单而直接地解决问题的方法，常常 直接基于问题的描述。
是最容易应用的方法，其时间性能比较低。 通常典型的指数时间算法一般都是通过穷举 法搜索而得到的。
2020/4/28
成都学院计算机系
-5-
二、设计思想
采用的基本技术是扫描技术，即使用一定的策 略将待求解问题的所有元素依次处理一次，从 而找到问题的解。 为了避免重复试探，在基本的数据结构中采用 遍历来处理每一个元素。
2020/4/28
成都学院计算机系
-12-
其基本语句 i>0和r[i]!=k，其执行次数
n
i 1
pici
1 n
n i 1
(n i 1)
n 1 2
O(n)
比较顺序查找方法，减少了系数。
2020/4/28
成都学院计算机系
-13-
4.3 排序问题中的穷举法
一、选择排序 思想：开始扫描整个序列，找到最小记录和序 列中的第一个记录交换，再从第二个记录扫描， 找到最小记录与第二个记录交换，直到扫描第 n-1个记录与第n个记录进行交换，使得整个序 列有序。
2020/4/28
成都学院计算机系
-14-
一般情况，第i趟排序从第i个记录开始扫描序 列，在n-i+1(1≤i≤n)个记录中找最小记录， 并与第i个记录进行交换。
2020/4/28
成都学院计算机系
-15-
Void Selectsort(int r[],int n) { for (i=1;i<=n-1;i++)
2020/4/28
成都学院计算机系
-8-
4.2 查找问题中的穷举法
顺序查找 思想：从表的一端向另一端逐个将元素与给定 值进行比较，若相等，查找成功，给出该元素 的具体位置；若整个表检测完仍未找到与给定 值相等的元素，则查找失败！
2020/4/28
成都学院计算机系
-9-
假设以n个数放入数组r[1]～r[n]中，查找值k 的算法。 int Seqsearch(int r[], int n, int k) { i=n;
n1
n
1
n 1
(n i)
n(n 1)
O(n2)
i1 j i1 i1
2
选择排序最多交换n-1次数据。
2020/4/28
成都学院计算机系
-17-
二、冒泡排序 一开始就扫描整个序列，在扫描的过程中两两 比较相邻记录，如反序则交换，最终将最大记 录置于最后一个记录位置，第二大记录置于倒 数第二个记录位置，重复至整个序列有序。
最近对问题的求解过程：分别计算每一对点 之间的距离，然后找出距离最小的那一对，只 考虑i<j的那些点对。
2020/4/28
成都学院计算机系
-22-
int closetpoint(int n,int x[],int y[],int &index1,int &index2) { mindist=+∞; for (i=1;i<n;i++) for (j=i+1;j<=n;j++) { d=(x[i]-x[j])*(x[i]-x[j])+ (y[i]-y[j])*(y[i]-y[j]);
4.5 几何问题中的穷举法
最近对问题 要求找出一个包含n个点的集合中距离最近
的两个点。 应用实例：空中交通
2020/4/28
成都学院计算机系
-21-
前提假设 1.二维空间中的点，并且点的坐标形式(x,y)给 出的。 2.若Pi=(xi,yi),Pj=(xj,yj)，则其间距离d:
d (xi x j )2 ( yi y j )2
-19-
基本语句 内层循环中的r[j]<r[j+1]，其执行次 数为：
n1 ni 1 n1 (n i) n(n 1) O(n2 )
i1 j1
i 1
2
不足：如果整个序列已经有序，还是要直接整个 外循环执行完。 思想有没有改进的办法？有则写出算法。
2020/4/28
成都学院计算机系
-20-
while (i>0 &&r8
成都学院计算机系
-10-
其基本语句 i>0和r[i]!=k，其执行次数
n
i 1
pibi
n i 1
pici
1 n
n i 1
(n i 1)
1 n
n i1
(n i 1)
n 1 O(n)
缺陷：每次都要判断下标i是否越界。
2020/4/28
成都学院计算机系
-11-
改进方法：哨兵
将k放入到r[0]中，每次将r[1]～r[n]中的值与 r[0]进行比较。
int Seqsearch(int r[], int n, int k) { i=n; r[0]=k; while (r[i]!=k) i--; return i; }