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

最近对问题-递归与分治算法《算法分析与设计》实验报告 -PAGE4-实验1递归与分治算法一，实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。二，实验内容设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三，实验环境TurboC或VC++四，实验学时2学时，必做实验五，数据结构与算法#include<iostream.h>#include<cmath>#defineTRUE1#defineFALSE0typedefstructNode{doublex;doubley;}Node;//坐标typedefstructList{Node*data;//点intcount;//点的个数}List;typedefstructCloseNode{Nodea;Nodeb;//计算距离的两个点doublespace;//距离平方}CloseNode;intn;//点的数目}//左右各距中线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.space>space)//在满足条件的区域内依次判断 {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的区域，是否有最近对 }}voidmain(){//初始化Listlist;CloseNodeclosenode;closenode.space=10000;//最近点的距离create(list);//输入各点到NList中cout<<"各点坐标为:"<<endl;for(inti=0;i<list.count;++i)cout<<"X="<<list.data[i].x<<"Y="<<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;cout<<endl<<endl;cout<<"用分治法求最近对:"<<endl;paixu(list);cout<<"经过排序后的各点:"<<endl;for(intj=0;j<list.count;++j)cout<<"X="<<list.data[j].x<<"Y="<<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;}六，核心源代码//左右各距中线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.space>space)//在满足条件的区域内依次判断 {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的区域，是否有最近对 }}七，实验结果八，实验体会通过这次实验，我深刻了解到分治法的实用性，