算法设计与分析-第03周-分治策略2课件

第2章分治策略(2)教学目的与要求1.掌握设计有效算法的分治策略。2.要求通过范例的学习掌握分治策略的技巧。第2章分治策略(2)教学目的与要求2.9线性时间选择给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。采用分治策略，利用在快速排序中使用到的RandomizedPartition算法，将序列随机分成两部分a[p…i]和a[i+1…r]，使得a[p…i]的每个元素都不大于a[i+1…r]的每个元素，而此时a[i]恰好为第i小元素，接着计算子数组a[p…i]的元素个数j，如果k≤j，则a[p…r]中第k小的数落在子数组a[p…i]中，如果k>j，则a[p…r]中第k小的数落在子数组a[i+1…r]中，此时要找的a[p…r]中第k小的元素是a[i+1…r]中第k-j小的元素。2.9线性时间选择给定线性序集中n个元素和一个整数k，1≤template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p],t;//将<x的元素交换到左边区域，将>x的元素交换到右边区域

while(true){while(a[++i]<x);//从左到右找到第一个不小于a[p]的元素a[i]while(a[--j]>x);//从右到左找到第一个不大于a[p]的元素a[j]if(i>=j)break;t=a[i];a[i]=a[j];a[j]=t;//交换a[i]和a[j]}a[p]=a[j];a[j]=x;//交换a[p]和a[j]returnj;}template<classType>template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Typet;t=a[i];a[i]=a[p];a[p]=t;returnPartition(a,p,r);}template<classType>template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){inti,j;if(p==r)returna[p];i=RandomizedPartition(a,p,r);j=i-p+1;//计算子数组a[p…i]的元素个数jif(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}template<classType>在最坏情况下（如在找最小元素时，总在最大元素处划分），算法RandomizedSelect需要(n2)计算时间，但该算法的平均性能较好。如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。在最坏情况下（如在找最小元素时，总在最大元素处划分），算法R例如，将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用Select来找出这n/5个元素的中位数（也就是这些中位数的中位数），若n/5是偶数，则找它的两个中位数中较大的一个，然后以这个元素作为基准划分。例如，将n个输入元素划分成n/5个组，每组5个元素，只可设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-template<classType>intPartition(Type*a,intp,intr,Typex){inti,left=p,right=r;Type*b=newType[r-p+1];for(i=0;i<r-p+1;i++){b[i]=a[p+i];}for(i=p;i<=r;i++){if(b[i]<x){a[left++]=b[i];}elseif(b[i]>x){a[right--]=b[i];}}for(i=left;i<=right;i++)a[i]=x;delete[]b;returnleft;}template<classType>//找a[p..r]中第k小的元素返回template<classType>TypeSelect(Typea[],intp,intr,intk){inti,j;Typex,t;if(r-p<75){Sort(a,p,r);returna[p+k-1];}for(i=0;i<=(r-p-4)/5;i++){x=a[p+5*i]至a[p+5*i+4]的第3小元素;//将a[p+5*i...p+5*i+4]的第3小元素与a[p+i]交换位置

t=a[p+i];a[p+i]=x;x=t;}//找a[p..r]中第k小的元素返回/*每一组的中位数排在了a[p..p+(r-p-4)/5]的位置，现在找中位数的中位数x，r-p-4即上面所说的n-5*/x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);/*将a[p…r]中不大于x的放在x左边，比x大的放在x右边，返回中位数的中位数x的下标i*/i=Partition(a,p,r,x),j=i-p+1;//求x左边有多少个元素，这些元素都比x小

