遞歸與分治算法

實驗1遞歸與分治算法一、實驗目的和要求進一步掌握遞歸算法的設計思想以及遞歸程序的調試技術；理解這樣一個觀點：分治與遞歸經常同時應用在算法設計之中。分別用蠻力法和分治法求解最近對問題；分析算法的時間性能，設計實驗程序驗證分析結論。二、實驗內容設p1=(x1,y1),p2=(x2,y2),…，pn二是評面上n個點構成的集合S，設計算法找出集合S中距離最近的點對。三、實驗環(huán)境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對稱區(qū)的算法*/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)<