数据结构与算法课程设计报告--最近点对问题的解决算法.docx

上传人:p** 文档编号:674117 上传时间:2024-01-08 格式:DOCX 页数:8 大小:32.45KB
下载 相关 举报
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第1页
第1页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第2页
第2页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第3页
第3页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第4页
第4页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第5页
第5页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第6页
第6页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第7页
第7页 / 共8页
数据结构与算法课程设计报告--最近点对问题的解决算法.docx_第8页
第8页 / 共8页
亲,该文档总共8页,全部预览完了,如果喜欢就下载吧!
资源描述

《数据结构与算法课程设计报告--最近点对问题的解决算法.docx》由会员分享,可在线阅读,更多相关《数据结构与算法课程设计报告--最近点对问题的解决算法.docx(8页珍藏版)》请在第壹文秘上搜索。

1、课程设计报告课程名称:数据结构与算法项目名称:最近点对问题的解决算法正文部分1)简介题目原文:最近点对问题在一片金属板上钻多个大小一样的洞,如果洞太近(洞中心距离Dcm),金属可能会断。现假设在金属板上,钻了n个洞,请编程判断该金属板是否会断。该问题的抽象模型:在一个二维平面中有有限的点,求其中距离最近的两点的距离。2)实现(算法,流程,数据结构,复杂度分析等的描述)算法:采用分治法。首先划分集合S为SL和SR,使得SL中的每一个点位于SR中每一个点的左边,并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题,得到DL和DR,分别表示SL和SR中的最近点对的距离。令d=min(DL,D

2、R)o如果S中的最近点对(PLP2)。PLP2两点一个在SL和一个在SR中,那么Pl和P2一定在以L为中心的间隙内,以L-d和L+d为界,如下图所示:LSl SR 如果在SL中的点P和在SR中的点Q成为最近点对,那么P和Q的距离必定小于do因此对间隙中的每一个点,在合并步骤中,只需要检验ypd和yp-d内的点即可。流程:步骤1:根据点的y值和X值对S中的点排序。步骤2:找出中线L将S划分为SL和SR步骤3:将步骤2递归的应用解决SL和SR的最近点对问题,并令d=min(dL,dR)o步骤4:将L-d-L+d内的点以y值排序,对于每一个点(XLyI)找出y值在yl-d-yld内的所有点,计算距离

3、为do如果Cr小于d,令d=d,最后的d值就是答案。数据结构:顺序存储。算法复杂度分析:STLisort使用了时间复杂度为O(Mgn)的排序算法,对于一个数据规模为n的最近点对问题,定义它的复杂度为T(n)o算法的第一步将问题分解成两个子问题,分解这部分的复杂读是2T(n)第2步线性扫描,上界为0(n)。第3步对于P中的每一个点,其比较的时间复杂度是常数。由于需要扫描所有P点,上界为0(n)。原问题时间复杂度T(n)=2T(n)+0(n)使用算法导论的主定理可以得出总的上界为O(nlgn)易知空间复杂度为0(n)3)结果展示(效果,功能,以及其他相关图片,数据等)可自行设置安全距离,设置打孔数

4、量请输入打孔数量?至少需要两个点.至少需要两个点.实际运行效果,附穷举法验证:请设定安全距离.4.567请输入打孔数量?1017.3555.08安全.0.3312.98615.03317.000.80:5安全.55安全.7.98.8安全.77危险,最近两点的距离为2.01246,少于4.567使用穷举法验证最小距离为2.012464)问题分析(碰到什么问题,如何解决)在类中定义的比较方法需要定义为静态,所以将数据存储容器作为全局变量定义。5)程序代码清单(代码应含有恰当的注释语句)/*源代码*/#include#include#include#includeusingnamespacestd;