if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}/*每一组的中位数排在了a[p..p+(r-p-4)上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。设n=r-p+1，即n为输入数组的长度，算法的递归调用在n≥75时才执行，n<75的时候，算法Select所用的计算时间不超过常数C1，找到中位数的中位数x后，算法Select以x为基准调用函数Partition对数组a[p…r]进行划分，这需要O(n)时间，算法Select的for循环体执行了n/5次，每一次需要O(1)时间，因此执行for循环共需要O(n)时间。上述算法将每一组的大小定为5，并选取75作为是否作递归调用的设对n个元素数组调用Select算法需要T(n)时间，那么找中位数的中位数x至多用了T(n/5)次时间，既然按照基准x划分所得到的两个子数组分别至多3n/4个元素，所以不论对哪一个子数组调用Select算法都至多用了T(3n/4)的时间。因此，得到，T(n)=O(n)设对n个元素数组调用Select算法需要T(n)时间，那么找2.10最接近点对问题给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。最接近点对可能多于一对，简单起见，只考虑找其中的一对作为问题的解。如果我们将每一个点和其他n-1个点的距离算出来，找到最小距离的两个点，算法效率需要O(n2)的计算时间，效率太低。下面设计一个耗时O(nlog2n)的算法：2.10最接近点对问题给定平面上n个点，找出其中一对点，使为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。问题在于：能否在线性时间内找到p3、q3？为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。问题在于：能否在线性时间内找到p、q？选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p,q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中。由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者。考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形。若矩形R中有多于6个S中的点，由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)<d，与d的意义矛盾。证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点，距离p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。下面给出用分治法求二维最接近点对算法：为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影boolCpair2(S,&d){n=|S|;if(n<2)returnfalse;1、m=S中各点x坐标下标的中位数;

构造S1和S2,S1={p∈S|x(p)<=x(m)},S2={p∈S|x(p)>x(m)}2、Cpair2(S1,d1);Cpair2(S2,d2);3、dm=min(d1,d2);4、令P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中的点依其y坐标值排序；并设X和Y是相应的已排好序的点列；第1步：O(n)第3步：O(1)第2步：2T(n/2)第4步：O(nlog2n)boolCpair2(S,&d)第1步：O(n)第3步：O第5步：O(n)5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；

6、d=min(dm,dl);returntrue;}若在每次执行第4步的时候进行排序，则最坏情况下第4步需要O(nlog2n)时间，这不符合要求，需要做一个技术处理。第6步：O(1)第5步：O(n)5、通过扫描X以及对于X中每个点检查Y中与使用预排序技术，在使用分治法之前，预先将S中n个点依其y坐标排好序，设排好序的点为P*，在执行分治法的第4步时，只要对P*进行1次线性扫描，即可抽取出我们所需要排好序的点列X和Y。然后，在第5步中再对X做一次线性扫描，即可求得dl。因此，第4步和第5步两遍扫描合在一起只要用O(n)时间。这样，经过预排序处理后算法后，算法Cpair2所需的计算时间T(n)满足递归方程即T(n)=O(nlog2n)。根据这个思想，写出的程序如下：使用预排序技术，在使用分治法之前，预先将S中n个点依其y坐标#include<iostream>#include<math.h>constintTOTAL=10000;usingnamespacestd;classPoint{public:doublegetx()const{returnx;}doublegety()const{returny;}doublesetx(doublexx){x=xx;returnx;}doublesety(doubleyy){y=yy;returny;}virtualbooloperator<=(Pointa){returntrue;}protected:doublex,y;};#include<iostream>//类PointX和PointY分别表示按照x坐标和y坐标排序的点classPointX:publicPoint{public:booloperator<=(Pointa)const{return(x<=a.getx());}friendinlinedoubledistance(constPointX&u,constPointX&v);};classPointY:publicPoint{public:booloperator<=(Pointa)const{return(y<=a.gety());}intsetp(intpp){p=pp;returnp;}intgetp(){returnp;}friendinlinedoubledistance(constPointY&u,constPointY&v);private:intp;//p表示以x坐标排序时，该点对应的下标(序号)};//类PointX和PointY分别表示按照x坐标和y坐标排inlinedoubledistance(constPointX&u,constPointX&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoulbledistance(constPointY&u,constPointY&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoubledistance(constPtemplate<classType>voidMerge(TypeY[],TypeZ[],intl,intm,intr){//将有序的Z[l...m]与有序的Z[m+1...r]合并到Y[l...r]Type*a=&Z[l];Type*b=&Z[m+1];Type*c=&Y[l];intanum=m-l+1,ap=0;intbnum=r-m,bp=0;intcnum=r-l+1,cp=0;while(ap<anum&&bp<bnum){if(a[ap]<=b[bp])c[cp++]=a[ap++];elsec[cp++]=b[bp++];}while(ap<anum)c[cp++]=a[ap++];while(bp<bnum)c[cp++]=b[bp++];}template<classType>template<classType>voidMergeSort(Typea[],intn){intanum,bnum,i;Type*b,*c;if(n<=1)return;anum=n/2;b=a+anum;bnum=n-anum;MergeSort(a,anum);MergeSort(b,bnum);c=newType[n];Merge(c,a,0,anum-1,n-1);for(i=0;i<n;i++)a[i]=c[i];delete[]c;}template<classType>/*X存放输入的点集，X和Y分别表示按照x坐标和y坐标排序的点，l和r表示点集Y中成员p的范围*/voidclosest(PointXX[],PointYY[],PointYZ[],intl,intr,PointX&a,PointX&b,double&d){doubled1,d2,d3,dp;intf,g,m,i,j,k;doubledr;PointXar,br;if(r-l==1)//2点的情况

{a=X[l];b=X[r];d=distance(X[l],X[r]);return;}/*X存放输入的点集，X和Y分别表示按照x坐标和y坐标排序的if(r-l==2)//3点的情况

{d1=distance(X[l],X[l+1]);d2=distance(X[l+1],X[r]);d3=distance(X[l],X[r]);if(d1<=d2&&d1<=d3){a=X[l];b=X[l+1];d=d1;}elseif(d2<=d3){a=X[l+1];b=X[r];d=d2;}else{a=X[l];b=X[r];d=d3;}return;}if(r-l==2)//3点的情况m=(l+r)/2;//m为点集Y中成员p的范围的中位数

/*将已经按照y坐标排序的点集Y[l..r]，等分成两个子集复制到Z，其中Z[l..(l+r)/2]中的每个点的x坐标都小于Z[(l+r)/2+1..r]中的每个点的x坐标*/f=l;g=m+1;for(i=l;i<=r;i++){if(Y[i].getp()>m)Z[g++]=Y[i];elseZ[f++]=Y[i];}m=(l+r)/2;//m为点集Y中成//递归处理这两个子集(注意参数传递时Z与Y位置的变化)closest(X,Z,Y,l,m,a,b,d);closest(X,Z,Y,m+1,r,ar,br,dr);if(dr<d)//d表示这两个子集中各自找到的最近点对的距离较小者

{a=ar;b=br;d=dr;}Merge(Y,Z,l,m,r);//重构数组Y//将与分割线距离为d的点置如数组Z中

k=l;for(i=l;i<=r;i++){if(fabs(Y[m].getx()-Y[i].getx())<d)Z[k++]=Y[i];}//递归处理这两个子集(注意参数传递时Z与Y位置的变//搜索Z[l..k-1]，若其中存在两点的距离小于d，则更新dfor(i=l;i<k;i++){for(j=i+1;j<k&&Z[j].gety()-Z[i].gety()<d;j++){dp=distance(Z[i],Z[j]);if(dp<d){d=dp;a=X[Z[i].getp()];b=X[Z[j].getp()];}}}}//搜索Z[l..k-1]，若其中存在两点的距离小于boolCpair2(PointXX[],intn,PointX&a,PointX&b,double&d){inti;PointY*Z,*Y;if(n<2)returnfalse;MergeSort(X,n);//将各点按照x坐标排序

Y=newPointY[n];for(i=0;i<n;i++)//将数组X内的信息写入数组Y{Y[i].setp(i);//同一点在数组X中的坐标的下标

Y[i].setx(X[i].getx());Y[i].sety(X[i].gety());}MergeSort(Y,n);//将各点按照y坐标排序

