计算机算法实验报告.docVIP

实验一 最接近点对问题 实验目的 为进一步学习分治策略的基本思想，本次实验将通过求最接近点对问题来加深我们对分治策略的认识。 实验问题描述 给定平面上N个点，找出其中的一对点，使得在n 个点组成的所有点对中，该点对间的距离最小。 设计思路及步骤 将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归地求其最接近的点对。 先考虑一维的情形：设计一个求一维点集S的最接近点对的算法 Bool Cpairl(S,d) { N=|S|; if(n2) {d=无穷大;return falSe;} m=S中各点坐标的中位数; 构造S1和S2; //S1={x∈S|x=m},S2={x∈S|xm} Cpairl(S1,d1); Cpairl(S2,d2); p=max(S1); q=max(S2); D=min(d1,d2,q-p); return true; } 由此推广到二维的情形： 若矩形R中有多于6个S中的点，则由鸽舍原理易知，至少有一个（d/2）*（2d/3）的小矩形中有2个以上S中的点。设u,v是位于同一小矩形中的2个点，则 (x(u)-x(v))2+(y(u)-y(v))2=(d/2)2+(2d/3)2=25d2/36 因此 distance（u,v）=5d/6d,与d的意义相矛盾。 算法实现代码 //2d10-2?二维最邻近点对问题??? #includetime.h??? #includeiostream???? #includecmath??? using?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?Type?? float?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?Type?? void?Merge(Type?c[],Type?d[],int?l,int?m,int?r);?? template?class?Type?? void?MergeSort(Type?a[],Type?b[],int?left,int?right);?? int?main()?? {??? srand((unsigned)time(NULL));?? int?length;?? cout请输入点对数：;?? cinlength;?? PointX?X[M];?? 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,b;??? float?d;?? Cpair2(X,length,a,b,d);??? coutendl;?? cout最邻近点对为：(a.x,a.y)和(b.x,b.y)?endl;?? cout最邻近距离为：?dendl;?? return?0;?? }?? float?Random()?? {?? float?result=rand()%10000;?? return?result*0.01;?? }?? //平面上任意两点u和v之间的距离可计算如下??? templat