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

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.23M 资料格式：doc 举报版权申诉

jiangxin20051986-729469-4744302542929854402.doc.pdf-第1页.png

第1页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第2页.png

第2页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第3页.png

第3页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第4页.png

第4页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第5页.png

第5页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第6页.png

第6页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第7页.png

第7页 / 共9页

jiangxin20051986-729469-4744302542929854402.doc.pdf-第8页.png

第8页 / 共9页

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

1.题目

2. 程序详细介绍(各模块的功能等)

3. 程序结构（流程图）

5.程序代码(源程序)

二.设计体会

三、参考文献

一. 用分治算法解平面最接近点对问题 1.题目关于最接近点对问题: 给定平面上 n 个点，找出其中一对点，使得在 n 个点所构成的所有点对中，该点对的距离最小。 2. 程序详细介绍(各模块的功能等) 本程序主要包括两个类:类 Point 和类 Ppoint.其中类 Point 为处理一些的基本数据传递等.类 Ppoint 为该程序的主要实现模块,该类中有输入点对的函数 shuru,对所输入的点对按 X 轴排序的函数 sort,求各点对的距离的函数 xiao 等. 假设 S 中的点为平面上的点，它们都有 2 个坐标值 x 和 y。为了将平面上点集 S 线性分割为大小大致相等的 2 个子集 S1 和 S2，我们选取一垂直线 l（方程：x=m）来作为分割直线。其中 m 为 S 中各点 x 坐标的中位数。由此将 S 分割为 S1={p∈S|px≤m}和 S2={p∈S|px>m}。从而使 S1 和 S2 分别位于直线 l 的左侧和右侧，且 S=S1∪S2 。由于 m 是 S 中各点 x 坐标值的中位数，因此 S1 和 S2 中的点数大致相等。递归地在 S1 和 S2 上解最接近点对问题，我们分别得到 S1 和 S2 中的最小距离δ1 和δ2.此即为该程序的大致算法. 3. 程序结构（流程图）该程序的流程图如下所示

4. 调试与测试：调试方法，测试结果（包括输入数据和输出结果）的分析与讨论运行该程序时,屏幕上会出现一个界面,首先该界面会提示输入要处理的点对个数,输入点对个数后从键盘输入数字 0 即可显示出处理后的各个结果,会出现如下结果:

5.程序代码(源程序) #include #include #include using 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; class Ppoint; } friend }; class Ppoint { int sum; double juli[10][10]; double min[11]; double mini[11]; 第一个点// double minj[11]; 第二个点// Point p[100]; Point p1; public: void shuru() { //min[10]用来存放每组中最短的距离// //mini[10]用来存放每组中距离最短的点对中的 //minj[10]用来存放每组中距离最短的点对中的 cout<<"请输入要处理的点的个数"<>sum; for(i=0;i

cin>>p[i].x; cin>>p[i].y; cout<p[j].x) { p1=p[i]; p[i]=p[j]; p[j]=p1; } } } for(i=0;i>i; cout<<"以下是第"<

min[k]=juli[k][0],mini[k]=10*k+1,minj[k]=10*k; for(i=1;i<10;i++) { cout<<"\n"<<"第"<>i; for(i=1;i

if(juli[i][j]=0;k--) if(p[(i+1)*10].x-p[i*10+k].xsqrt(m*m+n*n)) {

min[10]=sqrt(m*m+n*n); mini[10]=i*10+k; minj[10]=(i+1)*10+q; } } else break; } else break; } } void shuchu() { i=mini[10]; j=minj[10]; p2= abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x) ; q= abs(p[i].x-p[j].x)*abs(p[i].x-p[j].x) ; s=sqrt(p2+q); cout<<"\n"<<" 最接近点对为 "<<"p["<

分享到：

赞收藏

资料库

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

相关推荐

开发技术

热门标签

最新资料