算法第五章幻灯片.ppt

《算法第五章幻灯片.ppt》由会员分享，可在线阅读，更多相关《算法第五章幻灯片.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法第五章课件第1页，共91页，编辑于2022年，星期一什么是减治法什么是减治法n减治技术利用了一种关系：一个问题给减治技术利用了一种关系：一个问题给定实例的解和同样问题较小实例的解之定实例的解和同样问题较小实例的解之间的关系。一旦建立了这样一种关系，间的关系。一旦建立了这样一种关系，我们既可以从顶至下（递归地），也可我们既可以从顶至下（递归地），也可以从底至上（非递归地）来运用这种关以从底至上（非递归地）来运用这种关系。系。第2页，共91页，编辑于2022年，星期一三种主要的类型三种主要的类型n减去一个常量减去一个常量n减去一个常量因子减去一个常量因子n减去的规模是可变的减去的规模是可变的第

2、3页，共91页，编辑于2022年，星期一1.减常量减常量n每次算法迭代时，总是从实例规模中减去一个规模相同的每次算法迭代时，总是从实例规模中减去一个规模相同的常量的值常量的值n见图见图 5.1 P119n例：计算例：计算an的值的值 f(n-1)*a if n1 f(n)=a if n=1n从顶至下从顶至下 递归（利用上面公式）递归（利用上面公式）从底至上从底至上 迭代（迭代（a自乘自乘n-1次）次）第4页，共91页，编辑于2022年，星期一2.减常因子减常因子n每次算法迭代时，总是从实例规模中减每次算法迭代时，总是从实例规模中减去一个相同的常量因子去一个相同的常量因子n见图见图 5.2 P1

3、20n例例 (an/2)2 如果如果n是正偶数是正偶数 an=(a(n-1)/2)2*a 如果如果n是大于是大于1的奇数的奇数 a 如果如果 n=1第5页，共91页，编辑于2022年，星期一3.减可变规模减可变规模n每次算法迭代时，规模减小的模式是不每次算法迭代时，规模减小的模式是不同的同的n例例 欧几里得算法欧几里得算法 基于以下公式：基于以下公式：gcd(m,n)=gcd(n,m mod n)第6页，共91页，编辑于2022年，星期一5.1 插入排序插入排序n插入排序插入排序n思路：假设思路：假设n-1个数排序的问题已经解决，个数排序的问题已经解决，我们只需将第我们只需将第n个数插入到合适

4、的位置即个数插入到合适的位置即可可n关键：查找合适的位置关键：查找合适的位置第7页，共91页，编辑于2022年，星期一迭代过程迭代过程nA0Aj v do Aj+1 Aj j j-1 Aj+1 v第9页，共91页，编辑于2022年，星期一例n 89|45 68 90 29 34 17 45 89|68 90 29 34 17 45 68 89|90 29 34 17 45 68 89 90|29 34 17 29 45 68 89 90|34 17 29 34 45 68 89 90|17 17 29 34 45 68 89 90 第10页，共91页，编辑于2022年，星期一算法效率分析算法效

5、率分析n算法的基本操作是键值比较：算法的基本操作是键值比较：Ajvn比较次数取决于特定的输入比较次数取决于特定的输入nCworst(n)=(n-1)n/2 (n2)(一个严格递减的数组一个严格递减的数组)nCbest(n)=n-1 (n)(一个按照升序排列的数组一个按照升序排列的数组)nCavg(n)n2/4 (n2)第11页，共91页，编辑于2022年，星期一5.2 深度优先查找和广度优先查找深度优先查找和广度优先查找第12页，共91页，编辑于2022年，星期一 许多图的算法要求用一种系统的方式来对图的顶点许多图的算法要求用一种系统的方式来对图的顶点和边进行处理和边进行处理.有两种主要的算法

6、可以进行这种遍有两种主要的算法可以进行这种遍历历:(1)深度优先查找深度优先查找(DFS)(2)广度优先查找广度优先查找(BFS).图问题的一些重要算法图问题的一些重要算法,可以看作是减一技术的具体可以看作是减一技术的具体应用应用.第13页，共91页，编辑于2022年，星期一1.深度优先查找深度优先查找n基本思想基本思想：首先访问指定的起始顶点首先访问指定的起始顶点vi,然后在与然后在与vi邻接的未邻接的未被访问过的顶点中任意选择一个（比如被访问过的顶点中任意选择一个（比如vj)进行访问，进行访问，再在与再在与vj邻接的未被访问过的顶点中任意选择一个邻接的未被访问过的顶点中任意选择一个访问。如

