《数据结构与算法分析》课件第8章-缩小规模策略

第八章缩小规模策略小规模问题的解经过某种组合可以较容易地得到原问题的解。解决这类问题的求解方法有：分治与递归、动态规划和贪心算法，这章将介绍分治与递归。分治与递归策略递归的典型应用分治策略的应用缩小规模策略将一个难以直接解决的大问题，分解成多个规模较小的子问题，以便各个击破、分而治之。分治法：如果原问题可以分割为k个子问题，1＜k≤n，且这k个子问题都可解，并可利用子问题的解计算出原问题的解，则可以采用分治法。递归：分治法产生的子问题往往是原问题的较小模式，常使用递归技术。一个直接或间接调用自身的算法称为递归算法。递归策略定义特点需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。用有限的语句来定义对象的无限集合。

使用条件①

原问题可以通过转化为较小的子问题来解决，而子问题的求解方法与原问题相同，被处理的数据有规律地减少。②当子问题减小至一定程度时，调用自身算法的过程终止。递归需要有边界条件、递归推进部分和递归返回递归策略整数划分问题将一个正整数n表示为一系列正整数之和：n = n1 + n2 + … + nk,其中，n1≥n2≥…≥nk≥1，k≥1。该表示称为n的一个划分；不同划分的个数称为划分数，记为p(n)。【例1】整数6的11种划分。6；5 + 1；4 + 2，4 + 1 + 1；3 + 3，3 + 2 + 1，3 + 1 + 1 + 1;2 + 2 + 2,2 + 2 + 1 + 1,2 + 1 + 1 + 1 + 1;1 + 1 + 1 + 1 + 1 + 1;递归策略分析在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记为q(n，m)，则可以建立如下的递归关系：(1)q(n，1)=1，n≥1当最大加数n1不大于1时，只有一种划分形式：n=1+1+…+1(2)q(n，m)=q(n，n)，m≥n最大加数n1不能大于n，因此q(1，m)=1(3)q(n,n)=1+q(n,n-1)正整数n的划分，由n1= n的划分和n1≤n-1的划分组成(4)q(n,m)=q(n,m - 1)+q(n - m,m),n＞m>1正整数n的最大加数n1不大于m的划分，由n1=m的划分和n1≤m-1的划分组成递归策略计算q(n,m)的递归计算式分治策略基本思想将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归求解这些子问题，并将子问题的解合并，则得到原问题解。分治法求解问题的特征(1)

问题的规模缩小到一定的程度就可容易解决(2)

问题可分解为若干个规模较小的相同问题(3)

利用原问题分解出的子问题的解可合并为原问题的解(4)

问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题分治策略分治法的一般步骤分解

将要解决的问题划分成若干规模较小的同类问题求解

当子问题划分得足够小时，用较简单的方法解决合并

按原问题要求，将子问题的解逐层合并构成原问题解DataTypeDivide-and-Conquer(P){if(|P|<=n0)

Adhoc(P);dividePintosmallersubinstances;P1,P2,…,Pk;for(i=1;i<=k;i++)

y[i]=Divide-and-Conquer(Pi);returnMerge(y1,y2,…,yk);}分治算法设计模式递归算法的典型应用数据的定义按递归定义，如斐波那契(Fibonacci)数列的求解问题解法按递归算法实现，如二叉树、广义表等数据的结构形式是按递归定义的，如Hanoi问题递归算法常用于解决下述问题：递归算法的典型应用Hanoi塔问题问题描述借助B杆，将A杆的金片全部移到C杆，并仍保持原有顺序，要求在移动过程中不能大片压小片。递归算法的典型应用过程分解(1)以C杆为中介，将前n-1个金片从A杆挪到B杆(2)将A杆上仅剩的第n个金片移动到B杆(3)

以A杆为中介，将C杆上的n-1个金片移到B杆递归算法的典型应用递归函数//将from杆上的n-1块金片以tmp为中移至to杆voidHanoi(intn,charfrom,chartmp,charto){

if(n>0){

hanoi(n-1,from,to,tmp);

//将from杆上的n-1块金片移至tmp杆

printf("take%d块金片from%cto%c\n",n,from,to);

//将from上的一块金片移至yo杆

hanoi(n-1,tmp,from,to);

//将tmp杆上的n-1块金片移至to杆上

}}//Hanoi递归算法的典型应用全排列问题问题描述R={r1，r2，…，rn}是要进行排列的n个元素，Ri=R{ri}。集合X中元素的全排列记为Perm(X)；(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可递归定义为：(1)当n=1时，Perm(R)=(r1)，r1是集合R中的唯一元素。(2)当n＞1时，Perm(R)由(r1)Perm(R1)，(r2)Perm(R2)，…，(rn)Perm(Rn)构成。递归算法的典型应用【例2】集合{1,2,3}的全排列。递归算法的典型应用递归算法voidSwap(int&a,int&b){intt=a;a=b;b=t;}

//SwapvoidPerm(intR[],intk,intm){//产生集合R[k:m]的全排列

if(k==m){//R[k:m]具有一个排列，将其输出 for(inti=0;i<=k;i++)printf("%d",R[i]);

printf("\n");

}

