淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验1 递归与分治算法班级：学号：姓名：实验1 递归与分治算法实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。
（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。
实验内容设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
实验环境Turbo C 或VC++实验学时2学时，必做实验数据结构与算法#include<iostream>#include<Cmath>#include<algorithm>#define N 100using namespace std;struct point{int x,y;};bool cmpx(point a,point b){return a.x<b.x;}bool cmpy(point a,point b){return a.y>b.y;}int Sqrt(point a,point b)//两点间的距离的平方{int k;k=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);return k;}double min(double d1,double d2){if(d1<=d2)return d1;elsereturn d2;}bool different(point p[],int n,int start,int end){for(int i=start;i<end;i++){if(p[i].x==p[end].x&&p[i].y==p[end].y)return true;}return false;}int ClosestPoints1(point p[],int n,point & one,point & two)//求出两最近点的相关信息{int d=9999;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int temp=Sqrt(p[i],p[j]);if(temp<d){one=p[i];two=p[j];d=temp;}}return d;}int ClosestPoints2(point S[],int n) {if(n<2) return 10000;if(n==2){int d=Sqrt(S[0],S[1]);return d;}sort(S,S+n,cmpx);//按照X大小排序int m=S[n/2].x;int t=n/2;int i=0;point S1[5000],S2[5000];for(i=0;i<t;i++){S1[i]=S[i];}for(i=t;i<n;i++){S2[i-t]=S[i];}int d1=ClosestPoints2(S1,t);int d2=ClosestPoints2(S2,n-t);int d=min(d1,d2);point p1[N],p2[N];int j=0;int p1l=0,p2l=0;//对x坐标差值在2d之间的点进行归类，找到这些点for(i=0;i<t;i++){if(abs(S1[i].x-m)<d){p1[p1l]=S1[i];p1l++;}}for(i=0;i<n-t;i++){if(abs(S2[i].x-m)<d){p2[p2l]=S2[i];p2l++;}}//对两个区间内的点沿Y坐标轴进行排序sort(p1,p1+p1l,cmpy);sort(p2,p2+p2l,cmpy);int md=9999;for(i=0;i<p1l;i++){for(j=0;fabs(p2[j].y-p1[i].y)<d;j++){int pd=Sqrt(p1[i],p2[j]);md=min(pd,md);}}return min(d,md);}void main(){point p[N],a,b;int n=20;int d;cout<<"请输入点的个数:";cin>>n;cout<<"请输入各点（中间用空格）:"<<endl;for(int i=0;i<n;i++){cout<<"第"<<i+1<<"点:";cin>>p[i].x>>p[i].y;}d=ClosestPoints1(p,n,a,b);cout<<"\n蛮力法求最近点对："<<endl;cout<<"最短距离为:"<<sqrt(d)<<endl;cout<<"两个点分别为:("<<a.x<<","<<a.y<<") , ("<<b.x<<","<<b.y<<")"<<endl;d=ClosestPoints2(p,n);cout<<"\n分治法求最近点对："<<endl;cout<<"最短距离为:"<<sqrt(d)<<endl;cout<<"两个点分别为:("<<a.x<<","<<a.y<<") , ("<<b.x<<","<<b.y<<")"<<endl; }核心源代码蛮力法核心源代码：int ClosestPoints1(point p[],int n,point & one,point & two)//蛮力法求出两最近点的相关信息{int d=9999;for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){int temp=Sqrt(p[i],p[j]);if(temp<d){one=p[i];two=p[j];d=temp;}}return d;}分治法核心源代码：int ClosestPoints2(point S[],int n){if(n<2) return 10000;if(n==2){int d=Sqrt(S[0],S[1]);return d;}sort(S,S+n,cmpx);//按照X大小排序int m=S[n/2].x;int t=n/2;int i=0;point S1[5000],S2[5000];for(i=0;i<t;i++){S1[i]=S[i];}for(i=t;i<n;i++){S2[i-t]=S[i];}int d1=ClosestPoints2(S1,t);int d2=ClosestPoints2(S2,n-t);int d=min(d1,d2);point p1[N],p2[N];int j=0;int p1l=0,p2l=0;//对x坐标差值在2d之间的点进行归类，找到这些点for(i=0;i<t;i++){if(abs(S1[i].x-m)<d){p1[p1l]=S1[i];p1l++;}}for(i=0;i<n-t;i++){if(abs(S2[i].x-m)<d){p2[p2l]=S2[i];p2l++;}}//对两个区间内的点沿Y坐标轴进行排序sort(p1,p1+p1l,cmpy);sort(p2,p2+p2l,cmpy);int md=9999;for(i=0;i<p1l;i++){for(j=0;fabs(p2[j].y-p1[i].y)<d;j++){int pd=Sqrt(p1[i],p2[j]);md=min(pd,md);}}return min(d,md);}实验结果实验体会通过这次实验，我更加了解了蛮力法与分治法的本质区别，当我们在面对庞大数据时，分治法能更高效的完成任务，分治法将一个复杂的问题简单抽象地分成若干个子问题，很轻而易举的利用递归就完成了，本次实验存在的问题是：对最近点对相关的算法细节不是很清晰。
