算法课件-第5章-减治法

第5章减治法主要内容：

5.1插入排序

5.2深度优先查找与广度优先查找

5.3拓扑排序

5.4生成组合对象的算法

5.5减常因子算法5.6减可变规模算法减治法的基本思想将规模为n的问题递减为规模为n-1或n/2的子问题,反复递减后对子问题分别求解,再建立子问题的解与原问题的解的关系。减治法有三个变形:减常数(如1):每次迭代规模减1，即n→n-1

减因子(如1/2):每次迭代规模减半，即n→n/2

减可变规模:每次迭代减小的规模不同减（一）治技术规模为n的问题规模为n-1的子问题子问题的解原始问题的解例如：f(n)=anf(n)=f(n-1)*an>1f(n)=an=14减（半）治技术规模为n的问题规模为n/2的子问题子问题的解原始问题的解an=(an/2)2n是偶数an=(a(n-1)/2)2*an是奇数an=an=15.1插入排序插入排序的过程类似玩牌时整理手中纸牌的过程。它的基本思想是：每步将一个待排序的对象按照其关键字的大小，插到前面已经排好序的序列中的适当位置，直到全部对象插入完毕为止。常用的插入排序有：直接插入排序、折半插入排序、链表插入排序和希尔排序（缩小增量排序），它们划分的依据是在排好序的序列中寻找插入位置所使用方法的不同。直接插入排序伪代码ALGORITHMInsertionSort(A[0..n-1])//对给定序列进行直接插入排序//输入：大小为n的无序序列A//输出：按非递减排列的序列Afori←1ton-1do temp←A[i] j←i-1 whilej≥0andA[j]>tempdo A[j+1]←A[j] j←j–1 A[j+1]←temp直接插入排序举例待排序序列{89,45,68,90,29,34,17}插入过程:{89}不需比较{45,89}{45,68,89}{45,68,89,90}{29,45,68,89,90}{29,34,45,6889,90}{17,29,34,45,68,89,90}

插入次数=n-1=6比较次数=?直接插入排序效率分析基本操作:比较比较次数C(n):

最坏的情形,每次插入需比较已插入的所有元素,此时,第i次插入比较i个元素,故思考题思考：当n=1时，问题的解如何？当n>1时，问题的解与n=1时有什么关系？运送一个士兵需要4次横渡，故总共需要4n次横渡。思考题参考5.4.2节生成子集5.2深度优先和广度优先查找1、深度优先查找可以从任何顶点开始访问图的顶点，每次迭代时，处理与当前顶点相邻的未访问顶点。用栈来跟踪深度优先查找的操作最方便。DFS的伪代码（1）PseudocodeforDepth-first-searchofgraphG=(V,E)：DFS(G)count:=0

未访问的顶点标记为0foreachvertexv∈Vdoifv的标记为0dfs(v)dfs(v)count:=count+1

顶点v

标记为countforeachvertexwadjacenttovdoifwismarkedwith0dfs(w)DFS的伪代码（2）ALGORITHMDFS(G)//对给定图使用深度优先搜索进行遍历;//输入：图的邻接表表示结点个数为N;//输出：各个结点输出顺序数组fori←0toN-1do VisitArray[i]←0//访问数组初始为0count←0fori←0toN-1do ifVisitArray[i]=0 dfs(V)//调用子函数dfs进行深度优先遍历dfs(V)//使用深度优先搜索对邻接表进行遍历//输入：结点V的邻接表;//输出：各个结点输出顺序数组count←count+1;VisitArray[V]←count//记录访问的次序tmp←V.linkwhiletmp≠Nulldo ifVisitArray[tmp.vertex]≠0dfs(tmp.vertex)深度优先举例abefcdgh一个DFS输出序列：

a-b-f-e-g-c-d-h深度优先搜索的效率与图的表示有关对邻接矩阵表示的图：遍历的效率为

Θ(V2)对邻接链表表示的图：遍历的效率为