7、此继续，若到达某顶点不存在未被访问过访问。如此继续，若到达某顶点不存在未被访问过的邻接顶点时（即成为死端），则退回到最近被访的邻接顶点时（即成为死端），则退回到最近被访问过的那个顶点；若它还有未被访问过的邻接顶点，问过的那个顶点；若它还有未被访问过的邻接顶点，则选择一个进行访问。重复上述访问过程，直至全则选择一个进行访问。重复上述访问过程，直至全部顶点都被访问为止。部顶点都被访问为止。第14页，共91页，编辑于2022年，星期一使用栈 在第一次访问一个顶点的时候，我在第一次访问一个顶点的时候，我们把该顶点入栈；当她成为一个死端的们把该顶点入栈；当她成为一个死端的时候，我们把它出栈。时候，我们把

8、它出栈。第15页，共91页，编辑于2022年，星期一n深度优先查找森林深度优先查找森林n树向边树向边 从某个顶点出发，遇到一个与它相邻的未访问的顶从某个顶点出发，遇到一个与它相邻的未访问的顶点，连接这样两个顶点的边称为点，连接这样两个顶点的边称为树向边树向边。n回边回边 遍历过程遇到一条指向已访问顶点的边，并且这个顶遍历过程遇到一条指向已访问顶点的边，并且这个顶点不是它的直接前趋（即它在树中的父母），这种边称点不是它的直接前趋（即它在树中的父母），这种边称为回边。为回边。第16页，共91页，编辑于2022年，星期一图5.5DFS遍历 P126fgcadbeijh第17页，共91页，编辑于202

9、2年，星期一算法效率分析算法效率分析n邻接矩阵邻接矩阵 (|V|2)n邻接链表邻接链表(|V|+|E|)第18页，共91页，编辑于2022年，星期一DFS重要应用nDFS生成的两种顶点序列生成的两种顶点序列:第一次访问顶点的次序第一次访问顶点的次序(入栈入栈)和顶点成为死端的次序和顶点成为死端的次序(出栈出栈).n检查图的连通性和无环性检查图的连通性和无环性 （1）从任意节点开始）从任意节点开始DFS遍历，在该算法停下来以后，检查一下是否所有的顶遍历，在该算法停下来以后，检查一下是否所有的顶点都被访问过了。若都被访问过了，则这个图是连通的，否则图是不连通的。点都被访问过了。若都被访问过了，则这

10、个图是连通的，否则图是不连通的。（2）若）若DFS森林不包含回边，则这个图是无环的，否则图是有环的。森林不包含回边，则这个图是无环的，否则图是有环的。n求图的关节点求图的关节点n如果从图中移走一个顶点和所有它附带的边之后如果从图中移走一个顶点和所有它附带的边之后,图被分为若干个不相图被分为若干个不相交的部分交的部分,我们说这样的顶点是图的我们说这样的顶点是图的关节点关节点第19页，共91页，编辑于2022年，星期一2.广度优先查找广度优先查找n基本思想是：首先访问指定的起始顶点基本思想是：首先访问指定的起始顶点vi，然后依然后依次访问与次访问与vi邻接的所有顶点邻接的所有顶点vj,vj2,vj

11、p,再依次分再依次分别访问与别访问与 vj,vj2,vjp相邻接的所有未被访问过的相邻接的所有未被访问过的顶点。重复这一过程，直到所有顶点均被访问为止。顶点。重复这一过程，直到所有顶点均被访问为止。第20页，共91页，编辑于2022年，星期一使用队 该队列先从遍历的初始顶点开始该队列先从遍历的初始顶点开始,将将该顶点标识为已访问该顶点标识为已访问.在每次迭代的时候在每次迭代的时候,该算法找出所有和队头顶点邻接的未访该算法找出所有和队头顶点邻接的未访问顶点问顶点,把它们标记为已访问把它们标记为已访问,再把它们入再把它们入队队,然后然后,将队头顶点从队列中移去将队头顶点从队列中移去.第21页，共9

