递归与分治算法

实验1递归与分治算法一、实验目的和要求进一步掌握递归算法的设计思想以及递归程序的调试技术；理解这样一个观点：分治与递归经常同时应用在算法设计之中。分别用蛮力法和分治法求解最近对问题；分析算法的时间性能，设计实验程序验证分析结论。二、实验内容设p1=(x1,y1),p2=(x2,y2),…，pn二是评面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三、实验环境TurboC或VC++四、实验学时2学时，必做实验五、数据结构与算法#include<iostream>#include<cmath>usingnamespacestd;typedefstructNode/*定义存储点的结构*/{intx;inty;//点的x,y坐标}Node;typedefstructNList/*定义数据结构*/{Node*data;intcount;}NList;typedefstructCloseNode/*定义辅助的点结构*/{Nodea;Nodeb;doublespace;}CloseNode;intnum;/*归并排序算法*/voidMerge(NodeSR[],NodeTR[],inti,intm,intn)//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]{intj,k;for(j=m+1,k=i;i<=m&&j<=n;++k)if(SR[i].x<=SR[j].x)TR[k]=SR[i++];elseTR[k]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}voidMsort(NodeSR[],NodeTR1[],ints,intt)//将SR[s..t]归并排序为TR1[s..t]{if(s==t)TR1[s]=SR[s];else{intm=(s+t)/2;Node*TR2=newNode[num];Msort(SR,TR2,s,m);Msort(SR,TR2,m+1,t);Merge(TR2,TR1,s,m,t);}}voidMergeSort(NListL){Msort(L.data,L.data,0,L.count-1);}/*将各点坐标输入到数据结构NList中*/voidcreate(NList&L){cout<<"请输入平面上点的数目：〃；cin>>num;L.count=num;L.data=newNode[L.count];cout<<"输入"<<L.count<<"个点坐标X,Y,注意不要输入过大！"<<endl;for(inti=0;i<L.count;++i)cin>>L.data[i].x>>L.data[i].y;}/*求距离平方的函数*/doubleDis(Nodea,Nodeb){return((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y));}/*蛮力法求平面点集最近对问题，输入存放平面点集点的结构L、辅助点结构cnode，数组起点下标first与终点下标end*/voidClosestPoints1(constNList&L,CloseNode&cnode,intfirst,intend){for(inti=first;i<=end;++i)for(intj=i+1;j<=end;++j){doublespace=Dis(L.data[i],L.data[j]);if(space<cnode.space){cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}/*分治法求最近对中间2d对称区的算法*/voidMiddle(constNList&L,CloseNode&cnode,intmid,intmidX){inti,j;intd=sqrt(cnode.space);i=mid;while(i>=0&&L.data[i].x>=(midX-d)){j=mid;while(L.data[++j].x<=(midX+d)&&j<=L.count){if(L.data[j].y<(L.data[i].y-d)||L.data[j].y>(L.data[i].y+d))continue;doublespace=Dis(L.data[i],L.data[j]);if(cnode.space>space){cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}}--i;}}/*分治法求平面点集最近对问题，输入存放平面点集点的结构L、辅助点结构closenode，数组起点下标first与终点下标end*/voidClosestPoints2(constNList&L,CloseNode&closenode,intfirst,intend){if((end-first+1)<4)ClosestPoints1(L,closenode,first,end);else{intmid=(first+end)/2;intmidX=L.data[mid].x;ClosestPoints2(L,closenode,first,mid);ClosestPoints2(L,closenode,mid+1,end);Middle(L,closenode,mid,midX);}}/*主函数*/intmain(){cout<<"\t\t********************************************"<<endl;cout<<"\t\t*****蛮力法、分治法实现最近对问题的算法*****"<<endl;cout<<"\t\t********************************************"<<endl;NListlist;CloseNodeclosenode;closenode.space=10000;create(list);cout<<"各点坐标为："<<endl;for(inti=0;i<list.count;++i)cout<<"X="<<list.data[i].x<<"Y="<<list.data[i].y<<"\n”;if(num>=2){ClosestPoints1(list,closenode,0,list.count-1);cout<<"用蛮力法求最近对:"<<endl;cout<<"最近对为点("<<closenode.a.x<<”,"<<closenode.a.y<<”)和点("<<closenode.b.x<<”,"<<closenode.b.y<<”)”<<endl;cout<<"最近距离为："<<closenode.space<<endl;cout<<"**************************************"<<endl;cout<<"用分治法求最近对:〃<<endl;MergeSort(list);cout<<"经过归并排序后的各点坐标为:〃<<endl;for(intj=0;j<list.count;++j)cout<<"X="<<list.data[j].x<<"Y="<<list.data[j].y<<"\n”;ClosestPoints2(list,closenode,0,list.count-1);cout<<"最近对为点("<<closenode.a.x<<”,"<<closenode.a.y<<”)和点("<<closenode.b.x<<”,"<<closenode.b.y<<”)”<<endl;cout<<"最近距离为："<<closenode.space<<endl;return0;}else{cout<<"不存在最近点对！"<<endl;}}六、核心源代码/*蛮力法求平面点集最近对问题，输入存放平面点集点的结构L、辅助点结构cnode，数组起点下标first与终点下标end*/voidClosestPoints1(constNList&L,CloseNode&cnode,intfirst,intend){for(inti=first;i<=end;++i)for(intj=i+1;j<=end;++j){doublespace=Dis(L.data[i],L.data[j]);if(space<cnode.space){cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}}}/*分治法求平面点集最近对问题，输入存放平面点集点的结构L、辅助点结构closenode，数组起点下标first与终点下标end*/voidClosestPoints2(constNList&L,CloseNode&closenode,intfirst,intend){if((end-first+1)<