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

淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验1递归与分治算法最近对问题班级：软件081班学号：110831116姓名：陈点点评语：成绩：指导教师：批阅时间：年月日《算法分析与设计》实验报告-1-实验1递归与分治算法一，实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。二，实验内容设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三，实验环境TurboC或VC++四，实验学时2学时，必做实验五，数据结构与算法#includeiostream.h#includecmath#defineTRUE1#defineFALSE0typedefstructNode{doublex;doubley;}Node;//坐标typedefstructList{Node*data;//点intcount;//点的个数}List;typedefstructCloseNode{Nodea;Nodeb;//计算距离的两个点doublespace;//距离平方}CloseNode;《算法分析与设计》实验报告-2-intn;//点的数目//输入各点到List中voidcreate(List&L){cout请输入平面上点的数目:\n;cinn;L.count=n;L.data=newNode[L.count];//动态空间分配cout输入各点坐标:x_y):endl;for(inti=0;iL.count;++i)cinL.data[i].xL.data[i].y;}//求距离的平方doublesquare(Nodea,Nodeb){return((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y));}//蛮力法voidBruteForce(constList&L,CloseNode&cnode,intbegin,intend){for(inti=begin;i=end;++i){for(intj=i+1;j=end;++j){doublespace=square(L.data[i],L.data[j]);if(spacecnode.space){cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}}}}//冒泡排序voidBubbleSort(Noder[],intlength){intchange,n;n=length;change=TRUE;doubleb,c;for(inti=0;in-1&&change;++i)《算法分析与设计》实验报告-3-{change=FALSE;for(intj=0;jn-i-1;++j){if(r[j].xr[j+1].x){b=r[j].x;c=r[j].y;r[j].x=r[j+1].x;r[j].y=r[j+1].y;r[j+1].x=b;r[j+1].y=c;change=TRUE;}}}}//分治法中先将坐标按X轴从小到大的顺序排列voidpaixu(ListL){BubbleSort(L.data,L.count);//调用冒泡排序}//左右各距中线d的区域的最近对算法voidmiddle(constList&L,CloseNode&cnode,intmid,doublemidX){inti,j;//分别表示中线左边，右边的点doubled=sqrt(cnode.space);i=mid;while(i=0&&L.data[i].x=(midX-d))//在左边的d区域内{j=mid;while(L.data[++j].x=(midX+d)&&j=L.count)//在右边的d区域内{if(L.data[j].y(L.data[i].y-d)||L.data[j].y(L.data[i].y+d))//判断纵坐标是否在左边某固定点的2d区域内continue;doublespace=square(L.data[i],L.data[j]);if(cnode.spacespace)//在满足条件的区域内依次判断{cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}}--i;}}《算法分析与设计》实验报告-4-//分治法求最近对voidDivideConquer(constList&L,CloseNode&closenode,intbegin,intend){if(begin!=end){intmid=(begin+end)/2;//排列后的中间的那个点doublemidX=L.data[mid].x;DivideConquer(L,closenode,begin,mid);//继续在左半边用分治法求最近对DivideConquer(L,closenode,mid+1,end);//继续在右半边用分治法求最近对middle(L,closenode,mid,midX);//判断左右各距中线d的区域，是否有最近对}}voidmain(){//初始化Listlist;CloseNodeclosenode;closenode.space=10000;//最近点的距离create(list);//输入各点到NList中cout各点坐标为:endl;for(inti=0;ilist.count;++i)coutX=list.data[i].xY=list.data[i].y\n;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(intj=0;jlist.count;++j)coutX=list.data[j].xY=list.data[j].y\n;DivideConquer(list,closenode,0,list.count-1);cout最近对为点(closenode.a.x,closenode.a.y)和点(closenode.b.x,closenode.b.y)\n最近距离为:sqrt(closenode.space)endl;}《算法分析与设计》实验报告-5-六，核心源代码//左右各距中线d的区域的最近对算法voidmiddle(constList&L,CloseNode&cnode,intmid,doublemidX){inti,j;//分别表示中线左边，右边的点doubled=sqrt(cnode.space);i=mid;while(i=0&&L.data[i].x=(midX-d))//在左边的d区域内{j=mid;while(L.data[++j].x=(midX+d)&&j=L.count)//在右边的d区域内{if(L.data[j].y(L.data[i].y-d)||L.data[j].y(L.data[i].y+d))//判断纵坐标是否在左边某固定点的2d区域内continue;doublespace=square(L.data[i],L.data[j]);if(cnode.spacespace)//在满足条件的区域内依次判断{cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}}--i;}}//分治法求最近对voidDivideConquer(constList&L,CloseNode&closenode,intbegin,intend){if(begin!=end){intmid=(begin+end)/2;//排列后的中间的那个点doublemidX=L.data[mid].x;DivideConquer(L,closenode,begin,mid);//继续在左半边用分治法求最近对DivideConquer(L,closenode,mid+1,end);//继续在右半边用分治法求最近对middle(L,closenode,mid,midX);//判断左右各距中线d的区域，是否有最近对}}《算法分析与设计》实验报告-6-七，实验结果八，实验体会通过这次实验，我深刻了解到分治法的实用性，有效性。当遇到规模较大的问题，用我们以前学过的方法就太不明智了。将原问题划分成若干个较小规模的子问题，再继续求解，划分，能够简化问题。递归法，是一个很重要的方法，具有结构自相似的特性，刚开始学习编写的时候遇到了很多问题，不知道要找边界，不知道如何划分问题。关于这次算法，我觉得，类的部分还是一个难点，也就是说，不会将问题分解成抽象的概念，这也是我以后需要重点学习的地方。