12、1页，编辑于2022年，星期一n广度优先查找森林广度优先查找森林n树向边树向边 连接未访问顶点的边连接未访问顶点的边n交叉边交叉边 连接已访问顶点的边连接已访问顶点的边第22页，共91页，编辑于2022年，星期一图5.6BFS遍历 P128fgcadbeijh第23页，共91页，编辑于2022年，星期一算法效率分析算法效率分析n邻接矩阵邻接矩阵 (|V|2)n邻接链表邻接链表(|V|+|E|)第24页，共91页，编辑于2022年，星期一BFS的应用的应用n(1)检查图的连通性和无环性检查图的连通性和无环性n做法本质上和做法本质上和DFS是一样的是一样的n(2)求两个给定顶点间边的数量最少的路求

13、两个给定顶点间边的数量最少的路径径.n从两个给定的顶点中的一个开始从两个给定的顶点中的一个开始BFS遍历遍历,一一旦访问到了另一个顶点就结束旦访问到了另一个顶点就结束.从从BFS树的根树的根到第二个顶点间的最简单路径就是我们所求到第二个顶点间的最简单路径就是我们所求的路径的路径.第25页，共91页，编辑于2022年，星期一例:求图5.7中a,g之间的最少边路径fabcghedaefbcgd第26页，共91页，编辑于2022年，星期一3.DFS 和 BFS主要性质DFSBFS数据结构栈队列顶点顺序的种类两种顺序一种顺序边的类型(无向图)树向边和回边树向边和交叉边应用连通性、无环性、关节点连通性、

14、无环性、最少边路径邻接矩阵的效率(|V|2)(|V|2)邻接链表的效率(|V|+|E|)(|V|+|E|)第27页，共91页，编辑于2022年，星期一5.3 拓扑排序拓扑排序第28页，共91页，编辑于2022年，星期一1.有向图有向图n一个对所有的边都指定方向的图一个对所有的边都指定方向的图.第29页，共91页，编辑于2022年，星期一两种有向图的表示方法两种有向图的表示方法 (1)邻接矩阵 0 1 1 0 0 1 0 1 0 0 A=0 0 0 0 0 0 0 1 0 1 (2)邻接表 cabdeabcdebccaec第30页，共91页，编辑于2022年，星期一2.有向图的遍历有向图的遍历n

15、 对于有向图来说,DFS和BFS是主要的遍历算法,但相应森林的结构可能会更复杂.其可能具有的全部类型的边：（1）树向边：连接未访问顶点的边（2）回边：从顶点到祖先的边（3）前向边：从顶点到树中非子女子孙的边 （4）交叉边：不属于前三种的边第31页，共91页，编辑于2022年，星期一例:n树向边：树向边：ab,bc,den回边：回边：ban前向边：前向边：acn交叉边：交叉边：dcabdecacbed第32页，共91页，编辑于2022年，星期一3.无环有向图无环有向图n有向回路有向回路:DFS森林的一条回边的存在意森林的一条回边的存在意味着该有向图具有一个有向的回路味着该有向图具有一个有向的回路

16、.n无环有向图无环有向图:如果一个有向图的如果一个有向图的DFS森林森林没有回边没有回边,该有向图是一个无环有向图该有向图是一个无环有向图.第33页，共91页，编辑于2022年，星期一4.例:课程安排n五门必修课五门必修课C1,C2,C3,C4,C5其中其中,C1和和C2没有任何先决条件没有任何先决条件 修完修完C1和和C2才能修才能修C3 修完修完C3才能修才能修C4 修完修完C3和和C4才能修才能修C5应按照什么顺序来学习这五门课程应按照什么顺序来学习这五门课程.第34页，共91页，编辑于2022年，星期一n该问题可以用图来建模该问题可以用图来建模n该问题转换成为该问题转换成为拓扑排序拓扑

17、排序:按照次序列出有向图的按照次序列出有向图的顶点顶点,使得对于图中每一条边来说使得对于图中每一条边来说,边的起始顶点总是边的起始顶点总是排在边的结束顶点之前排在边的结束顶点之前.C1C2C3C5C4第35页，共91页，编辑于2022年，星期一n注注:要让拓扑排序有解要让拓扑排序有解,问题中的图必须是问题中的图必须是一个无环有向图一个无环有向图.第36页，共91页，编辑于2022年，星期一5.两种算法两种算法n(1)深度优先查找的一个简单应用深度优先查找的一个简单应用 n(2)基于减治技术的一个直接实现基于减治技术的一个直接实现第37页，共91页，编辑于2022年，星期一(1)深度优先查找的一

