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

1、實(shí)驗(yàn)1 遞歸與分治算法一，實(shí)驗(yàn)?zāi)康暮鸵螅?）進(jìn)一步掌握遞歸算法的設(shè)計(jì)思想以及遞歸程序的調(diào)試技術(shù)；（2）理解這樣一個(gè)觀點(diǎn)：分治與遞歸經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中。（3）分別用蠻力法和分治法求解最近對問題；（4）分析算法的時(shí)間性能，設(shè)計(jì)實(shí)驗(yàn)程序驗(yàn)證分析結(jié)論。 二，實(shí)驗(yàn)內(nèi)容設(shè)p1=(x1, y1), p2=(x2, y2), , pn=(xn, yn)是平面上n個(gè)點(diǎn)構(gòu)成的集合S，設(shè)計(jì)算法找出集合S中距離最近的點(diǎn)對。三，實(shí)驗(yàn)環(huán)境 Turbo C 或VC+四，實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)五，數(shù)據(jù)結(jié)構(gòu)與算法#include<iostream.h>#include<cmath>#def

2、ine TRUE 1#define FALSE 0typedef struct Node double x; double y;Node; /坐標(biāo)typedef struct List Node* data; /點(diǎn) int count; /點(diǎn)的個(gè)數(shù)List;typedef struct CloseNode Node a; Node b; /計(jì)算距離的兩個(gè)點(diǎn) double space; /距離平方CloseNode;int n; /點(diǎn)的數(shù)目/輸入各點(diǎn)到List中void create(List &L) cout<<"請輸入平面上點(diǎn)的數(shù)目:n" cin>

3、;>n; L.count=n; L.data = new NodeL.count; /動態(tài)空間分配 cout<<"輸入各點(diǎn)坐標(biāo) :x_y):"<<endl; for(int i=0;i<L.count;+i) cin>>L.datai.x>>L.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,CloseNod

4、e &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(space<cnode.space) cnode.a=L.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=

5、0;i<n-1&&change;+i)change=FALSE;for(int j=0;j<n-i-1;+j)if(rj.x>rj+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;/分治法中先將坐標(biāo)按X軸從小到大的順序排列void paixu(List L) BubbleSort(L.data,L.count); /調(diào)用冒泡排序/左右各距中線d的區(qū)域的最近對算法void middle(const List & L,CloseNode &cnode,

6、int mid,double midX) int i,j; /分別表示中線左邊，右邊的點(diǎn) double d=sqrt(cnode.space); i=mid; while(i>=0&&L.datai.x>=(midX-d) /在左邊的d區(qū)域內(nèi) j=mid; while(L.data+j.x<=(midX+d)&&j<=L.count) /在右邊的d區(qū)域內(nèi) if(L.dataj.y<(L.datai.y-d)|L.dataj.y>(L.datai.y+d) /判斷縱坐標(biāo)是否在左邊某固定點(diǎn)的2d區(qū)域內(nèi) continue; doub

7、le space = square(L.datai,L.dataj); if(cnode.space>space) /在滿足條件的區(qū)域內(nèi)依次判斷 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; /排列后的中間的那個(gè)點(diǎn) double midX = L.datamid.x;

8、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; /最近點(diǎn)的距離 create(list); /輸入各點(diǎn)到NList中 cout<<"各點(diǎn)坐標(biāo)為:"<

9、;<endl; for(int i=0;i<list.count;+i) cout<<"X="<<list.datai.x<<" Y="<<list.datai.y<<"n" BruteForce(list,closenode,0,list.count-1); cout<<"用蠻力法求最近對:"<<endl; cout<<"最近對為點(diǎn) ("<<closenode.a.x<

10、<","<<closenode.a.y<<")和點(diǎn)("<<closenode.b.x<<","<<closenode.b.y<<")n"<<"最近距離為: "<<sqrt(closenode.space)<<endl; cout<<endl<<endl; cout<<"用分治法求最近對:"<<endl; paixu(

11、list); cout<<"經(jīng)過排序后的各點(diǎn):"<<endl; for(int j=0;j<list.count;+j) cout<<"X="<<list.dataj.x<<" Y="<<list.dataj.y<<"n" DivideConquer(list,closenode,0,list.count-1); cout<<"最近對為點(diǎn) ("<<closenode.a.x<&

12、lt;","<<closenode.a.y<<")和點(diǎn)("<<closenode.b.x<<","<<closenode.b.y<<")n"<<"最近距離為: "<<sqrt(closenode.space)<<endl;六，核心源代碼 /左右各距中線d的區(qū)域的最近對算法void middle(const List & L,CloseNode &cnode,int mid,

13、double midX) int i,j; /分別表示中線左邊，右邊的點(diǎn) double d=sqrt(cnode.space); i=mid; while(i>=0&&L.datai.x>=(midX-d) /在左邊的d區(qū)域內(nèi) j=mid; while(L.data+j.x<=(midX+d)&&j<=L.count) /在右邊的d區(qū)域內(nèi) if(L.dataj.y<(L.datai.y-d)|L.dataj.y>(L.datai.y+d) /判斷縱坐標(biāo)是否在左邊某固定點(diǎn)的2d區(qū)域內(nèi) continue; double space

14、 = square(L.datai,L.dataj); if(cnode.space>space) /在滿足條件的區(qū)域內(nèi)依次判斷 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; /排列后的中間的那個(gè)點(diǎn) double midX = L.datamid.x; DivideConquer(L,closenode,begin,mid); /繼續(xù)在左半邊用分治法求最近對 DivideConquer(L,closenode,mid+1,end); /繼續(xù)在右半邊用分治法求最近對 middle(L,closenode,mid,midX); /判斷左右各距中線d