Θ(V+E)2、广度优先查找可以从任何顶点开始访问图的顶点，每次迭代时，处理所有与当前顶点相邻的未访问顶点。用队列来跟踪广度优先查找的操作较方便。BFS的伪代码（1）BFS(G)count:=0标记每个顶点v=0foreachvertexv∈Vdobfs(v)bfs(v)count:=count+1标记v=count初始化顶点序列vwhile序列非空doa:=frontofqueueforeachvertexwadjacenttoadoifwismarkedwith0count:=count+1markwwithcountaddwtotheendofthequeueremoveafromthefrontofthequeueBFS的伪代码（2）ALGORITHMBFS(G)//输入：图的邻接表表示结点个数为N；//输出：各个结点输出顺序数组fori←0toN-1do VisitArray[i]←0 //访问数组初始为0count←0fori←0toN-1doifVisitArray[i]=0bfs(V)//调用子函数bfs进行广度优先遍历

ALGORITHMbfs(V)//使用广度优先搜索对邻接表进行遍历//输入：结点V的邻接表；//输出：各个结点输出顺序数组count←count+1;VisitArray[V]←count //记录访问的次序Queue.Enqueue(V) //把源结点加入到队列中whilenotQueue.Emptydo tmp←Queue.Dequeue//取队头结点扫描判断

whiletmp≠Nulldo ifVisitArray[tmp.vertex]=0 count←count+1 Queue.Enqueue(tmp)//把未访问的结点加入到

VisitArray[tmp.vertex]←count//记录访问次序

tmp←tmp.link //访问邻接表下一个结点BFS举例一个BFS的输出序列：

a-b-e-f-g-c-h-dabefcdghDFS与BFS的比较

DFSBFS数据结构临时栈(stack)队列(queue)边类型树与回边(backedges)树与交叉边(crossedges)邻接链表的效率邻接矩阵的效率应用判断是否有环判断是否连通求关节点(articulationpoints)判断是否有环判断是否连通求最短路径(minimum-edgepaths)Θ(V+E)Θ(V+E)Θ(V2)Θ(V2)5.3拓扑排序在大学学习的过程中，各门课程的学习是有先后顺序的，有些课程需要先修课程，有些则不需要；有些课程之间有先后的关系，有些课程则可以并行的进行。问题要求确定一个学习方案使得各门课程的学习能够有序进行。拓扑排序问题：对给定的无环有向图，要求按照某种顺序列出它的顶点序列，使图的每一条边的起点总在结束顶点之前。求拓扑序列的方法1方法1、应用DFS的出栈次序。DFS序列：

C1-C3-C4-C5--C2

出栈序列：

C5-C4-C3-C1-C2拓扑排序：

C2-C1-C3-C4-C5注：1、注意遍历到死端点时的出栈次序

2、拓扑排序不唯一C1C3C2C5C4求拓扑序列的方法1方法2、减治法，每次选择没有输入的点。容易得到一个拓扑序列：P-W-S-M-F-H-T即：微生物-小麦-羊-

-小虾-鱼-人-虎F鱼H人M小虾S羊W小麦P微生物T虎本节作业思考题：习题5.1-1,5.1-7,5.2-10,5.3-3,5.3-9作业：习题5.1-4，5.2-1，5.3-15.4生成组合对象的算法1、生成排列排列问题指的是对于给定的多个元素求其中各种可能的序列。为了简单起见，这里仅仅考虑1到n之间的整数的排列问题。下面介绍三种生成方法：（1）插入法（2）Johnson-Trotter法（3）字典顺序法插入法生列排列举例：求n=3的排列方法（自顶向下）：

在n=2的排列中插入3，在n=1的排列中插入2。自底向上生成排列的过程：在1中从右到左插入2得到12，21在12中从右到左插入3得到123，132，312在21中从右到左插入3得到213，231，321