Z=newPointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete[]Y;delete[]Z;returntrue;}boolCpair2(PointXX[],intn,intmain(){PointXX[TOTAL],a,b;intn=TOTAL;doubled;inti;for(i=0;i<n;i++){X[i].setx((double)rand()/100);X[i].sety((double)rand()/100);}Cpair2(X,n,a,b,d);printf("(%f,%f)(%f,%f)%f\n",a.getx(),a.gety(),b.getx(),b.gety(),d);return0;}intmain()2.11循环赛日程问题设有n=2k(k为正整数)个运动员进行乒乓球循环赛正赛，现要求设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。将比赛日程设计为n行和n-1列的一个表，在表中第i行第j列处填写第i个选手在第j天的对手。按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。

2.11循环赛日程问题设有n=2k(k为正整数)个运动员进图中所列出的正方形表是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。该算法没有使用递归，这也说明并非所有的分治策略都要使用递归。1234567821436587341278564321876556781234658721437856341287654321图中所列出的正方形表是8个选手的比赛日程表。其中左上角与左下12345678以k=3，n=8名选手为例。初始状态：填写第0列。之后，进行k=3个阶段，设第s个阶段要循环ns次，则n1=n/2=4，n2=n1/2=2，n3=n2/2=11221344356657887第1阶段（s=1）：填写第1列（j=1）循环4次，循环次数为n1=n/2=4，8个大块，每个大块含m*m=1*1个小块，每次循环复制2个大块，在第t（t=0,1,2,3）次循环时，执行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m]，i=1，分别把左下角复制到右上角，把左上角复制到右下角

