实验七 最近点对问题的设计与实现.doc_第1页
实验七 最近点对问题的设计与实现.doc_第2页
实验七 最近点对问题的设计与实现.doc_第3页
实验七 最近点对问题的设计与实现.doc_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

实验七 最近点对问题的设计与实现一、 实验目的1掌握分治算法的基本原理2利用分治策略编程解决最近点对问题二、 实验要求1设计算法2写出相应程序3保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容算法思想：用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S1和 S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，如果这两个点分别在 S1和 S2中，则根据具体情况具体分析。1、考虑一维情形下的最近点对问题：设x1, x2, , xn是x轴上有n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。算法思想：用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数近似相同。递归地在S1和S2上求出最接近点对 (p1, p2) 和(q1, q2)，如果集合S中的最接近点对都在子集S1或S2中，则d=min(p1, p2), (q1, q2)即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3, q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。例如：(1)输入 -8，-5，-4，1，3，7，输出为1. (2)输入 -8，-5，-2，1，3，7，输出为2. (3)输入 -8，-4，-1，1，4，7，输出为2.附加题：（有时间可继续完成下面内容）2、考虑一维情形下的最近点对问题：设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。算法：四、程序代码#include int a(int * p,int low,int high) int min=0,min1,min2,min3; int m=(high+low)/2; if(high-low1) min1=a(p,low,m); min2=a(p,m+1,high); min=min1min2?min1:min2; else if(low=high) return phigh-plow-1; else return phigh-plow; return min; int main() int p20,x; printf(请输入数组个数：); scanf(%d,&x); printf(请输入数组元素：n); for(int i=0;ix;i+) scanf(%d,&pi)
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论