18、个简单应用深度优先查找的一个简单应用n执行一次执行一次DFS,并记住顶点变成死端并记住顶点变成死端(即退即退出遍历栈出遍历栈)的顺序的顺序.将该次序反过来就得到将该次序反过来就得到了拓扑排序的一个解了拓扑排序的一个解.n例见图例见图5.10 C5 1 出栈次序 C4 2 C5,C4,C3,C1,C2 C3 3 拓扑排序表 C1 4 C2 5 C2,C1,C3,C4,C5 C1C2C3C5C4第38页，共91页，编辑于2022年，星期一(2)基于减治技术的一个直接实现基于减治技术的一个直接实现n不断地做这样一件事不断地做这样一件事,在余下的有向图中求出一个在余下的有向图中求出一个源源,它是一个没

19、有输入边的顶点它是一个没有输入边的顶点,然后把它和所有从它然后把它和所有从它出发的边都删除出发的边都删除.(如果有多个这样的源如果有多个这样的源,可任意选择可任意选择一个一个.如果这样的源点不存在如果这样的源点不存在,算法停止算法停止.)顶点被删除顶点被删除的次序就是拓扑排序问题的一个解的次序就是拓扑排序问题的一个解.n例：见图例：见图5.11 P133n注意注意：拓扑排序问题可能会有若干个不同的可选解：拓扑排序问题可能会有若干个不同的可选解第39页，共91页，编辑于2022年，星期一5.4 生成组合对象的算法生成组合对象的算法第40页，共91页，编辑于2022年，星期一1.生成排列生成排列n

20、问题描述问题描述 假设需要对元素进行排列的集合是从假设需要对元素进行排列的集合是从1到到n的简单整的简单整数集合，使其更一般性，可以把其解释为数集合，使其更一般性，可以把其解释为n个元素集合个元素集合a1,an中元素的下标，求所有的排中元素的下标，求所有的排列。列。第41页，共91页，编辑于2022年，星期一三种主要的方法三种主要的方法n最小变化算法（利用减一技术）nJohnson-Trotter算法（n值较小时）n按字典序排列算法第42页，共91页，编辑于2022年，星期一（1）最小变化算法n思路：假设已经解决了规模为思路：假设已经解决了规模为n-1的排列，共有的排列，共有(n-1)!个排列

21、，我们只需把个排列，我们只需把n插入到插入到n-1个元素的每一种个元素的每一种排列中的排列中的n个可能位置，即可解决问题，共个可能位置，即可解决问题，共n(n-1)!=n!个排列。个排列。n把把n插入的方法：一开始从右到左把插入的方法：一开始从右到左把n插入到插入到12(n-1）的位置中，然后每处理一个）的位置中，然后每处理一个新排列时，再调换方向。新排列时，再调换方向。n见图见图5.12第43页，共91页，编辑于2022年，星期一（2）Johnson-Trotter算法n思路：我们给一个排列中的每个元素思路：我们给一个排列中的每个元素k赋予一个方赋予一个方向，若元素向，若元素k的箭头指向一个

22、相邻的较小元素，则的箭头指向一个相邻的较小元素，则k在这个以箭头标记的排列中是在这个以箭头标记的排列中是移动的移动的。n算法和例题见书算法和例题见书P135第44页，共91页，编辑于2022年，星期一（3）字典序）字典序n思路：从右到左扫描一个当前的排列，寻找第一对思路：从右到左扫描一个当前的排列，寻找第一对连续的元素连续的元素ai和和ai+1，并且，并且aian)，然后在尾部寻找大于，然后在尾部寻找大于ai的最的最小的数字，并将其放在位置小的数字，并将其放在位置i上；最后将上；最后将ai和尾部剩下的元素按升序填充到和尾部剩下的元素按升序填充到i+1到到n的位置上即可。的位置上即可。n计算计算

