用分治算法解平面最接近点对问题.doc

《用分治算法解平面最接近点对问题.doc》由会员分享，可在线阅读，更多相关《用分治算法解平面最接近点对问题.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一. 用分治算法解平面最接近点对问题关于最接近点对问题:给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。2. 程序详细介绍(各模块的功能等) 本程序主要包括两个类:类Point与类Ppoint.其中类PointPpoint为该程序的主要实现模块,该类中有输入点对的函数shuru,对所输入的点对按X轴排序的函数sort,求各点对的距离的函数xiao等.假设S中的点为平面上的点，它们都有2个坐标值x与y。为了将平面上点集S线性分割为大小大致相等的2个子集S1与S2，我们选取一垂直线l方程：x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1=

2、pS|pxm与S2=pS|pxm。从而使S1与S2分别位于直线l的左侧与右侧，且S=S1S2 。由于m是S中各点x坐标值的中位数，因此S1与S2中的点数大致相等。递归地在S1与S2上解最接近点对问题，我们分别得到S1与S2中的最小距离1与2.此即为该程序的大致算法.3. 程序构造流程图 该程序的流程图如下所示4. 调试与测试：调试方法，测试结果包括输入数据与输出结果的分析与讨论运行该程序时,屏幕上会出现一个界面,首先该界面会提示输入要处理的点对个数,输入点对个数后从键盘输入数字0即可显示出处理后的各个结果,会出现如下结果:第 11 页5.程序代码(源程序)#include#include#in

3、cludeusing namespace std;int i,j,k,d,m,n;double p2,q,s,r,t;class Point /创立一个点类/public: double x; double y; double getx()return x; double gety()return y;friend class Ppoint; class Ppointint sum;double juli1010;double min11; /min10用来存放每组中最短的距离/double mini11; /mini10用来存放每组中距离最短的点对中的第一个点/double minj11;

4、/minj10用来存放每组中距离最短的点对中的第二个点/Point p100;Point p1;public:void shuru()cout请输入要处理的点的个数sum;for(i=0;isum;i+) cout请输入点对 pi.x;cinpi.y; coutpi.x,pi.yendl;void sort() cout以下是按x轴上由小到大排序后的点对endl;for(i=0;isum-1;i+)for(j=i+1;jpj.x)p1=pi;pi=pj;pj=p1;for(i=0;isum;i+)coutpi.x,pi.yendl;void xiao() cout以下是对每个模块中的点求距离e

5、ndl; for(k=0;ksum/10;k+) cout按任意键继续i; cout以下是第k个模块中的距离endl;for(i=1;i10;i+)for(j=0;ji;j+)r=abs(pk*10+i.x-pk*10+j.x);t=abs(pk*10+i.y-pk*10+j.y);juliij=sqrt(r*r+t*t);coutjuliijt;coutendl; mink=julik0,minik=10*k+1,minjk=10*k;for(i=1;i10;i+)coutn第i行以前的最小值为minkendl;for(j=0;ji;j+)if(juliijmink)mink=juliij;

6、minik=10*k+i;minjk=10*k+j;coutn这是第k个模块中的结果endl;coutn距离最小值为minkendl;coutn距离最小值的第一个点为minikendl; /cout距离最小值的第一个点为minikendl;/ if(sum%10!=0) k=sum/10; cout输入0显示结果i; for(i=1;isum%10;i+) for(j=0;ji;j+)m=abs(pk*10+i.x-pk*10+j.x);n=abs(pk*10+i.y-pk*10+j.y);juliij=sqrt(m*m+n*n);coutjuliij;coutt;coutendl; mink

7、=juli10,minik=10*k+1,minjk=10*k; for(i=1;isum%10;i+) coutn第i行以前的最小值为minkendl; for(j=0;ji;j+) if(juliijmink) mink=juliij; minik=10*k+i; minjk=10*k+j; coutn这是第k个模块中的结果endl; coutn距离最小值为minkendl; coutn距离最小值的第一个点为minikendl; /cout距离最小值的第一个点为minikendl; void realmin()coutn几个模块中的最小值是：min10endl;for(i=0,min10=

8、min0,mini10=mini0,minj10=minj0;i=sum/10;i+)if(minimin10)min10=mini;mini10=minii;minj10=minji;void bianjiemin()coutn 包括边界的最小值是：min10endl;for(i=0;i=0;k-)if(p(i+1)*10.x-pi*10+k.xmin10)for(q=0;q10;q+) if(p(i+1)*10+m.x-p(i+1)*10.xsqrt(m*m+n*n) min10=sqrt(m*m+n*n); mini10=i*10+k; minj10=(i+1)*10+q;elsebre

9、ak;elsebreak;void shuchu()i=mini10;j=minj10;p2= abs(pi.x-pj.x)*abs(pi.x-pj.x) ;q= abs(pi.x-pj.x)*abs(pi.x-pj.x) ;s=sqrt(p2+q);coutn最接近点对为pi(pi.x,pi.y) pj(pj.x,pj.y)endl;coutn最短距离为min10;coutn最短距离为s;int main()Ppoint x;x.shuru();x.sort();x.xiao();x.realmin();x.bianjiemin();x.shuchu(); return 0;二.设计体会通过

10、这次的课程设计，我对C+程序语言有了更进一步的认识。我运用C+程序语言进展编程的能力有一定程度的提高,也掌握了C+程序语言程序设计过程、方法及实现，为以后相关的课程的学习打下良好根底；培养了我分析、解决问题的能力；也提高了我课程设计论文的写作能力。此次课程设计也让我发现了自己有许多的缺乏之处.由于平时的编写程序的时机也不是很多,再加上自己对C+程序语言掌握的不是很全面,使我设计程序的过程中遇到了一些难题.最后还得求助于书本才得以将问题解决.所以,我认为自己的实际编写程序能力还有待加强.在课程设计的过程当中，程序的设计中运用到了C+程序语言中的类设计与实现、学生选修课程系统设计与用分治算法解平面最接近点对问题这两个程序,经过查阅各种书籍以及上网查询,我根本能够实现教师所要求实现的功能.总之,通过这次C+程序语言的课程设计,我不但在C+的理论知识方面有所提高,而且在实际应用方面也有一定的提高!以后我也会更加努力的学习有关C+以及相关的知识,以使自己更加理解C+程序语言并会运用其编出更好的程序!三、参考文献钱能 清华大学出版社陈志泊 王春玲 人民邮电出版 网站: