最接近点对 分治法.docxVIP

实验1 递归与分治算法实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。实验内容设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。实验环境 Turbo C 或VC++实验结果：随机生成：手动输入：源代码：//二维最邻近点对问题#include stdafx.h#includetime.h#includeiostream #includecmath#includestdlib.husing namespace std;const int M=50;//用类PointX和PointY表示依x坐标和y坐标排好序的点class PointX {public: int operator=(PointX a)const{ return (x=a.x); }int ID; //点编号float x,y; //点坐标 };class PointY { public: int operator=(PointY a)const{ return(y=a.y); }int p; //同一点在数组x中的坐标 float x,y; //点坐标};float Random();template class Typefloat dis(const Typeu,const Typev); bool Cpair2(PointX X[], int n,PointX a,PointX b, float d);void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX a,PointX b,float d);template typename Type void Copy(Type a[],Type b[], int left,int right);template class Typevoid Merge(Type c[],Type d[],int l,int m,int r);template class Typevoid MergeSort(Type a[],Type b[],int left,int right);int main(){ srand((unsigned)time(NULL));int length;int chose;cout请选择随机生成(1)或手动输入(2)：endl;cinchose;cout请输入点对数：;cinlength;PointX X[M];if (chose==2){for(int i=0;ilength;i++){coutendl请输入点对：endl;X[i].ID=i;cinX[i].x;cinX[i].y;cout(X[i].x,X[i].y) ;}}else if(chose==1){cout随机生成的二维点对为：endl; for(int i=0;ilength;i++){X[i].ID=i;X[i].x=Random();X[i].y=Random();cout(X[i].x,X[i].y) ;}}PointX a; PointX b; float d;Cpair2(X,length,a,b,d); coutendl;cout最邻近点对为：(a.x,a.y)和(b.x,b.y) endl;cout最邻近距离为： dendl;system(pause);return 0;}float Random(){float result=rand()%10000;return result*0.01;}//平面上任意两点u和v之间的距离可计算如下template class Typeinline float dis(const Type u,const Type v){float dx=u.x-v.x;float dy=u.y-v.y; return sqrt(dx*dx+dy*dy); }bool Cpair2(PointX X[], int n,PointX a,PointX b,float d){if(n2) return false;PointX* tmpX = new PointX[n];MergeSort(X,tmpX,0,n-1);PointY* Y=new PointY[n]; for(int i=0;in;i++) //将数组X中的点复制到数组Y中{ Y[i].p=i;Y[i].x=X[i].x;Y[i].y=X[i].y;} PointY* t