第5章 减治法 修改

第五章减治法1234减治法的设计思想排序问题中的减治法组合问题中的减治法5查找问题中的减治法小结子问题的规模是n/2子问题的解原问题的解原问题的规模是n（1）原问题的解只存在于其中一个较小规模的子问题中;（2）原问题的解与其中一个较小规模的解之间存在某种确定的对应关系。1减治法的设计思想对于给定的整数a和非负整数n，计算an的值应用减治技术得到如下计算方法：应用分治技术得到如下计算方法：应用分治法（例如二分法）得到的算法通常具有如下递推式：分治法和减治法区别应用减治法（例如减半法）得到的算法通常具有如下递推式：

所以，通常来说，应用减治法处理问题的效率是很高的，一般是O(log2n)数量级。

减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：

2一个简单的例子—两个序列的中位数问题描述：一个长度为n（n≥1）的升序序列S，处在第n/2个位置的数称为序列S的中位数。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。想法：分别求出两个序列的中位数，记为a和b；比较a和b，有下列三种情况：①a=b：则a即为两个序列的中位数；②a<b：则中位数只能出现在a和b之间，在序列A中舍弃a之前的元素得到序列A1，在序列B中舍弃b之后的元素得到序列B1；③a>b：则中位数只能出现在b和a之间，在序列A中舍弃a之后的元素得到序列A1，在序列B中舍弃b之前的元素得到序列B1；在A1和B1中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。2一个简单的例子—两个序列的中位数对于两个给定的序列A={11,13,15,17,19},B={2,4,10,15,20}，求序列A和B的中位数的过程。步骤操作说明序列A序列B1初始序列{11,13,15,17,19}{2,4,10,15,20}2分别求中位数{11,13,15,17,19}{2,4,10,15,20}315>10，结果在[10,15]之间舍弃15之后元素，{11,13,15}舍弃10之前元素，{10,15,20}4分别求中位数{11,13,15}{10,15,20}513<15，结果在[11,15]之间舍弃13之前元素，{13,15}舍弃15之后元素，{10,15}6分别求中位数{13,15}{10,15}710<13，结果在[10,13]之间舍弃13之后元素，{13}舍弃10之前元素，{15}8长度为1，较小者为所求{13}{15}2一个简单的例子—两个序列的中位数1.循环直到序列A和序列B均只有一个元素

1.1a=序列A的中位数；

1.2b=序列B的中位数；

1.3比较a和b，执行下面三种情况之一：

1.3.1若a=b，则返回a，算法结束；

1.3.2若a<b，则在序列A中舍弃a之前的元素，在序列B中舍弃b之后的元素，转步骤1；

1.3.3若a>b，则在序列A中舍弃a之后的元素，在序列B中舍弃b之前的元素，转步骤1；

2.序列A和序列B均只有一个元素，返回较小者；2一个简单的例子—两个序列的中位数查找问题中的减治法——折半查找问题描述：应用折半查找方法在一个有序序列中查找值为k的记录。若查找成功，返回记录k在序列中的位置，若查找失败，返回失败信息。5.2查找问题中的减治法

5.2.1折半查找

5.2.2二叉查找树折半查找——想法折半查找利用了记录序列有序的特点，其查找过程是：取有序序列的中间记录作为比较对象，若给定值与中间记录相等，则查找成功；若给定值小于中间记录，则在中间记录的左半区继续查找；若给定值大于中间记录，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

[r1………rmid-1]rmid

[rmid+1………rn]如果k<rmid查找这里如果k>rmid查找这里k（mid=(1+n)/2）例：查找值为14的记录的过程：

0123456789101112137141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=141.low=1；high=n；//设置初始查找区间2.测试查找区间［low，high］是否存在，若不存在，则查找失败；否则3.取中间点mid=(low+high)/2;比较k与r[mid]，有以下三种情况：

3.1若k<r[mid]，则high=mid-1；查找在左半区进行，转2；

