《最近对问题 递归与分治算法.doc》由会员分享，可在线阅读，更多相关《最近对问题 递归与分治算法.doc（7页珍藏版）》请在三一文库上搜索。
1、实验1 递归与分治算法一，实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。 二，实验内容设p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三，实验环境 Turbo C 或VC+四，实验学时 2学时，必做实验五，数据结构与算法#include#include#define TRUE 1#define FALSE 0typede
2、f 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) coutn; L.count=n; L.data = new NodeL.count; /动态空间分配 cout输入各点坐标 :x_y):endl; for
3、(int i=0;iL.datai.xL.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,CloseNode &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(spacecnode.space) cnode.a=L
4、.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=0;in-1&change;+i)change=FALSE;for(int j=0;jrj+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) Bub
5、bleSort(L.data,L.count); /调用冒泡排序/左右各距中线d的区域的最近对算法void middle(const List & L,CloseNode &cnode,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) /判断纵坐标是否
6、在左边某固定点的2d区域内 continue; double space = square(L.datai,L.dataj); if(cnode.spacespace) /在满足条件的区域内依次判断 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
7、 = L.datamid.x; 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各点坐标为:endl; f
8、or(int i=0;ilist.count;+i) coutX=list.datai.x Y=list.datai.yn; BruteForce(list,closenode,0,list.count-1); cout用蛮力法求最近对:endl; cout最近对为点 (closenode.a.x,closenode.a.y)和点(closenode.b.x,closenode.b.y)n最近距离为: sqrt(closenode.space)endl; coutendlendl; cout用分治法求最近对:endl; paixu(list); cout经过排序后的各点:endl; for(i
9、nt j=0;jlist.count;+j) coutX=list.dataj.x Y=list.dataj.yn; DivideConquer(list,closenode,0,list.count-1); cout最近对为点 (closenode.a.x,closenode.a.y)和点(closenode.b.x,closenode.b.y)n最近距离为: sqrt(closenode.space)=0&L.datai.x=(midX-d) /在左边的d区域内 j=mid; while(L.data+j.x=(midX+d)&j=L.count) /在右边的d区域内 if(L.dataj
10、.y(L.datai.y+d) /判断纵坐标是否在左边某固定点的2d区域内 continue; double space = square(L.datai,L.dataj); if(cnode.spacespace) /在满足条件的区域内依次判断 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;
11、 /排列后的中间的那个点 double midX = L.datamid.x; DivideConquer(L,closenode,begin,mid); /继续在左半边用分治法求最近对 DivideConquer(L,closenode,mid+1,end); /继续在右半边用分治法求最近对 middle(L,closenode,mid,midX); /判断左右各距中线d的区域，是否有最近对七，实验结果八，实验体会通过这次实验，我深刻了解到分治法的实用性，有效性。当遇到规模较大的问题，用我们以前学过的方法就太不明智了。将原问题划分成若干个较小规模的子问题，再继续求解，划分，能够简化问题。递归法，是一个很重要的方法，具有结构自相似的特性，刚开始学习编写的时候遇到了很多问题，不知道要找边界，不知道如何划分问题。关于这次算法，我觉得，类的部分还是一个难点，也就是说，不会将问题分解成抽象的概念，这也是我以后需要重点学习的地方。