算法分析与设计作业

页1最接近点对问题问题此问题分为一维，二维，三维的情况1.一维:给定直线上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，这个问题比较简单，是引出二维解法的一个引子，因为一维的直线上的点，相邻点的距离肯定小于相隔的点的距离，只需要考虑相邻点即可。2.二维：给定平面上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，这是我们这一问题的重点3.三维：给定空间上n个点，找其中一对点，使得在n个点组成的所有点对中，该点对间的距离最小，此问题是二维的解法的复杂化，具体可以在飞机航线等问题上运用，但在此不多做介绍。基本思想由于该问题的基本解法是去考察每个点和其他所有点的距离。因此它的时间复杂度是2()On,这样做的效率太低，我们就要去寻找一个更高效的办法：分治法。1.因二维的情况太过复杂，先考虑一维的情况中，可以用分治法对其进行分部计算：把直线分成两部分,1s2s,分别求出其最接近点的距离1d2d。但分割开的地方的两点距离可能小于这两个值，这三个值进行比较之后，得到最后结果。2.鉴于此，二维的也可以用此方法进行计算：把待计算的点s分成两部分1s2s，分别求出其最接近点的距离1d2d。但1d2d最小的未必是s中的最小距离d，它有可能是1s中的一个点和2s中的一个点组成的最接近点对。所以还要考虑1s中的所有点到2s中的每一个点的距离，一一比较之后得出一个最小值，再和1d2d比较，这就得出了最后结果。3.接下来是具体算法实现的步骤：1.把待计算的点s分成两部分1s2s:重要的如何去划分，这里采用在二维平面上的中线（用横坐标的最小值加上最大值的平均数）来划分。2.分别求出其最接近点的距离1d2d:这可以用一个递归来完成。3.计算1s中的所有点到2s中的每一个点的距离：这个问题是此问题的关键。页2首先要考虑的是，1s中的点，是不是每一个都有可能和2s中的某个点组成最接近点呢。答案是未必。假设中线的横坐标是x.而1d2d中较小的值为d。则1s中距离中线大于d的点，它和2s中任意点的距离必定大于d。所以，只用考虑符合（X-1xd）的点即可。其中1x为点的横坐标。然后要考虑的是，对于每个中距离中线小于d的点，是不是2s中的每个点都有可能和其组成最接近点呢？答案也是未必。假设一个1s中距离中线小于d的点为1n，它的纵坐标为y，那么2s中距离1n小于于d的点，它的纵坐标和y之差的绝对值必然小于d。即一定在下图阴影部分之中。在下图中，我们观察到：将阴影部分分成6块，每块顶多有一个点。否则，任意一块中的两个点，他们的距离一定小于等于2212()()23dd，即小于d，这和d的定义矛盾。至此，我们得到结论，不是每个2s中的点都需要计算的。我们只需要计算1s中距离中线x不超过d的点和与此点对应的符合阴影部分的2s中的点。4.在第三步中的所有距离中得到一个最小距离3d，和1d2d相比之后，得出最终答案。4.现在要考虑的是这个算法和基本算法的2()On的时间复杂度相比，它有优越性么?假设问题的规模为n，在这个算法中，它的分割步骤和合并步骤总共耗时()On。因此，页3算法耗费的计算时间为()Tn满足递归方程(1)4()2(/2)()4OnTnTnOnn解此方程得T(n)=(log)Onn。源代码因课本上的关键代码是用C++编写的。本人不善于用C++，故进行修改并用C实现。#includestdio.h#includemath.h#defineMAX50intpoint1,point2,x[MAX];floatpoint[MAX][2];floatdistance(inta,intb){//两点间距离floatdx,dy;dx=point[a][0]-point[b][0];dy=point[a][1]-point[b][1];return(sqrt(dx*dx+dy*dy));}voidrecord(inta,intb){//用point1,point2来记录最接近点的编号。if(point1==-1){point1=a;point2=b;}elseif(distance(a,b)distance(point1,point2)){point1=a;point2=b;}}floatclosest(intm,intn){//分治法求最接近距离floatd,d1,d2,mid;inti,j,k;if((n-m)==1){d=distance(x[m],x[n]);record(x[m],x[n]);returnd;}if((n-m)==2){d=distance(x[m],x[m+1]);d1=distance(x[m],x[n]);d2=distance(x[m+1],x[n]);if(d=d1&&d=d2){record(x[m],x[m+1]);returnd;}if(d1=d&&d1=d2){record(x[m],x[n]);returnd1;}if(d2=d&&d2=d1){record(x[m+1],x[n]);returnd2;}}//多于点的情况用分治法k=(m+n)/2;d1=closest(m,k);d2=closest(k+1,n);if(d1d2)d=d1;elsed=d2;mid=(point[k][0]+point[k+1][0])/2;for(i=m;i=k;i++){页4if(point[x[i]][0]mid-d)continue;//左边部分离中线距离大于d的被排除for(j=n;j=k+1;j--){if(point[x[j]][0]mid+d)continue;//右边部分离中线距离大于d的被排除if(abs(point[x[j]][1]-point[x[i]][1])d)continue;//右边部分纵坐标离左边所选点纵坐标的距离大于d的被排除d1=distance(x[i],x[j]);if(d1d){record(x[i],x[j]);d=d1;}}}returnd;}voidarrange(intn){//对x[]进行赋值，赋值为以点的横坐标从小到大排列的点的序号floatx1[MAX],tem1;inttem;inti,j;for(i=0;in;i++)x1[i]=point[i][0];for(i=0;in;i++)x[i]=i;for(i=0;in-1;i++){for(j=0;jn-1-i;j++){if(x1[j]x1[j+1]){tem1=x1[j];x1[j]=x1[j+1];x1[j+1]=tem1;tem=x[j];x[j]=x[j+1];x[j+1]=tem;}}}}intmain(void){floatx1[MAX],tem1;inti,j,n,tem;floata,b,d;point1=-1;//录入点的数据*****printf(请输入点的个数（为大于等于的自然数）：);scanf(%d,&n);for(i=0;in;i++){printf(请输入点的横坐标和纵坐标，中间用空格分开：);scanf(%f%f,&a,&b);point[i][0]=a;point[i][1]=b;}//******************arrange(n);d=closest(0,n-1);printf(最接近点对为第%d个点和第%d个点,point1+1,point2+1);printf(其距离为%.5f\n,d);system(pause);return0;}页5测试数据及运行结果为验证程序的正确性，特寻找几组独特的数据进行检测N测试数据结果11,1无结果21,12,21,21.4142151,11,21000,10001050,5050,10501,21.000040,00,84,44,-41,45.65685观察以上测试，基本符合题意要求。但此程序仅得到一个最接近点对，若出现相等的情况，只给出其中一个。调试心得和源程序源程序在源代码部分已经给出。在调试过程中，我发现对于数组地址的传递比较容易出错，鉴于时间问题，只好采取设置全局变量的办法解决了问题。另：本程序几乎被我重新编写，和书中的代码有巨大的差异，但算法思想是一致的。页6算法分析题：1.1求下列函数的渐近表达式：()Tn=2310nn的渐近表达式()Tn=23n.()Tn=2/102nn的渐近表达式为()Tn=2n.()Tn=21+1/n的渐近表达式为()Tn=21.()Tn=3logn的渐近表达式为()Tn=3logn.()Tn=10log3n的渐近表达式为()Tn=log310n.1.2试论(1)O,(2)O的区别。因为:(1)O+(1)O=(11)O=(2)O(1)O+(1)O==(1)O.所以，(1)O，(2)O应该是相等的。1.3按照渐近阶从低到高的顺序排列以下表达式：24n,logn,3n,20n,2,2/3n.又!n应该排在哪一位？从低到高：2，logn，20n，2/3n，24n，3n，!n2.2下面的7个算法与本章中的二分搜索算法BinarySearch略有不同。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明1.while(left=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(xa[middle])left=middle;elseright=middle;}return-1;不正确，当循环进行到只有两个元素的时候，intmiddle=(left+right)/2,就等于那个较小的元素位置。这时如果X大于较小的元素的时候，即if(xa[middle])left=middle;就造成了下次循环还是两个元素，这就形成了死循环。当循环进行只有一个元素的时候，若X不等于这个元素，无论是大还是小，left，middle，right的值都一样，都会继续进行循环，这也是死循环。页72.while(leftright-1){intmiddle=(left+right)/2;if(xa[middle])right=middle;elseleft=middle;}if(x==a[left])returnleft;return-1;不正确，当x等于最后一个最大的元素的时候，循环中的if(xa[middle])一直不执行。一直执行left=middle.因为循环的条件是while(leftright-1),即三个或三个以上时循环，又有一定会出现三个元素的时刻T(四个元素的时候，middle=(left+right)/2为第二个元素,left=middle,则下一步是三个元素)，则此次循环执行完毕时，只有最后两个元素，跳出循环，最后判断x==a[left],误认为找不到X的匹配，出错。*******************************************************************************3.while(left+1!=right){intmiddle=(left+right)/2;if(x=a[middle])left=middle;elseright=middle;}if(x==a[left])returnleft;return-1;不正确，当x=最大元素的时候，因为循环的条件是left+1!=right,循环到最大的两个元素的时候跳出，但接下来只拿这两个元素的左元素和X做比较，做出了误判。*******************************************************************************4.if(n0&&x=a[0]){intleft=0,right=n-1;while(leftright){intmiddle=(left+right)/2;if(xa[middl