最近對問題遞歸與分治算法

1、實驗1 遞歸與分治算法一，實驗目的和要求（1）進一步掌握遞歸算法的設計思想以及遞歸程序的調試技術；（2）理解這樣一個觀點：分治與遞歸經常同時應用在算法設計之中。（3）分別用蠻力法和分治法求解最近對問題；（4）分析算法的時間性能，設計實驗程序驗證分析結論。 二，實驗內容設p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n個點構成的集合s，設計算法找出集合s中距離最近的點對。三，實驗環(huán)境 turbo c 或vc+四，實驗學時 2學時，必做實驗五，數(shù)據(jù)結構與算法#include#include#define true 1#define false 0typede

2、f struct node double x; double y;node; /坐標typedef struct list node* data; /點 int count; /點的個數(shù)list;typedef struct closenode node a; node b; /計算距離的兩個點 double space; /距離平方closenode;int n; /點的數(shù)目/輸入各點到list中void create(list &l) coutn; l.count=n; l.data = new nodel.count; /動態(tài)空間分配 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的區(qū)域的最近對算法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區(qū)域內 j=mid; while(l.data+j.x=(midx+d)&j=l.count) /在右邊的d區(qū)域內 if(l.dataj.y(l.datai.y+d) /判斷縱坐標是否

6、在左邊某固定點的2d區(qū)域內 continue; double space = square(l.datai,l.dataj); if(cnode.spacespace) /在滿足條件的區(qū)域內依次判斷 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); /繼續(xù)在左半邊用分治法求最近對 divideconquer(l,closenode,mid+1,end); /繼續(xù)在右半邊用分治法求最近對 middle(l,closenode,mid,midx); /判斷左右各距中線d的區(qū)域，是否有最近對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區(qū)域內 j=mid; while(l.data+j.x=(midx+d)&j=l.count) /在右邊的d區(qū)域內 if(l.dataj

10、.y(l.datai.y+d) /判斷縱坐標是否在左邊某固定點的2d區(qū)域內 continue; double space = square(l.datai,l.dataj); if(cnode.spacespace) /在滿足條件的區(qū)域內依次判斷 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 = l.datamid.x; divideconquer(l,closenode,begin,mid); /繼續(xù)在左半邊用分治法求最近對 divideconquer(l,closenode,mid+1,end); /繼續(xù)在右半邊用分治法求最近對 middle(l,closenode,mid,midx); /判斷左右各距中線d的區(qū)域，是否有最近對七，實驗結果八，實驗體會通過這次實驗，我深刻了解到分治法的實用性，有效性。當遇到規(guī)模較大的問題，