23、163542按字典序后面的数按字典序后面的数第45页，共91页，编辑于2022年，星期一2.生成子集生成子集n问题描述个子集问题描述个子集 生成一个抽象集合生成一个抽象集合A=a1,an的所有的所有2n个个子集子集第46页，共91页，编辑于2022年，星期一减一思想减一思想n思路：假设已经得到了思路：假设已经得到了a1,an-1的所有的所有的子集；可将的子集；可将a1,an的所有子集分的所有子集分为两组：不包含为两组：不包含an的子集（已得到）和的子集（已得到）和包含包含an的子集，只需将的子集，只需将an添加到添加到a1,an-1的所有子集中。的所有子集中。n见图见图5.13第47页，共91

24、页，编辑于2022年，星期一对较小集合生成子集对较小集合生成子集n简便方法简便方法 利用利用n个元素集合个元素集合a1,an的所有的所有2n个子集个子集和长度为和长度为n的所有的所有2n个比特串之间一一对应关系个比特串之间一一对应关系n思路：思路：若若ai属于该子集，记为属于该子集，记为1，若不属于，记为，若不属于，记为0n见书上例题见书上例题 n=3时时 第48页，共91页，编辑于2022年，星期一n存在一种生成比特串的最小变化，使得每一个比特串存在一种生成比特串的最小变化，使得每一个比特串和它的直接前趋之间仅仅相差一个比特位。对子集来和它的直接前趋之间仅仅相差一个比特位。对子集来讲，要么增

25、加一个元素，要么删除一个元素，但两者讲，要么增加一个元素，要么删除一个元素，但两者不能同时发生。不能同时发生。n例：例：n=3 000 001 011 010 110 111 101 100 这是这是二进制反射格雷码二进制反射格雷码的一个例子的一个例子 第49页，共91页，编辑于2022年，星期一5.5 减常因子算法减常因子算法第50页，共91页，编辑于2022年，星期一1.假币问题假币问题n问题描述问题描述 在在n枚外观相同的硬币中枚外观相同的硬币中,有一枚是假币有一枚是假币,假设假设已知假币比真币轻已知假币比真币轻,并有一架天平并有一架天平,设计一个高效设计一个高效的算法来检测出这枚假币的

26、算法来检测出这枚假币.第51页，共91页，编辑于2022年，星期一减常因子算法减常因子算法n思路：把n枚硬币分成两堆，每堆有n/2枚硬币，若n为奇数，就留下一枚额外的硬币，然后把两堆硬币放在天平上。若两堆重量相同，则留下的硬币为假币；否则我们可以用同样的方式对较轻的一堆硬币进行处理，这堆硬币中一定包含那枚假币。第52页，共91页，编辑于2022年，星期一算法效率分析算法效率分析n该算法在最坏情况下所需要的称重次数W(n)的递推关系式：W(n)=w(n/2 )+1 for n1,w(1)=0 W(n)=log2n (logn)第53页，共91页，编辑于2022年，星期一思考思考n有没有更高效的算

27、法有没有更高效的算法n如果把硬币分成三堆呢如果把硬币分成三堆呢?n做习题做习题5.5 3第54页，共91页，编辑于2022年，星期一n如果如果n=3k,则将硬币分为三等分则将硬币分为三等分n如果如果n=3k+1(即即n mod 3=1),则将硬则将硬币分为币分为k,k,k+1或者或者k+1,k+1,k-1三份三份n如果如果n=3k+2(即即n mod 3=2),则将硬则将硬币分为币分为k,k,K+2 或者或者k+1,k+1,k 三份三份第55页，共91页，编辑于2022年，星期一If n=1 硬币为假币硬币为假币Else 将硬币分为三份将硬币分为三份 n/3,n/3,n-2*n/3,并称前两份

28、并称前两份 if 重量相等重量相等,就继续处理第三份就继续处理第三份 else 继续处理轻的那份继续处理轻的那份第56页，共91页，编辑于2022年，星期一B.W(n)=w(n/3 )+1 for n1,w(1)=0.W(n)=log3n (logn)C.log2n/log3n=log2n/log32log2n=log231.6第57页，共91页，编辑于2022年，星期一思考n是不是分的堆数越多越好是不是分的堆数越多越好?第58页，共91页，编辑于2022年，星期一2.俄式乘法俄式乘法(俄国农夫法俄国农夫法)n问题描述问题描述n两个正整数相乘的非主流算法两个正整数相乘的非主流算法n较大实例的解