12345678以k=3，n=8名选手为例。初始状态：填写第12342143341243215678658778568765第2阶段（s=2）：填写第2,3列（j=2,3）循环2次，循环次数为n2=n1/2=2，4个大块，每个大块含m*m=2*2个小块，每次循环复制2个大块，在第t（t=0,1）次循环时，执行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m]，i=2,3，分别把左下角复制到右上角，把左上角复制到右下角1234567821436587341278564321876556781234658721437856341287654321第3阶段（s=3）：填写第4,5,6,7列（j=4,5,6,7）循环1次，循环次数为n3=n2/2=2，2个大块，每个大块含m*m=4*4个小块，每次循环复制2个大块，在第t（t=0）次循环时，执行a[i+2*t*m-m][j]=a[i+2*t*m][j-m]和a[i+2*t*m][j]=a[i+2*t*m-m][j-m]，i=4,5,6,7，分别把左下角复制到右上角，把左上角复制到右下角123421433412432156786587785687voidTable(intk,inta[][N]){intn=1,m=1,i,j,t,s;for(i=1;i<=k;i++)n*=2;for(i=0;i<n;i++){a[i][0]=i+1;}//k个阶段，从左到右

for(s=1;s<=k;s++){n/=2;/*每个阶段有t次循环，即复制n个大块*/for(t=0;t<n;t++){//j表示列

for(j=m;j<2*m;j++){for(i=m;i<2*m;i++){a[i-m+2*t*m][j]=a[i+2*t*m][j-m];//右上角=左下角

a[i+2*t*m][j]=a[i-m+2*t*m][j-m];//右下角=左上角

}}}m*=2;}}voidTable(intk,inta[][N])voidTable(intk,inta[][N]){intn=1,m=1,i,j,t,s;for(i=1;i<=k;i++)n*=2;for(i=0;i<n;i++){a[i][0]=i+1;}voidTable(intk,inta[][N])for(s=1;s<=k;s++)//k个阶段，从左到右

{n/=2;for(t=0;t<n;t++)//每个阶段有t次循环，即复制n个大块

{for(j=m;j<2*m;j++)//j表示列

{for(i=m;i<2*m;i++){a[i-m+2*t*m][j]=a[i+2*t*m][j-m];////右上角=左下角

a[i+2*t*m][j]=a[i-m+2*t*m][j-m];//右下角=左上角

}}}m*=2;}}for(s=1;s<=k;s++)//循环赛日程安排问题也可以写成递归算法，如下：voidtable(intx,intk,int**a){//此函数为从x号球员起的共2的k次方名球员安排日程表

inti,j,y;if(k==1)//只有两名球员

{a[x][0]=x;a[x][1]=x+1;a[x+1][0]=x+1;a[x+1][1]=x;}循环赛日程安排问题也可以写成递归算法，如下：

else{y=pow(2,k-1);table(x,k-1,a);table(x+y,k-1,a);for(i=x;i<x+y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i+y][j-y];}else