3.2若k>r[mid]，则low=mid+1；查找在右半区进行，转2；

3.3若k=r[mid]，则查找成功，返回记录在表中位置mid；折半查找——算法判定树——描述折半查找的判定过程。长度为n的判定树的构造方法为：

（1）当n=0时，判定树为空；（2）当n＞0时，判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1]~r[mid-1]相对应的判定树，根结点的右子树是与r[mid+1]~r[n]相对应的判定树。具有11个结点的判定树6312548111079

在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。具有n个结点的判定数的深度为。5.2.2查找问题中的减治法——二叉查找树在一个无序序列中执行查找操作，可以将无序序列建立一棵二叉查找树，然后在二叉查找树中查找值为k的记录，若查找成功，返回记录k的存储地址，若查找失败，返回空指针。二叉查找树定义？二叉查找树查找——想法由二叉查找树的定义，在二叉查找树root中查找给定值k的过程是：⑴若root是空树，则查找失败；⑵若k＝根结点的值，则查找成功；⑶若k<根结点的值，则在root的左子树上查找；⑷若k>根结点的值，则在root的右子树上查找；上述过程一直持续到查找成功或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉查找树=平衡二叉树？在二叉查找树中查找关键字值为35，95的过程：5030208090858840353250302080908588403532二叉查找树查找——实例简述查找过程？BiNode*SearchBST(BiNode*root,intk){if(root==NULL)returnNULL；

elseif(root->data==k)

returnroot;elseif(k<root->data)

returnSearchBST(root->lchild,k);elsereturnSearchBST(root->rchild,k);}二叉查找树查找——算法

在二叉排序树上查找关键码等于给定值的结点的过程，恰好走了一条从根结点到该结点的路径，和给定值的比较次数等于给定值的结点在二叉排序树中的层数，比较次数最少为1次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。具有n个结点的二叉树的深度至少是，至多是n，所以，二叉排序树的查找性能在O(log2n)和O(n)之间。

问题：如何建立二叉查找树？输入数据{53,78,65,17,87,09,81,15}二叉搜索树的建立输入数据{53,78,65,17,87,09,81,15}要求：创建一棵二叉搜索树53537853786553786517537865871753786509178753786581178709537865151787098135154550402510203028插入新结点28二叉搜索树的插入每次结点的插入，都要从根结点出发搜索插入位置，然后把新结点作为叶结点插入。为了向二叉搜索树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。搜索成功:树中已有这个元素,不再插入。搜索不成功:树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。问题2：二叉搜索树的形态只有一种吗？

同样3个数据{1,2,3}，输入顺序不同，建立起来的二叉搜索树的形态也不同。这直接影响到二叉搜索树的搜索性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉搜索树的高度达到最大。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}

1231321231231235.2.3查找问题中的减治法——选择问题问题描述：设无序序列T=(r1,r2,…,rn)，T的第k（1≤k≤n）小元素定义为T按升序排列后在第k个位置上的元素。给定一个序列T和一个整数k，寻找T的第k小元素的问题称为选择问题）。将寻找第n/2小元素的问题称为中值问题。应用：中值滤波选择问题——想法考虑快速排序的划分过程，一般情况下，设待划分的序列为ri～rj，选定一个轴值对序列ri～rj进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位置是s，则：（1）若k=s，则rs就是第k小元素；（2）若k<s，则第k小元素一定在序列ri

～rs-1中；（3）若k>s，则第k小元素一定在序列rs+1

～rj中；无论哪种情况，或者已经得出结果，或者将选择问题的查找区间减少一半（如果轴值恰好是序列的中值）。分治法设计思想？两者在时间复杂度区别？选择问题——实例以5为轴值划分序列4<5，只在左侧查找以2为轴值划分序列4>2，只在右侧查找以4为轴值划分序列4＝4,轴值第4小元素5381469272341569872341

243