于是得{123，132，312，213，231，321}Johnson-Trotter法生成排列其实有的算法并不需要知道规模n-1的排列就可以直接得到规模n的排列结果，Johnson-Trotter算法就是其中一种。利用这一算法求得的排列序列还是相邻序列变化最小的一个序列集合，也就是说下一个序列与上一个序列仅仅交换了两个元素的位置。J-T方法举例在排列的每一分量上画一个箭头。求最大的移动整数k，不断移动元素，直到没有元素可移动为止，掉转所有大于k的整数方向。移动元素：如果分量k的箭头指向一个相邻的较小元素，则该分量在排列中是移动的。例n=3,从123开始：字典顺序生成排列尽管Johnson-Trotter算法非常高效，但是似乎不是那么直观，不太符合人们的思维习惯。事实上比较自然的算法称为“字典排序（lexicographicorder）算法”，它是根据单词在字典中的排列顺序得到的算法。字典生成顺序举例例n=3在{1，2，3}中按字典顺序选择：

123

132

213

231

312

3212、生成子集集合A的“幂集”是指以集合A的所有子集为元素组成的集合。降低规模的减治法可以用来求幂集。

减治法的缺点也是在求解规模为n的问题时，需要得到规模为n-1的问题的解。这一过程是可以避免的，使用位串法求解集合幂集就是其中的一种解决方案。减治法生成幂集例n=3方法：在n=2的幂集中加入元素3，在n=1的幂集中加入元素2，在n=0的幂集中加入元素1

,{1}//n=1

,{1},{2},{1,2}//加入元素2,{1},{2},{1,2},{3},{1,3},{2,3},{1,2,3}//加入元素3位串法生成幂集例n=3,元素为{a1,a2,a3}方法：每一个子集与一个3位二进制串b1b2b3对应，ai属于该子集时，bi=1,否则bi=0二进制串：000,001,010,011,100,101,110,111对应子集：

,{a3},{a2},{a2,a3},{a1},{a1,a3},{a1,a2},{a1,a2,a3}我们可以产生从0到2n-1的二进制数来生成长度为n的所有二进制串5.5减常因子法1、假币问题

有n个金币，其中一个是假币。这个假币的重量比真币的重量要轻一点，所有n-1个金币的重量是一样的。现在你有一架天平，设计高效的算法（用最少的使用天平次数）找出那个假的金币。

假币问题解法1、用减治法（减半）

把n个硬币分为两堆，每堆n/2个，每次称两堆。易见W(1)=0

W(n)=W(n/2)+1

解得W(n)=log2n假币问题解法2、用减治法(减n/3）

把n个硬币分为三堆，每堆n/3个，每次称任意二堆。易见 W(1)=0 当n=1

W(n)=W(n/3)+1 当n>1

解得W(n)=O(log3n)，结果比减半法更好。假币问题实例：n=9用方法1（减半法）需要称3次。用方法2（减n/3法）需要称2次。

过程：

将9个金币分为3个组，每组3个金币。

将其中的两组放在天平的两边，如果有一边轻，说明假的金币就在这个组里。如果两边一样重，说明假的金币在第三个组里。

在有假币的组中，拿出两个金币，放在天平的两边，如果有一个轻，则这个轻的就是假币，如果两个一样重，则剩下的一个就是假币。2、俄式乘法/俄国农民法

设n、m是整数，以n为实例规模的度量。若n为偶数，则

n·m=(n/2)·2m若n为奇数，则

n·m=((n-1)/2)·2m+m以1·m=m为算法停止的条件。俄国农民法举例:50×65nm分析.506550×65=25×13025130+13025×130=12×260+1301226065203104012080=3250

3、约瑟夫斯问题约瑟夫斯是公元1世纪的犹太历史学家，他领导了反抗罗马人的武装起义，但是失败了。他和四十名犹太士兵被罗马人围困在一个山洞中。这四十个士兵宁死不屈，决定杀身成仁。但约瑟夫斯不想，但又不便公开反对，于是提出一个方法，就是四十一个人站成一个圈，从某人开始数起，凡数到三的人就让大家成全他升天，这样下去直到剩下最后一个人，这个人就自杀。大家都没有意见，于是约瑟夫斯就挑选了第31号的位置。结果所有人都死了，剩下他一个活下来投降了罗马人。这也是约瑟夫斯问题的最初提法。约瑟夫斯问题

约瑟夫斯问题的一般提法：设有n个以1、2、…、n编号的人，按编号顺序围成一圈，从1号开始报数，每数到m就淘汰一人，问最后被淘汰的人是几号呢？令L(n,m)为上述最后被淘汰的人的号码，则可以将最初的约瑟夫斯问题写成L(41,3)＝31。对于具体不同的n、m，求其计算公式。约瑟夫斯问题分析当m＝2时，公式是：L(n,2)＝2b＋1。

其中b是这样得出的，把n写成2a＋b，而a必须尽可能大。例如当n=100，则100可以写成25＋68，也可以写成26＋36，但是不能再写成27的了，所以，a=6，而b=36。

L(6,2)=2×2+1=5,//6=22+2,b=2L(7,2)=2×3+1=7,//7=22+3

,b=3

L(13,2)=2×5+1=11,//13=23+5,b=5约瑟夫斯问题分析当m＝3、4、…时，有没有公式呢？但存在一个L(n,m)递推公式：

L(1,m)＝1

L(k＋1,m)≡L(k,m)＋mmod

(n+1)减可变规模算法欧几里得算法计算中值和选择问题插值查找二叉查找树的查找和插入拈游戏计算中值和选择问题选择问题是求一个n个数列表的第k个最小元素的问题。这个数字被称为第k个顺序统计量

k＝1或者k＝n的情况，就是求列表的最小或最大元素时，要求找出这样一个元素，该元素比列表中的一半元素大，比另一半元素小，这个值被称为中值。计算中值和选择问题方法：

利用快速排序的分区方法，将数组分成两部分，分割点的下标为s，右边部分大于枢轴值p，左边部分小于枢轴值p。若s=k则结束；若s>k，则在左边继续找第k小的元素；若s<k，则在右边继续找第k-s小的元素；计算中值和选择问题例1找到下面9个数的中值：4，1，10，9，7，12，8，2，15，那么k=54 110 9 7 12 8 2 152 14 9 7 12 8 10 15S＝3<K＝5，所以处理右边部分

9 7 12 8 10 15 8 7 9 12 10 15S＝6>K＝5，所以处理左边部分

7 8中值＝8

插值查找插值查找用于查找有序数组不同于折半查找总是把查找键和给定有序数组的中间元素进行比较（每次规模消减一半）插入查找为了找到用来和查找键进行比较的数组元素，考虑了查找键的值精确地说，如果某次迭代处理的是数组位于最左边元素A[l]和最右边元素A[r]之间的一部分，该算法假设数组的值是线性递增的（该假设的精确度会影响算法的效率，但不会影响算法的正确性）插值查找值下标lxrA[l]vA[r]二叉查找树的查找和插入二叉查找树：每个节点一个元素，并使得对于每个节点来说，所有左子树的元素都小于子树根节点的元素，所有右子树的元素都大于子树根节点的元素。查找元素v：如果子树为空，查找失败如果不为空，则把v和该树的根K(r)比较相等就是找到了

v<K(r)则在左子树中查找

v>K(r)则在右子树中查找二叉查找树的查找和插入一棵查找树的规模的最佳度量就是树的高度最坏情况就是当这棵树是单支树时是Θ(n)平均效率为Θ(logn)，更精确来说，查找一棵由n个随机键构造起来的二叉查找树所需的键值比较次数大约是二叉搜索树算法：ALGORITHMBstSearch(R,k)//二叉搜索树上搜索算法的递归实现//输入：以R为根的二叉搜索树，待搜索值k//输出：搜索成功时，返回k在树中的位置，否则返回空值ifR=NullreturnNullelseifR.data>k returnBstSearch(R.leftChild,k)elseifA.data<k returnBstSearch(R.rightChild,k)ElsereturnRALGORITHMBstSearch2(R,k)//二叉搜索树上搜索算法的迭代实现//输入：以R为根的二叉搜索树，待搜索值k//输出：搜索成功时，返回k在树中的位置，否则返回空值tmp←Rwhiletmp≠Nulldo iftmp.data=kreturntmp elseiftmp.data>k tmp←tmp.leftChild else tmp←tmp.rightChildreturnNull拈游戏单堆棋子版本有一堆n

个棋子两个玩家轮流从堆中拿走最小1个