for(i=x+y;i<x+2*y;i++){for(j=y;j<2*y;j++)a[i][j]=a[i-y][j-y];}}}for(i=x+y;i<x+2*y;i+本周课程结束，谢谢！本周课程结束，谢谢！第2章分治策略(2)教学目的与要求1.掌握设计有效算法的分治策略。2.要求通过范例的学习掌握分治策略的技巧。第2章分治策略(2)教学目的与要求2.9线性时间选择给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。采用分治策略，利用在快速排序中使用到的RandomizedPartition算法，将序列随机分成两部分a[p…i]和a[i+1…r]，使得a[p…i]的每个元素都不大于a[i+1…r]的每个元素，而此时a[i]恰好为第i小元素，接着计算子数组a[p…i]的元素个数j，如果k≤j，则a[p…r]中第k小的数落在子数组a[p…i]中，如果k>j，则a[p…r]中第k小的数落在子数组a[i+1…r]中，此时要找的a[p…r]中第k小的元素是a[i+1…r]中第k-j小的元素。2.9线性时间选择给定线性序集中n个元素和一个整数k，1≤template<classType>intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p],t;//将<x的元素交换到左边区域，将>x的元素交换到右边区域

while(true){while(a[++i]<x);//从左到右找到第一个不小于a[p]的元素a[i]while(a[--j]>x);//从右到左找到第一个不大于a[p]的元素a[j]if(i>=j)break;t=a[i];a[i]=a[j];a[j]=t;//交换a[i]和a[j]}a[p]=a[j];a[j]=x;//交换a[p]和a[j]returnj;}template<classType>template<classType>intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Typet;t=a[i];a[i]=a[p];a[p]=t;returnPartition(a,p,r);}template<classType>template<classType>TypeRandomizedSelect(Typea[],intp,intr,intk){inti,j;if(p==r)returna[p];i=RandomizedPartition(a,p,r);j=i-p+1;//计算子数组a[p…i]的元素个数jif(k<=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);}template<classType>在最坏情况下（如在找最小元素时，总在最大元素处划分），算法RandomizedSelect需要(n2)计算时间，但该算法的平均性能较好。如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的ε倍(0<ε<1是某个正常数)，那么就可以在最坏情况下用O(n)时间完成选择任务。例如，若ε=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)≤T(9n/10)+O(n)。由此可得T(n)=O(n)。在最坏情况下（如在找最小元素时，总在最大元素处划分），算法R例如，将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。递归调用Select来找出这n/5个元素的中位数（也就是这些中位数的中位数），若n/5是偶数，则找它的两个中位数中较大的一个，然后以这个元素作为基准划分。例如，将n个输入元素划分成n/5个组，每组5个元素，只可设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-template<classType>intPartition(Type*a,intp,intr,Typex){inti,left=p,right=r;Type*b=newType[r-p+1];for(i=0;i<r-p+1;i++){b[i]=a[p+i];}for(i=p;i<=r;i++){if(b[i]<x){a[left++]=b[i];}elseif(b[i]>x){a[right--]=b[i];}}for(i=left;i<=right;i++)a[i]=x;delete[]b;returnleft;}template<classType>//找a[p..r]中第k小的元素返回template<classType>TypeSelect(Typea[],intp,intr,intk){inti,j;Typex,t;if(r-p<75){Sort(a,p,r);returna[p+k-1];}for(i=0;i<=(r-p-4)/5;i++){x=a[p+5*i]至a[p+5*i+4]的第3小元素;//将a[p+5*i...p+5*i+4]的第3小元素与a[p+i]交换位置

t=a[p+i];a[p+i]=x;x=t;}//找a[p..r]中第k小的元素返回/*每一组的中位数排在了a[p..p+(r-p-4)/5]的位置，现在找中位数的中位数x，r-p-4即上面所说的n-5*/x=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);/*将a[p…r]中不大于x的放在x左边，比x大的放在x右边，返回中位数的中位数x的下标i*/i=Partition(a,p,r,x),j=i-p+1;//求x左边有多少个元素，这些元素都比x小

