最近对问题递归与分治算法

1、实验1 递归与分治算法一，实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。 二，实验内容设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三，实验环境 Turbo C 或VC+四，实验学时 2学时，必做实验五，数据结构与算法#include<iostream.h>#include<cmath>#def

2、ine TRUE 1#define FALSE 0typedef struct Node double x; double y;Node; /坐标typedef struct List Node* data; /点 int count; /点的个数List;typedef struct CloseNode Node a; Node b; /计算距离的两个点 double space; /距离平方CloseNode;int n; /点的数目/输入各点到List中void create(List &L) cout<<"请输入平面上点的数目:n" cin>

3、;>n; L.count=n; L.data = new NodeL.count; /动态空间分配 cout<<"输入各点坐标 :x_y):"<<endl; for(int i=0;i<L.count;+i) cin>>L.datai.x>>L.datai.y;/求距离的平方double square(Node a,Node b) return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);/蛮力法void BruteForce(const List &L,CloseNod

4、e &cnode,int begin,int end) for(int i=begin;i<=end;+i) for(int j=i+1;j<=end;+j) double space=square(L.datai,L.dataj); if(space<cnode.space) cnode.a=L.datai; cnode.b=L.dataj; cnode.space=space; /冒泡排序void BubbleSort(Node r,int length)int change,n;n=length;change=TRUE;double b,c;for(int i=

5、0;i<n-1&&change;+i)change=FALSE;for(int j=0;j<n-i-1;+j)if(rj.x>rj+1.x)b=rj.x;c=rj.y;rj.x=rj+1.x;rj.y=rj+1.y;rj+1.x=b;rj+1.y=c; change=TRUE;/分治法中先将坐标按X轴从小到大的顺序排列void paixu(List L) BubbleSort(L.data,L.count); /调用冒泡排序/左右各距中线d的区域的最近对算法void middle(const List & L,CloseNode &cnode,

6、int mid,double midX) int i,j; /分别表示中线左边，右边的点 double d=sqrt(cnode.space); i=mid; while(i>=0&&L.datai.x>=(midX-d) /在左边的d区域内 j=mid; while(L.data+j.x<=(midX+d)&&j<=L.count) /在右边的d区域内 if(L.dataj.y<(L.datai.y-d)|L.dataj.y>(L.datai.y+d) /判断纵坐标是否在左边某固定点的2d区域内 continue; doub

7、le space = square(L.datai,L.dataj); if(cnode.space>space) /在满足条件的区域内依次判断 cnode.a=L.datai; cnode.b=L.dataj; cnode.space=space; -i; /分治法求最近对void DivideConquer(const List &L,CloseNode &closenode,int begin,int end)if(begin!=end) int mid = (begin+end)/2; /排列后的中间的那个点 double midX = L.datamid.x;

8、DivideConquer(L,closenode,begin,mid); /继续在左半边用分治法求最近对 DivideConquer(L,closenode,mid+1,end); /继续在右半边用分治法求最近对 middle(L,closenode,mid,midX); /判断左右各距中线d的区域，是否有最近对void main() /初始化 List list; CloseNode closenode; closenode.space = 10000; /最近点的距离 create(list); /输入各点到NList中 cout<<"各点坐标为:"<

9、;<endl; for(int i=0;i<list.count;+i) cout<<"X="<<list.datai.x<<" Y="<<list.datai.y<<"n" BruteForce(list,closenode,0,list.count-1); cout<<"用蛮力法求最近对:"<<endl; cout<<"最近对为点 ("<<closenode.a.x<

10、<","<<closenode.a.y<<")和点("<<closenode.b.x<<","<<closenode.b.y<<")n"<<"最近距离为: "<<sqrt(closenode.space)<<endl; cout<<endl<<endl; cout<<"用分治法求最近对:"<<endl; paixu(

11、list); cout<<"经过排序后的各点:"<<endl; for(int j=0;j<list.count;+j) cout<<"X="<<list.dataj.x<<" Y="<<list.dataj.y<<"n" DivideConquer(list,closenode,0,list.count-1); cout<<"最近对为点 ("<<closenode.a.x<&

12、lt;","<<closenode.a.y<<")和点("<<closenode.b.x<<","<<closenode.b.y<<")n"<<"最近距离为: "<<sqrt(closenode.space)<<endl;六，核心源代码 /左右各距中线d的区域的最近对算法void middle(const List & L,CloseNode &cnode,int mid,

13、double midX) int i,j; /分别表示中线左边，右边的点 double d=sqrt(cnode.space); i=mid; while(i>=0&&L.datai.x>=(midX-d) /在左边的d区域内 j=mid; while(L.data+j.x<=(midX+d)&&j<=L.count) /在右边的d区域内 if(L.dataj.y<(L.datai.y-d)|L.dataj.y>(L.datai.y+d) /判断纵坐标是否在左边某固定点的2d区域内 continue; double space

14、 = square(L.datai,L.dataj); if(cnode.space>space) /在满足条件的区域内依次判断 cnode.a=L.datai; cnode.b=L.dataj; cnode.space=space; -i; /分治法求最近对void DivideConquer(const List &L,CloseNode &closenode,int begin,int end)if(begin!=end) int mid = (begin+end)/2; /排列后的中间的那个点 double midX = L.datamid.x; DivideConquer(L,closenode,begin,mid); /继续在左半边用分治法求最近对 DivideConquer(L,closenode,mid+1,end); /继续在右半边用分治法求最近对 middle(L,closenode,mid,midX); /判断左右各距中线d