第5章 减治法

1、第五章第五章 减减 治治 法法1234减治法的设计思想减治法的设计思想排序问题中的减治法排序问题中的减治法组合问题中的减治法组合问题中的减治法5查找问题中的减治法查找问题中的减治法小结小结第五章第五章 减治法减治法变治法分两个阶段工作，即“变”阶段和“治”阶段.变治法的三种类型： 1)实例化简(instance simplification) 2)改变表现(representation change) 3)问题化简(problem reduction)problems instancesimpler instanceorAnother representationor another prob

2、lems instancesolution变变 治治 法法 概概 述述减治是基于变治的思想。减治是基于变治的思想。逻辑等价逻辑等价第五章第五章 减治法减治法子问题子问题的规模是的规模是n/2子问题的解子问题的解原问题的解原问题的解原问题原问题的规模是的规模是n（1） 原问题的原问题的解只存在于其中解只存在于其中一个较小规模的一个较小规模的子问题中子问题中;（2） 原问题的原问题的解与其中一个较解与其中一个较小规模的解之间小规模的解之间存在某种确定的存在某种确定的对应关系。对应关系。1 1 减治法的设计思想减治法的设计思想第五章第五章 减治法减治法对于给定的整数对于给定的整数a和非负整数和非负整

3、数n，计算，计算an的值的值应用减治技术得到如下计算方法：应用减治技术得到如下计算方法：且是奇数且是偶数1)(1)(122)1(22naananaannn1122naanaannn应用分治技术得到如下计算方法：应用分治技术得到如下计算方法：第五章第五章 减治法减治法应用分治法（例如二分法）得到的算法通常具有应用分治法（例如二分法）得到的算法通常具有如下递推式：如下递推式： 分治法和减治法区别分治法和减治法区别应用减治法（例如减半法）得到的算法通常具有应用减治法（例如减半法）得到的算法通常具有如下递推式：如下递推式： 111)2/(0)(nnnTnT足够小nnfnTngnT)()2/(2)()(

4、第五章第五章 减治法减治法2 2一个简单的例子一个简单的例子两个序列的中位数两个序列的中位数问题描述：一个长度为问题描述：一个长度为n（n1）的升序序列）的升序序列S，处在第，处在第n/2个位置的数称为序列个位置的数称为序列S的中位的中位数数 。两个序列的中位数是他们所有元素的升。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列序序列的中位数。现有两个等长升序序列A和和B，试设计一个在时间和空间两方面都尽，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。可能高效的算法，找出两个序列的中位数。第五章第五章 减治法减治法想法：想法：分别求出两个序列的中位

5、数，记为分别求出两个序列的中位数，记为a和和b；比；比较较a和和b，有下列三种情况：，有下列三种情况： a = b：则：则a即为两个序列的中位数；即为两个序列的中位数； a b：则中位数只能出现在：则中位数只能出现在b和和a之间，在序列之间，在序列A中舍弃中舍弃a之后的元素得到序列之后的元素得到序列A1，在序列，在序列B中舍弃中舍弃b之前的元素得到序列之前的元素得到序列B1；在在A1和和B1中分别求出中位数，重复上述过程，直中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。到两个序列中只有一个元素，则较小者即为所求。2 2一个简单的例子一个简单的例子两个序列的中位数

6、两个序列的中位数第五章第五章 减治法减治法对于两个给定的序列对于两个给定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B的中位数的过程。的中位数的过程。步步骤骤操作说明操作说明序列序列A序列序列B1初始序列初始序列11, 13, 15, 17, 192, 4, 10, 15, 202分别求中位数分别求中位数11, 13, 15, 17, 192, 4, 10, 15, 2031510，结果在，结果在10, 15之间之间舍弃舍弃15之后元素，之后元素，11,13,15舍弃舍弃10之前元素，之前元素，10,15,204分别求中位数分别求

7、中位数11,13,1510,15,2051315，结果在，结果在11, 15之间之间舍弃舍弃13之前元素，之前元素，13,15舍弃舍弃15之后元素，之后元素，10,156分别求中位数分别求中位数13,1510,1571013，结果在，结果在10, 13之间之间舍弃舍弃13之后元素，之后元素，13舍弃舍弃10之前元素，之前元素，158长度为长度为1，较小者为所求，较小者为所求13152 2一个简单的例子一个简单的例子两个序列的中位数两个序列的中位数第五章第五章 减治法减治法1. 循环直到序列循环直到序列A和序列和序列B均只有一个元素均只有一个元素 1.1 a = 序列序列A的中位数；的中位数；

8、1.2 b = 序列序列B的中位数；的中位数； 1.3 比较比较a和和b，执行下面三种情况之一：，执行下面三种情况之一： 1.3.1 若若a=b，则返回，则返回a，算法结束；，算法结束； 1.3.2 若若ab，则在序列，则在序列A中舍弃中舍弃a之后的元素，之后的元素，在序列在序列B中舍弃中舍弃b之前的元素，转步骤之前的元素，转步骤1； 2. 序列序列A和序列和序列B均只有一个元素，返回较小者；均只有一个元素，返回较小者；2 2一个简单的例子一个简单的例子两个序列的中位数两个序列的中位数第五章第五章 减治法减治法查找问题中的减治法查找问题中的减治法折半查找折半查找问题描述：应用折半查找方法在一个

9、有序序列中问题描述：应用折半查找方法在一个有序序列中查找值为查找值为k的记录。若查找成功，返回记录的记录。若查找成功，返回记录k在序在序列中的位置，若查找失败，返回失败信息。列中的位置，若查找失败，返回失败信息。 第五章第五章 减治法减治法折半查找折半查找想法想法折半查找利用了记录序列有序的特点，其查找过程是：取折半查找利用了记录序列有序的特点，其查找过程是：取有序序列的中间记录作为比较对象，若给定值与中间记录有序序列的中间记录作为比较对象，若给定值与中间记录相等，则查找成功；若给定值小于中间记录，则在中间记相等，则查找成功；若给定值小于中间记录，则在中间记录的左半区继续查找；若给定值大于中间

10、记录，则在中间录的左半区继续查找；若给定值大于中间记录，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。功，或所查找的区域无记录，查找失败。 r1 rmid-1 rmid rmid+1 rn 如果krmid查找这里k（mid=(1+n)/2）第五章第五章 减治法减治法折半查找折半查找实例实例在有序表在有序表 7, 14, 18, 21, 23, 29, 31, 35, 38 中查找值为中查找值为18的的过程如下：过程如下： 第五章第五章 减治法减治法1. low=1；high=n； /设置初始查找区

11、间设置初始查找区间2. 测试查找区间测试查找区间low，high是否存在，若不是否存在，若不存在，则查找失败；否则存在，则查找失败；否则3. 取中间点取中间点mid=(low+high)/2; 比较比较k与与rmid，有以下三种情况：有以下三种情况： 3.1 若若krmid，则，则low=mid+1；查找在右；查找在右半区进行，转半区进行，转2； 3.3 若若k=rmid，则查找成功，返回记录在，则查找成功，返回记录在表中位置表中位置mid；折半查找折半查找算法算法第五章第五章 减治法减治法查找问题中的减治法查找问题中的减治法二叉查找树二叉查找树在一个无序序列中执行查找操作，可以在一个无序序列

12、中执行查找操作，可以将无序序列建立一棵二叉查找树，然后将无序序列建立一棵二叉查找树，然后在二叉查找树中查找值为在二叉查找树中查找值为k的记录，若查的记录，若查找成功，返回记录找成功，返回记录k的存储地址，若查找的存储地址，若查找失败，返回空指针。失败，返回空指针。二叉查找树定义？二叉查找树定义？第五章第五章 减治法减治法二叉查找树查找二叉查找树查找想法想法由二叉查找树的定义，在二叉查找树由二叉查找树的定义，在二叉查找树root中查找中查找给定值给定值k的过程是：的过程是：若若root是空树，则查找失败；是空树，则查找失败；若若k根结点的值，则查找成功；根结点的值，则查找成功；若若k根结点的值，

13、则在根结点的值，则在root的右子树上查找；的右子树上查找；上述过程一直持续到查找成功或者待查找的子树上述过程一直持续到查找成功或者待查找的子树为空，如果待查找的子树为空，则查找失败。为空，如果待查找的子树为空，则查找失败。 二叉查找树二叉查找树=平衡二叉树？平衡二叉树？第五章第五章 减治法减治法在二叉查找树中查找关键字值为在二叉查找树中查找关键字值为35，95的过程：的过程：5030208090858840353250302080908588403532二叉查找树查找二叉查找树查找实例实例简述查找过程？简述查找过程？第五章第五章 减治法减治法BiNode * SearchBST( (BiNo

14、de *root, int k) ) if ( (root= =NULL) ) return NULL； else if ( (root-data=k) ) return root; else if ( (k-data) ) return SearchBST( (root-lchild, k) ); else return SearchBST( (root-rchild, k) ); 二叉查找树查找二叉查找树查找算法算法第五章第五章 减治法减治法查找问题中的减治法查找问题中的减治法选择问题选择问题问题描述：设无序序列问题描述：设无序序列T=(r1, r2, , rn)，T的第的第k（1kn）小

15、元素定义为）小元素定义为T按升序排列按升序排列后在第后在第k个位置上的元素。个位置上的元素。给定一个序列给定一个序列T和一个整数和一个整数k，寻找，寻找T的第的第k小元素的问题称为选择问题）。小元素的问题称为选择问题）。将寻找第将寻找第n/2小元素的问题称为中值问题。小元素的问题称为中值问题。第五章第五章 减治法减治法选择问题选择问题想法想法考虑快速排序的划分过程，一般情况下，设待划分的序列考虑快速排序的划分过程，一般情况下，设待划分的序列为为rirj，选定一个轴值对序列，选定一个轴值对序列rirj进行划分，使得比轴值进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值小的元

16、素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是的右侧，假定轴值的最终位置是s，则：，则：（1）若）若k=s，则，则rs就是第就是第k小元素；小元素；（2）若）若ks，则第，则第k小元素一定在序列小元素一定在序列rs+1 rj中；中；无论哪种情况，或者已经得出结果，或者将选择问题的查无论哪种情况，或者已经得出结果，或者将选择问题的查找区间减少一半（如果轴值恰好是序列的中值）。找区间减少一半（如果轴值恰好是序列的中值）。 分治法设计思想？两者在时间复杂分治法设计思想？两者在时间复杂度区别？度区别？第五章第五章 减治法减治法选择问题选择问题实例实例以以5为轴值划分序列为轴值

17、划分序列42，只在右侧查找，只在右侧查找以以4为轴值划分序列为轴值划分序列44,轴值第轴值第4小元素小元素5 3 8 1 4 6 9 2 72 3 4 1 5 6 9 8 72 3 4 1 2 4 3 4 3 3 4 找第找第4 4小的元素过程：小的元素过程：第五章第五章 减治法减治法选择问题选择问题算法算法1. 设置初始查找区间：设置初始查找区间：i=1; j=n; 2. 以以ri为轴值对序列为轴值对序列rirj进行一次划分，得进行一次划分，得到轴值的位置到轴值的位置s;3. 将轴值位置将轴值位置s与与k比较比较 3.1 如果如果k等于等于s，则将，则将rs作为结果返回；作为结果返回； 3.

18、2 否则，如果否则，如果k rj，则完全二叉树已经是堆，筛选，则完全二叉树已经是堆，筛选完毕；完毕； 3.2 否则将否则将ri和和rj交换；令交换；令i=j，转步骤，转步骤2继续进继续进行筛选；行筛选；第五章第五章 减治法减治法问题描述：假设有问题描述：假设有n=2k个选手进行竞技淘个选手进行竞技淘汰赛，最后决出冠军的选手，设计竞技淘汰赛，最后决出冠军的选手，设计竞技淘汰比赛的过程。汰比赛的过程。组合问题中的减治法组合问题中的减治法淘汰赛冠军问题淘汰赛冠军问题 第五章第五章 减治法减治法淘汰赛冠军问题淘汰赛冠军问题实例实例 第五章第五章 减治法减治法 string Game(string r

19、, int n) i=n; while (i1) i=i/2; for (j=0; ji; j+) if (Comp(rj+i, rj) rj=rj+i; return r0; 淘汰赛冠军问题淘汰赛冠军问题算法算法第五章第五章 减治法减治法问题描述：在问题描述：在n枚外观相同的硬币中，有枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。通过一一枚是假币，并且已知假币较轻。通过一架来任意比较两组硬币，从而得知两组硬架来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，币的重量是否相同，或者哪一组更轻一些，假币问题要求设计一个高效的算法来检测假币问题要求设计一个高效的算法来检测出这枚假币。出这枚假币。T(n)=O(log2n)组合问题中的减治法组合问题中的减治法假币问题假币问题 第五章第五章 减治法减治法最自然的想法就是一分为二，也就是把最自然的想法就是一分为二，也就是把n枚硬币枚硬币分成两组，每组有分成两组，每组有 n/2 枚硬币，如果枚硬币，如果n为奇数，为奇数，就留下一枚硬币，然后把两组硬币分别放到天平就留下一枚硬币，