if(k<=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);}/*每一组的中位数排在了a[p..p+(r-p-4)上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=εn，0<ε<1。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。设n=r-p+1，即n为输入数组的长度，算法的递归调用在n≥75时才执行，n<75的时候，算法Select所用的计算时间不超过常数C1，找到中位数的中位数x后，算法Select以x为基准调用函数Partition对数组a[p…r]进行划分，这需要O(n)时间，算法Select的for循环体执行了n/5次，每一次需要O(1)时间，因此执行for循环共需要O(n)时间。上述算法将每一组的大小定为5，并选取75作为是否作递归调用的设对n个元素数组调用Select算法需要T(n)时间，那么找中位数的中位数x至多用了T(n/5)次时间，既然按照基准x划分所得到的两个子数组分别至多3n/4个元素，所以不论对哪一个子数组调用Select算法都至多用了T(3n/4)的时间。因此，得到，T(n)=O(n)设对n个元素数组调用Select算法需要T(n)时间，那么找2.10最接近点对问题给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。最接近点对可能多于一对，简单起见，只考虑找其中的一对作为问题的解。如果我们将每一个点和其他n-1个点的距离算出来，找到最小距离的两个点，算法效率需要O(n2)的计算时间，效率太低。下面设计一个耗时O(nlog2n)的算法：2.10最接近点对问题给定平面上n个点，找出其中一对点，使为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。问题在于：能否在线性时间内找到p3、q3？为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则p3和q3两者与m的距离不超过d，即p3∈(m-d,m]，q3∈(m,m+d]。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。如果S的最接近点对是{p3,q3}，即|p3-q3|<d，则选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。问题在于：能否在线性时间内找到p、q？选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p,q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中。由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6×n/2=3n个候选者。考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)×(2d/3)的矩形。若矩形R中有多于6个S中的点，由鸽舍原理易知至少有一个(d/2)×(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)<d，与d的意义矛盾。证明：将矩形R的长为2d的边3等分，将它的长为d的边2等分，为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点，距离p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。下面给出用分治法求二维最接近点对算法：为了确切地知道要检查哪6个点，可将p和P2中所有S2的点投影boolCpair2(S,&d){n=|S|;if(n<2)returnfalse;1、m=S中各点x坐标下标的中位数;

构造S1和S2,S1={p∈S|x(p)<=x(m)},S2={p∈S|x(p)>x(m)}2、Cpair2(S1,d1);Cpair2(S2,d2);3、dm=min(d1,d2);4、令P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中的点依其y坐标值排序；并设X和Y是相应的已排好序的点列；第1步：O(n)第3步：O(1)第2步：2T(n/2)第4步：O(nlog2n)boolCpair2(S,&d)第1步：O(n)第3步：O第5步：O(n)5、通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；

6、d=min(dm,dl);returntrue;}若在每次执行第4步的时候进行排序，则最坏情况下第4步需要O(nlog2n)时间，这不符合要求，需要做一个技术处理。第6步：O(1)第5步：O(n)5、通过扫描X以及对于X中每个点检查Y中与使用预排序技术，在使用分治法之前，预先将S中n个点依其y坐标排好序，设排好序的点为P*，在执行分治法的第4步时，只要对P*进行1次线性扫描，即可抽取出我们所需要排好序的点列X和Y。然后，在第5步中再对X做一次线性扫描，即可求得dl。因此，第4步和第5步两遍扫描合在一起只要用O(n)时间。这样，经过预排序处理后算法后，算法Cpair2所需的计算时间T(n)满足递归方程即T(n)=O(nlog2n)。根据这个思想，写出的程序如下：使用预排序技术，在使用分治法之前，预先将S中n个点依其y坐标#include<iostream>#include<math.h>constintTOTAL=10000;usingnamespacestd;classPoint{public:doublegetx()const{returnx;}doublegety()const{returny;}doublesetx(doublexx){x=xx;returnx;}doublesety(doubleyy){y=yy;returny;}virtualbooloperator<=(Pointa){returntrue;}protected:doublex,y;};#include<iostream>//类PointX和PointY分别表示按照x坐标和y坐标排序的点classPointX:publicPoint{public:booloperator<=(Pointa)const{return(x<=a.getx());}friendinlinedoubledistance(constPointX&u,constPointX&v);};classPointY:publicPoint{public:booloperator<=(Pointa)const{return(y<=a.gety());}intsetp(intpp){p=pp;returnp;}intgetp(){returnp;}friendinlinedoubledistance(constPointY&u,constPointY&v);private:intp;//p表示以x坐标排序时，该点对应的下标(序号)};//类PointX和PointY分别表示按照x坐标和y坐标排inlinedoubledistance(constPointX&u,constPointX&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoulbledistance(constPointY&u,constPointY&v){doubledx=u.getx()-v.getx();doubledy=u.gety()-v.gety();returnsqrt(dx*dx+dy*dy);}inlinedoubledistance(constPtemplate<classType>voidMerge(TypeY[],TypeZ[],intl,intm,intr){//将有序的Z[l...m]与有序的Z[m+1...r]合并到Y[l...r]Type*a=&Z[l];Type*b=&Z[m+1];Type*c=&Y[l];intanum=m-l+1,ap=0;intbnum=r-m,bp=0;intcnum=r-l+1,cp=0;while(ap<anum&&bp<bnum){if(a[ap]<=b[bp])c[cp++]=a[ap++];elsec[cp++]=b[bp++];}while(ap<anum)c[cp++]=a[ap++];while(bp<bnum)c[cp++]=b[bp++];}template<classType>template<classType>voidMergeSort(Typea[],intn){intanum,bnum,i;Type*b,*c;if(n<=1)return;anum=n/2;b=a+anum;bnum=n-anum;MergeSort(a,anum);MergeSort(b,bnum);c=newType[n];Merge(c,a,0,anum-1,n-1);for(i=0;i<n;i++)a[i]=c[i];delete[]c;}template<classType>/*X存放输入的点集，X和Y分别表示按照x坐标和y坐标排序的点，l和r表示点集Y中成员p的范围*/voidclosest(PointXX[],PointYY[],PointYZ[],intl,intr,PointX&a,PointX&b,double&d){doubled1,d2,d3,dp;intf,g,m,i,j,k;doubledr;PointXar,br;if(r-l==1)//2点的情况

{a=X[l];b=X[r];d=distance(X[l],X[r]);return;}/*X存放输入的点集，X和Y分别表示按照x坐标和y坐标排序的if(r-l==2)//3点的情况

{d1=distance(X[l],X[l+1]);d2=distance(X[l+1],X[r]);d3=distance(X[l],X[r]);if(d1<=d2&&d1<=d3){a=X[l];b=X[l+1];d=d1;}elseif(d2<=d3){a=X[l+1];b=X[r];d=d2;}else{a=X[l];b=X[r];d=d3;}return;}if(r-l==2)//3点的情况m=(l+r)/2;//m为点集Y中成员p的范围的中位数

/*将已经按照y坐标排序的点集Y[l..r]，等分成两个子集复制到Z，其中Z[l..(l+r)/2]中的每个点的x坐标都小于Z[(l+r)/2+1..r]中的每个点的x坐标*/f=l;g=m+1;for(i=l;i<=r;i++){if(Y[i].getp()>m)Z[g++]=Y[i];elseZ[f++]=Y[i];}m=(l+r)/2;//m为点集Y中成//递归处理这两个子集(注意参数传递时Z与Y位置的变化)closest(X,Z,Y,l,m,a,b,d);closest(X,Z,Y,m+1,r,ar,br,dr);if(dr<d)//d表示这两个子集中各自找到的最近点对的距离较小者

{a=ar;b=br;d=dr;}Merge(Y,Z,l,m,r);//重构数组Y//将与分割线距离为d的点置如数组Z中

k=l;for(i=l;i<=r;i++){if(fabs(Y[m].getx()-Y[i].getx())<d)Z[k++]=Y[i];}//递归处理这两个子集(注意参数传递时Z与Y位置的变//搜索Z[l..k-1]，若其中存在两点的距离小于d，则更新dfor(i=l;i<k;i++){for(j=i+1;j<k&&Z[j].gety()-Z[i].gety()<d;j++){dp=distance(Z[i],Z[j]);if(dp<d){d=dp;a=X[Z[i].getp()];b=X[Z[j].getp()];}}}}//搜索Z[l..k-1]，若其中存在两点的距离小于boolCpair2(PointXX[],intn,PointX&a,PointX&b,double&d){inti;PointY*Z,*Y;if(n<2)returnfalse;MergeSort(X,n);//将各点按照x坐标排序

Y=newPointY[n];for(i=0;i<n;i++)//将数组X内的信息写入数组Y{Y[i].setp(i);//同一点在数组X中的坐标的下标

Y[i].setx(X[i].getx());Y[i].sety(X[i].gety());}MergeSort(Y,n);//将各点按照y坐标排序

Z=newPointY[n];closest(X,Y,Z,0,n-1,a,b,d);delete[]Y;delete[]Z;returntrue;}boolCpair2(PointXX[],intn,int