29、和较小实例的解较大实例的解和较小实例的解(以以n的值作为的值作为实例规模的度量实例规模的度量)N*m=n/2*2m n是偶数是偶数 N*m=(n-1)/2*2m+m n是奇数是奇数 第59页，共91页，编辑于2022年，星期一n实例 n m 50 65 25 130 12 260 (+130)6 520 3 1040 1 2080(+1040)2080+(130+1040)=3250 第60页，共91页，编辑于2022年，星期一算法特性算法特性n该算法只包括折半、加倍和相加这几个该算法只包括折半、加倍和相加这几个简单的操作简单的操作n算法使得硬件实现的速度非常快，因为算法使得硬件实现的速度非常

30、快，因为使用移位就可以完成二进制数的折半和使用移位就可以完成二进制数的折半和加倍。加倍。第61页，共91页，编辑于2022年，星期一3.约瑟夫斯问题约瑟夫斯问题n问题描述问题描述n约瑟夫斯参加了并记录了公元约瑟夫斯参加了并记录了公元6670年犹太人反抗罗马的年犹太人反抗罗马的起义。约瑟夫斯作为一个将军，设法守住了裘达伯特的起义。约瑟夫斯作为一个将军，设法守住了裘达伯特的堡垒达堡垒达47天之久，但在城市陷落了以后，他和天之久，但在城市陷落了以后，他和40名死硬名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说决说“宁死不投降宁死不投降”

31、。于是，约瑟夫建议每个人应该轮流。于是，约瑟夫建议每个人应该轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签预谋地抓到了最后一签,并且作为洞穴中的两个幸存者之并且作为洞穴中的两个幸存者之一一,他说服了他原先的牺牲品一起投降罗马他说服了他原先的牺牲品一起投降罗马.第62页，共91页，编辑于2022年，星期一实例n先让n个人围成一圈，并将他们从1到n编号，从编号为一的那个人那里开始这个残酷的计数，每次消去第二个人直到只留下一个幸存者,算出幸运者的号码J(n).12 11 61 21 7 21 5 32 61 32 41 5

32、2 41 n=6时 n=7时第63页，共91页，编辑于2022年，星期一算法n为了得到新的位置编号相对应的初始位为了得到新的位置编号相对应的初始位置编号置编号.nJ(2k)=2J(k)-1nJ(2k+1)=2J(k)+1nJ(1)=1n练习练习 J(40)第64页，共91页，编辑于2022年，星期一nJ(40)=2j(20)-1 =2(2j(10)-1)-1 =4j(10)-3 =4(2j(5)-1)-3 =8j(5)-7 =8(2j(2)+1)-7 =16j(2)+1 =16(2j(1)-1)+1 =32j(1)-15=32-15=17第65页，共91页，编辑于2022年，星期一思考n在在4

33、0名顽强的将士中，倒数第二个幸存名顽强的将士中，倒数第二个幸存者是几号者是几号?n 求求n个人中倒数第二个幸存者的号码。个人中倒数第二个幸存者的号码。第66页，共91页，编辑于2022年，星期一另一个算法另一个算法n将将n的二进制数做一次的二进制数做一次向左向左的循环移位来的循环移位来得到得到j(n)n例例:J(6)=J(1102)=1012=5 J(7)=J(1112)=1112=7 J(40)=J(1010002)=0100012=17第67页，共91页，编辑于2022年，星期一5.6 减可变规模算法减可变规模算法第68页，共91页，编辑于2022年，星期一例例n欧几里得算法欧几里得算法

34、gcd(m,n)=gcd(m,m mod n)gcd(31415,14142)=gcd(14142,3131)=gcd(3131,1618)=gcd(1618,1513)=gcd(1513,105)=gcd(105,43)=gcd(43,19)=gcd(19,5)=gcd(5,4)=gcd(4,1)=gcd(1,0)=1.第69页，共91页，编辑于2022年，星期一1.计算中值和选择问题计算中值和选择问题n选择问题选择问题 求一个n个数列表的第个数列表的第k个最小元素个最小元素.这个数字这个数字被称为被称为第第k个顺序统计量个顺序统计量.k=1 找最小元素找最小元素 k=n 找最大元素找最大元