else{//R[k:m]具有多个排列并递归生成

for(inti=k;i<=m;i++){

Swap(R[k],R[i]);Perm(R,k+1,m);Swap(R[k],R[i]);

}

}

}//Perm分治策略的应用二分搜索基本思想R[n/2]＝k——算法终止R[n/2]＞k——在R[]的左半部搜索R[n/2]＜k——在R[]的右半部搜索对有序表R[0~n-1]，将给定关键字k与中间位置元素的关键字进行比较，若：每次比较将待查记录区间缩小一半分治策略的应用实现表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中界点，k为待查值

重复上述操作，直至low>high时，查找失败将k与mid指向的记录比较若k==r[mid].key，则若k<r[mid].key，则若k>r[mid].key，则分治策略的应用查找过程找211

234567891011

51319213756

647580

8892highlowmid1

234567891011

51319213756

647580

8892lowhighmid查找成功1

234567891011

51319213756

647580

8892lowhighmid21分治策略的应用找661

2345678910

51019213137

424850

55highlowmid1

2345678910

51019213137

424850

55lowhighmidhighlowmid55highlowlowmid1

2345678910

51019213137

424850

55high查找失败分治策略的应用算法intBinerSerch(intR[],intx)

{

intlow,mid,high;

low=0;high=n-1;

while(low<=high)

{

mid=(low+high)/2;

if(x==R[mid])returnmid;

if(x<R[mid])high=mid-1;

elselow=mid+1;

}return-1;}分治策略的应用性能分析第i次比较剩余n/2i若最后只剩一个，则n/2i=1，即i=log2n即比较次数O(log2n)时间复杂度O(log2n)

特点表中元素需有序排列，且顺序存储。但对需频繁插入或删除操作的数据集来说，维护有序会有较大的工作量。分治策略的应用查找判定树

描述查找过程的二叉树。树中结点的数字表示该结点在有序表中的位置（1~n）。6391741025811【例3】具有11个结点的折半查找判定树。结论：在查找成功时进行的比较次数最多不超过树的深度。分治策略的应用【例4】建立具有13个结点的判定树，并其成功查找的ASL。73101851224139611ASL=1/13×(1+2×2+3×4+4×6)=41/13≈3.15分治策略的应用归并排序基本思想两路归并设初始序列含n个记录，可看成n个有序子序列，各序列长度为1；再两两合并，……如此重复，直至得到长度为n的有序序列。两两合并，得到

n/2

个长度为2或1的有序子序列;将元素集合分割成n个（≥2）子集，对每个子集分别排序，再将排好序的子集归并为一个集合。若n为1，排序终止。分治策略的应用【例5】两路归并过程示例。分治策略的应用算法——两个有序文件的合并voidMerge(rectypeR[],rectypeT[],intlow,intmid,inthigh){

//R[low～mid]与R[mid+1～high]是两个有序文件

//结果文件T[low～high]

inti,j,k;

i=low;

j=mid+1;

k=low;

while((i<=mid)&&(j<=high))

if(R[i].key<=R[j].key)T[k++]=R[i++];

elseT[k++]=R[j++];

while(i<=mid)T[k++]=R[i++];

while(j<=high)T[k++]=R[j++];}分治策略的应用算法——一趟归并voidMergePass(rectypeR[],rectypeT[],intlen){

//

对R中n/len个有序子文件做一趟归并，结果放在T中

inti,j;

i=0;//i向第一对子文件的起始点

while(i+2

len

1<n){//两个长度为len的有序子文件

Merge(R,T,i,i+len-1,i+2

len-1);

i=i+2

len;//i指向下一对子文件的起始点

}

if((i+len-1)<n-1)//子文件个数偶数,一个长度小于len

Merge(R,T,i,i+len-1,n-1);

else

//子文件个数为奇数

for(j=i;j<n;j++)T[j]=R[j];

}分治策略的应用算法——两路归并voidMergeSort(rectypeR[]){

//对R进行二路归并排序

intlen;

len=1;

while(len<n)

{

MergePass(R,T,len);

//一趟归并，结果在T中

len=2

len;//若n≥len,则将T复制回R

MergePass(T,R,len);

//再次归并，结果在R中

len=2

len;

}

}

分治策略的应用算法评价空间复杂度第i趟归并后，有序子文件长度2i，故需log2n趟归并，每趟归并时间O(n)。T(n)=O(nlog2n)时间复杂度S(n)=O(n)排序稳定性稳定排序分治策略的应用快速排序基本思想n个元素被分成3段：左段left，右段right和中段middle。中段仅一个元素。左段中各元素都小于中段元素，右段中各元素都大于等于中段元素。left和right都可独立排序，且不必对left和right的排序结果进行合并。

任意选取一记录做"基准"，通过一趟排序，将基准记录放在表最终位置上，同时在基准前后各形成两个子表。前子表的所有元素关键字均小于基准，而后子表都大于(等于)它。

再对两个子表重复以上过程，至每个子表只有一个元素。分治策略的应用【例6】快速排序过程示例。分治策略的应用【例6】快速排序过程示例。分治策略的应用算法intPartition(rectypeR[],intl,inth){

//对R[l]到R[h]划分

inti,j;rectypetemp;

i=l;j=h;temp=R[i];//初始化,temp为基准

do{

while((R[j].key>=temp.key)&&(i<j