5、classPointdoublex,y;点对象的结构public:Point(doublex,doubley)(this-x=x;this-y=y;)doubledistjo(Pointp)returnsqrt(-p.x)*(x-p.x)+(y-p.y)*(y-p.y);)friendclassPlane:;vectorcontainer:点集的容器,使用STLVeCtor存储classPlanePub附平面类的声明voidadd(Pointp)(container.psh-back(p);)staticboolcmpXY(constPoint&a,constPointsb)(if(a.xI=

6、b.x)returna.b.x;returna.yb.y;若横坐标不同则比较横坐标,否则比较纵坐标staticboolcmpY(inta,intb)以纵坐标为主的比较函数returncontainera.yntainerb.y;)doubledist(inti,intj)Zi与第j个点的距离(已排序)returncontaineri.distJo(containerO);doublemin(doublex,doubley)取最小值方法returnxy?x:y;)voidsort()使用STLalgorithm提供的sort方法对所有点进行XY排序std:sort(container.begin

7、(),container.end(),cmpXY);)doublegetClosest(intleft,intright)主要方法,递归调用int*tmp=newint10000;用以存放与左右两边边界距离为d的所有点doubled=9999999;if(left=right)returnd;if(left+1=right)returndist(left,right);intmid=(left+right)2;doubledleft=getClosest(left,mid);取左区域最小距离doubledright=getClosest(mid+i,right);取右区域最小距离d=min(d

8、left,dright);从两者中取最小值intk=0;for(inti=left;i=right;i+)if(fabs(containermid.x-container(i.x)=d)tmpk+=i;取边界两侧距边界小于d的点std:sort(tmp,tmp+k,cmpY);for(inti=0;ik;i+)for(intj=i+1;jk&containertmpj.y-containertmpi.yt)d=t;W在边界点中按y轴方向的距离比较;)deletetmp;returnd;)doublebrute_getClosest()穷举法,用以验证结果的准确性intlen=container

9、.size();doubled=99999;for(inti=0;iIen;i+)for(intj=i+1;jIen;j+)if(dist(i,j)d)d=dist(i,j);)returnd;)-Plane()(container.clear(););intmain()(doublesafe_dist:cout,Pleaseinputthesafedistancebetweeneachtwopoints.n;cinsafe_dist;intn;coutn;while(n=1)coutn;)Planepn:for(inti=0;ixy;Pointp(x,y);pn.add(p);pnsort(

10、);doubledist=p.getClosest(0,i);if(dist=1)coutWarning,theminimumdistanceofpointsis,dist,lessthansafe_distendl;Cout,Verifyingwithbrutealgorithm,pn.brute-getClosest()endl;break;)elsecout,Thenewholeissafe.n;)*代码结束*/6)心得与体会体会:第一点:通过这个作业,我们充分认识和了解了用分治法解决实际问题的优点:分一将问题分解为规模更小的子问题;治一将这些规模更小的子问题逐个击破;合一将已解决的子问

11、题合并,最终得出母问题的解;第二点:两个人分工合作也体现了程序设计中的面向对象,模块化设计的思想。7)任务分工及所完成的状况分工:李逸飞负责:步骤1(根据点的y值和X值对S中的点排序。)步骤2(找出中线L将S划分为SL和SR)步骤3(将步骤2递归的应用解决SL和SR的最近点对问题,并令d=min(dLzdR)供同完成)梁志煌负责:步骤3(将步骤2递归的应用解决SL和SR的最近点对问题,并令d=min(dLzdR)(共同完成)步骤4(将L-d-L+d内的点以y值排序,对于每一个点(XLyI)找出y值在yl-d-yld内的所有点,计算距离为do如果Cr小于d,令d=d,最后的d值就是答案。)8)参考文献1”最近点对问题,NoAlGo,http:/noalgo.info/793.html9)诚信承诺(注此项不可分开为两页!)个人得分权重分配表排序姓名学号项目个人权重150%250%我组成员总共2名,权重总和为:100%本组成员郑重承诺在课程设计完成过程中不发生任何不诚信现象,一切不诚信所导致的后果均由本组成员承担。同时我组成员同意此课程设计的个人得分权重分配表。签名(手签全部成员):

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!