35、素 k=n/2 找找中值中值,即该元素比列表中的一半即该元素比列表中的一半 元素大元素大,又比另一半元素小又比另一半元素小.第70页，共91页，编辑于2022年，星期一方法一n先把列表进行排序先把列表进行排序,然后从结果中选出第然后从结果中选出第k个元素个元素.n算法效率取决于所选用的排序算法的效算法效率取决于所选用的排序算法的效率率.第71页，共91页，编辑于2022年，星期一各种排序算法的效率 选择排序选择排序 冒泡排序冒泡排序 插入排序插入排序 合并排序合并排序 快速排序快速排序 最坏情况最坏情况 (n(n2 2)(n(n2 2)(n(n2 2)(nlogn)(nlogn)(n(n2 2

36、)平均情况平均情况 (n(n2 2)(n(n2 2)(n(n2 2)(nlogn)(nlogn)(nlogn)(nlogn)第72页，共91页，编辑于2022年，星期一方法二n ai1ais-1 p ais+1ain p pn值P是中轴,将数组分为两个子集 s是分区的分割位置 if s=k:中轴中轴P就是选择问题的解就是选择问题的解 if sk:到左边的分区中求解到左边的分区中求解 if sk:到右边的分区继续求解到右边的分区继续求解 第73页，共91页，编辑于2022年，星期一实例实例:找出下面数列中的中值找出下面数列中的中值(共共9个数个数,即求第即求第5小的元素小的元素)4 1 10 9

37、 7 12 8 2 15我们选择第一个元素作为中轴，我们选择第一个元素作为中轴，分区分区 2 1 4 9 7 12 8 10 15 因为因为s=3k=5,我们处理列表的左边部分我们处理列表的左边部分 8 7分区分区 7 8现在现在S=k=5,算法停止算法停止,我们找到的中值是我们找到的中值是8第74页，共91页，编辑于2022年，星期一算法效率分析算法效率分析n平均情况（分割点总是位于剩下的数组的中间位置）平均情况（分割点总是位于剩下的数组的中间位置）C(n)=C(n/2)+n+1 根据主定理根据主定理C(n)(n)n最差情况最差情况,对于一个严格递增的数组对于一个严格递增的数组 Cworst

38、(n)=(n+1)+n+3=(n+1)(n+2)/2-3 (n2)C(n)(n2)例例:1 2 3 4 5 k=5第75页，共91页，编辑于2022年，星期一2.插值查找插值查找n考虑在电话号码簿上查找名字考虑在电话号码簿上查找名字 如如:查查Brown,Smith的电话号码的电话号码 n不同于折半查找总是把查找键和给定数不同于折半查找总是把查找键和给定数组的中间元素进行比较组的中间元素进行比较.n插值查找插值查找每一轮迭代用数组的哪个值与每一轮迭代用数组的哪个值与键值比较进行了进一步的考虑键值比较进行了进一步的考虑.第76页，共91页，编辑于2022年，星期一见图5.16 值 Ar v Al

39、 l x r 第77页，共91页，编辑于2022年，星期一nX=l+(v-Al)(r-l)/ar-alnIf v=Ax 算法结束 if vAx 在Ax+1.r中继续查找第78页，共91页，编辑于2022年，星期一插值查找算法效率分析插值查找算法效率分析n平均情况键值比较次数平均情况键值比较次数log2log2n+1 O(logn)n最差情况是线性的最差情况是线性的第79页，共91页，编辑于2022年，星期一折半查找和插值查找的比较折半查找折半查找Cw(n)=log2n+1(logn)Cavg(n)(logn)插值查找Cw(n)(n)Cavg(n)log2log2n+1 O(logn)对于较小的

40、文件对于较小的文件,折半查找很可能更好一些折半查找很可能更好一些,但对于更大但对于更大的文件和那些比较的开销非常大或者访问的成本非常高的文件和那些比较的开销非常大或者访问的成本非常高的应用的应用,插值查找更值得考虑插值查找更值得考虑.第80页，共91页，编辑于2022年，星期一3.二叉查找树的查找和插入二叉查找树的查找和插入 二叉查找树：二叉查找树：一种节点包含可排序项集一种节点包含可排序项集合中元素的二叉树合中元素的二叉树,每个节点一个元素每个节点一个元素,并并使得对于每个节点来说使得对于每个节点来说,所有左子树的元所有左子树的元素都小于子树根节点的元素素都小于子树根节点的元素,所有右子树所

41、有右子树的元素都大于子树根节点的元素的元素都大于子树根节点的元素.第81页，共91页，编辑于2022年，星期一二叉查找树的查找二叉查找树的查找n要求找一个给定值要求找一个给定值v的元素的元素n递归做法：递归做法：若树为空，则查找失败若树为空，则查找失败 若树不为空，把若树不为空，把v和该树的根和该树的根K进行比较进行比较 当当v=K时，查找成功，停止时，查找成功，停止 当当vK时，在右子树中继续查找时，在右子树中继续查找第82页，共91页，编辑于2022年，星期一n二叉查找树的规模的最佳量度就是树的二叉查找树的规模的最佳量度就是树的高度高度.n在二叉树的查找中在二叉树的查找中,从一次迭代到另一

42、次从一次迭代到另一次迭代迭代,树的高度的减少通常都不相同树的高度的减少通常都不相同,即减即减可变规模可变规模.第83页，共91页，编辑于2022年，星期一算法效率分析算法效率分析n最坏情况属于最坏情况属于 (n)n平均情况属于平均情况属于 (logn)第84页，共91页，编辑于2022年，星期一二叉查找树的插入二叉查找树的插入n把新的键插入到二叉查找树的操作基本把新的键插入到二叉查找树的操作基本上和查找到那个地方是相同的上和查找到那个地方是相同的n二叉查找树的插入操作和查找操作的效二叉查找树的插入操作和查找操作的效率特性也是相同的率特性也是相同的第85页，共91页，编辑于2022年，星期一拈游

43、戏拈游戏n单堆棋子版本单堆棋子版本n I 堆棋子版本堆棋子版本第86页，共91页，编辑于2022年，星期一单堆棋子版本单堆棋子版本n问题描述问题描述 现有一堆现有一堆n个棋子，两个玩家轮流从堆中个棋子，两个玩家轮流从堆中拿走最少拿走最少1个，最多个，最多m个棋子，且每次拿个棋子，且每次拿走的棋子数目可以不同，拿到最后的一走的棋子数目可以不同，拿到最后的一个棋子的玩家胜利。问先走还是后走，个棋子的玩家胜利。问先走还是后走，怎么走？怎么走？第87页，共91页，编辑于2022年，星期一结论结论n当当n是是m+1的倍数时，的倍数时，n个棋子的实例是一个棋子的实例是一个个败局败局。n当当n不是不是m+1

44、的倍数时，的倍数时，n个棋子的实例是个棋子的实例是一个一个胜局胜局。n胜利策略：每次拿走胜利策略：每次拿走n mod(m+1)个棋子个棋子第88页，共91页，编辑于2022年，星期一I 堆棋子版本堆棋子版本n问题描述问题描述 有有I 堆棋子，每堆棋子数分别是堆棋子，每堆棋子数分别是n1,n2,nI,每次走的时候，玩家可以从任意一每次走的时候，玩家可以从任意一堆中拿走任意堆中拿走任意允许允许数量的棋子，甚至可数量的棋子，甚至可以把一堆都拿光，拿到最后的一个棋子以把一堆都拿光，拿到最后的一个棋子的玩家胜利。问先走还是后走，怎么走的玩家胜利。问先走还是后走，怎么走？第89页，共91页，编辑于2022

45、年，星期一n思考：思考：对对I=2时，时，n1=n2和和n1n2的实例情况是的实例情况是否相同？若相同，给出谁能赢，如何赢；否相同？若相同，给出谁能赢，如何赢；若不同，考虑每种情况谁能赢，如何赢若不同，考虑每种情况谁能赢，如何赢？第90页，共91页，编辑于2022年，星期一I 堆棋子版本的解堆棋子版本的解nI 堆棋子版本的解基于堆中棋子数的二进堆棋子版本的解基于堆中棋子数的二进制表示；我们只需计算每堆棋子数的制表示；我们只需计算每堆棋子数的二二进制数位和进制数位和:对每一位分别求和并忽略进对每一位分别求和并忽略进位。位。n结论：当且仅当二进制数位和中包含至结论：当且仅当二进制数位和中包含至少一个少一个1时，为时，为胜局胜局；当且仅当二进制数；当且仅当二进制数位和只包含位和只包含0时，为时，为败局败局。n例题见课本例题见课本第91页，共91页，编辑于2022年，星期一