4334

找第4小的元素过程：选择问题——算法1.设置初始查找区间：i=1;j=n;2.以ri为轴值对序列ri~rj进行一次划分，得到轴值的位置s;3.将轴值位置s与k比较

3.1如果k等于s，则将rs作为结果返回；

3.2否则，如果k<s，则j=s-1，转步骤2；

3.3否则，i=s+1，转步骤2；5.3排序问题中的减治法

5.3.2堆排序

5.3.1插入排序插入排序

基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。直接插入排序(InsertSort)

基本思想：当插入第i个对象时，前面的R[1],R[2],…,R[i-1]已经排好序，此时，用R[i]的关键字与R[i-1],R[i-2],…的关键字顺序进行比较，找到插入位置即将R[i]插入，原来位置上对象向后顺移。直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i=2;i<n;i++){R[0]＝R[i];j＝i-1;while(R[0].key<R[j].key)R[j+1]＝R[j--];R[j+1]＝R[0];}}算法中引入附加记录R[0]有两个作用：其一是进入查找循环之前，它保存了R[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），R[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。因此，我们把R[0]称为“监视哨”。直接插入排序举例i(1)(2)(3)(4)(5)(6)(0)[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]算法分析直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。若初始时关键字递增有序（正序），这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的移动次数为2(n-1)。若初始时关键字递减有序（反序），这是最坏情况。这时的记录比较和移动次数分别为：直接插入排序的稳定性直接插入排序是一种稳定的排序方法。原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。5.3.2排序问题中的减治法——堆排序堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（小根堆）；或者每个结点的值都大于或等于其左右孩子结点的值（大根堆）。如果将具有n个结点的堆按层序从1开始编号，则结点之间满足如下关系：问题描述：应用堆排序方法对一个记录序列进行升序排列。ki≤k2iki≤k2i+1ki≥k2iki≥k2i+11≤i≤n/2或堆排序——想法堆排序是利用堆（假设利用大根堆）的特性进行排序的方法，其基本思想是：首先将待排序的记录序列构造成一个堆，此时，堆顶记录是堆中所有记录的最大者，将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），然后将剩余记录再调整成堆，这样又找出了次大记录，以此类推，直到堆中只有一个记录为止。堆排序——实例282516321836163216282518362532162818362528323628161825堆排序——算法1.设置i和j，分别指向当前要筛选的结点和要筛选结点的左孩子；2.若ri已是叶子，则筛选完毕；否则，比较要筛选结点的左右孩子，并将j指向值较大的结点；3.将ri和rj进行比较，有以下两种情况：

3.1如果ri>rj，则完全二叉树已经是堆，筛选完毕；

3.2否则将ri和rj交换；令i=j，转步骤2继续进行筛选；算法5.4——筛选法调整堆

voidSiftHeap(intr[],intk,intn){i=k;j=2*i;//置i为要筛的结点，j为i的左孩子

while(j<=n)//筛选还没有进行到叶子

{if(j<n&&r[j]<r[j+1])j++;//比较i的左右孩子，j为较大者

if(r[i]>r[j])//根结点已经大于左右孩子中的较大者

break;else{r[i]←→r[j];//将根结点与结点j交换

i=j;j=2*i;//被筛结点位于原来结点j的位置

}}}C++描述5.4

组合问题中的减治法5.4.1淘汰赛冠军问题

5.4.2假币问题问题描述：假设有n=2k个选手进行竞技淘汰赛，最后决出冠军的选手，设计竞技淘汰比赛的过程。组合问题中的减治法——淘汰赛冠军问题

淘汰赛冠军问题——实例

stringGame(stringr[],intn){i=n;while(i>1){i=i/2;for(j=0;j<i;j++)if(Comp(r[j+i],r[j]))r[j]=r[j+i];}returnr[0];}淘汰赛冠军问题——算法问题描述：在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。通过一架来任意比较两组硬币，从