欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    用分治算法解平面最接近点对问题(共9页).doc

    • 资源ID:14148456       资源大小:215.50KB        全文页数:9页
    • 资源格式: DOC        下载积分:20金币
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录   QQ登录  
    二维码
    微信扫一扫登录
    下载资源需要20金币
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    用分治算法解平面最接近点对问题(共9页).doc

    精选优质文档-倾情为你奉上一. 用分治算法解平面最接近点对问题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=pS|pxm和S2=pS|px>m。从而使S1和S2分别位于直线l的左侧和右侧,且S=S1S2 。由于m是S中各点x坐标值的中位数,因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题,我们分别得到S1和S2中的最小距离1和2.此即为该程序的大致算法.3. 程序结构(流程图) 该程序的流程图如下所示4. 调试与测试:调试方法,测试结果(包括输入数据和输出结果)的分析与讨论运行该程序时,屏幕上会出现一个界面,首先该界面会提示输入要处理的点对个数,输入点对个数后从键盘输入数字0即可显示出处理后的各个结果,会出现如下结果:专心-专注-专业5.程序代码(源程序)#include<iostream>#include<cmath>#include<fstream>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; friend class Ppoint; ;class Ppointint sum;double juli1010;double min11; /min10用来存放每组中最短的距离/double mini11; /mini10用来存放每组中距离最短的点对中的第一个点/double minj11; /minj10用来存放每组中距离最短的点对中的第二个点/Point p100;Point p1;public:void shuru()cout<<"请输入要处理的点的个数"<<endl;cin>>sum;for(i=0;i<sum;i+) cout<<"请输入点对 "<<endl; cin>>pi.x;cin>>pi.y; cout<<pi.x<<","<<pi.y<<endl;void sort() cout<<"以下是按x轴上由小到大排序后的点对"<<endl;for(i=0;i<sum-1;i+)for(j=i+1;j<sum;j+)if(pi.x>pj.x)p1=pi;pi=pj;pj=p1;for(i=0;i<sum;i+)cout<<pi.x<<","<<pi.y<<endl; void xiao() cout<<"以下是对每个模块中的点求距离"<<endl; for(k=0;k<sum/10;k+) cout<<"按任意键继续"<<endl; cin>>i; cout<<"以下是第"<<k<<"个模块中的距离"<<endl;for(i=1;i<10;i+)for(j=0;j<i;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);cout<<juliij<<"t"cout<<endl; mink=julik0,minik=10*k+1,minjk=10*k;for(i=1;i<10;i+)cout<<"n"<<"第"<<i<<"行以前的最小值为"<<mink<<endl;for(j=0;j<i;j+)if(juliij<mink)mink=juliij;minik=10*k+i;minjk=10*k+j;cout<<"n"<<"这是第"<<k<<"个模块中的结果"<<endl;cout<<"n"<<"距离最小值为"<<mink<<endl;cout<<"n"<<"距离最小值的第一个点为"<<minik<<endl; /cout<<"距离最小值的第一个点为"<<minik<<endl;/ if(sum%10!=0) k=sum/10; cout<<"输入0显示结果"<<endl; cin>>i; for(i=1;i<sum%10;i+) for(j=0;j<i;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);cout<<juliij;cout<<"t" cout<<endl; mink=juli10,minik=10*k+1,minjk=10*k; for(i=1;i<sum%10;i+) cout<<"n"<<"第"<<i<<"行以前的最小值为"<<mink<<endl; for(j=0;j<i;j+) if(juliij<mink) mink=juliij; minik=10*k+i; minjk=10*k+j; cout<<"n"<<"这是第"<<k<<"个模块中的结果"<<endl; cout<<"n"<<"距离最小值为"<<mink<<endl; cout<<"n"<<"距离最小值的第一个点为"<<minik<<endl; /cout<<"距离最小值的第一个点为"<<minik<<endl; void realmin()cout<<"n"<<"几个模块中的最小值是:"<<min10<<endl;for(i=0,min10=min0,mini10=mini0,minj10=minj0;i<=sum/10;i+)if(mini<min10)min10=mini;mini10=minii;minj10=minji;void bianjiemin()cout<<"n"<<" 包括边界的最小值是:"<<min10<<endl;for(i=0;i<sum/10;i+)for(k=9;k>=0;k-)if(p(i+1)*10.x-pi*10+k.x<min10)for(q=0;q<10;q+) if(p(i+1)*10+m.x-p(i+1)*10.x<min10)m=abs(pi*10+k.x-p(i+1)*10+m.x); n=abs(pi*10+k.y-p(i+1)*10+m.y); if(min10>sqrt(m*m+n*n) min10=sqrt(m*m+n*n); mini10=i*10+k; minj10=(i+1)*10+q; elsebreak;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);cout<<"n"<<"最接近点对为"<<"p"<<i<<""<<"("<<pi.x<<","<<pi.y<<")"<<" "<<"p"<<j<<""<<"("<<pj.x<<","<<pj.y<<")"<<endl;cout<<"n"<<"最短距离为"<<min10;cout<<"n"<<"最短距离为"<<s;int main()Ppoint x;x.shuru();x.sort();x.xiao();x.realmin();x.bianjiemin();x.shuchu(); return 0;二.设计体会通过这次的课程设计,我对C+程序语言有了更进一步的认识。我运用C+程序语言进行编程的能力有一定程度的提高,也掌握了C+程序语言程序设计过程、方法及实现,为以后相关的课程的学习打下良好基础;培养了我分析、解决问题的能力;也提高了我课程设计论文的写作能力。此次课程设计也让我发现了自己有许多的不足之处.由于平时的编写程序的机会也不是很多,再加上自己对C+程序语言掌握的不是很全面,使我设计程序的过程中遇到了一些难题.最后还得求助于书本才得以将问题解决.所以,我认为自己的实际编写程序能力还有待加强. 在课程设计的过程当中,程序的设计中运用到了C+程序语言中的类设计与实现、函数调用等方面的知识,从而使我更进一步地了解了那些方面的知识.我设计了学生选修课程系统设计和用分治算法解平面最接近点对问题这两个程序,经过查阅各种书籍以及上网查询,我基本能够实现老师所要求实现的功能. 总之,通过这次C+程序语言的课程设计,我不但在C+的理论知识方面有所提高,而且在实际应用方面也有一定的提高!以后我也会更加努力的学习有关C+以及相关的知识,以使自己更加理解C+程序语言并会运用其编出更好的程序!三、参考文献钱能<<C+程序设计教程(第二版)>> 清华大学出版社陈志泊 王春玲<<面向对象的程序设计语言-C+>> 人民邮电出版 网站:HTTP:/WWW.DDVIP.COM

    注意事项

    本文(用分治算法解平面最接近点对问题(共9页).doc)为本站会员(飞****2)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

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

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开