最近對(duì)問(wèn)題 遞歸與分治算法

《最近對(duì)問(wèn)題 遞歸與分治算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、《算法分析與設(shè)計(jì)》實(shí)驗(yàn)報(bào)告-7-實(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）分別用蠻力法和分治法求解最近對(duì)問(wèn)題；（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)對(duì)。三，實(shí)驗(yàn)環(huán)境TurboC或VC++四，實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)，必做實(shí)驗(yàn)五，數(shù)據(jù)結(jié)構(gòu)與算法#include#inclu

2、de#defineTRUE1#defineFALSE0typedefstructNode{doublex;doubley;}Node;//坐標(biāo)typedefstructList{Node*data;//點(diǎn)intcount;//點(diǎn)的個(gè)數(shù)}List;typedefstructCloseNode{《算法分析與設(shè)計(jì)》實(shí)驗(yàn)報(bào)告-7-Nodea;Nodeb;//計(jì)算距離的兩個(gè)點(diǎn)doublespace;//距離平方}CloseNode;intn;//點(diǎn)的數(shù)目//輸入各點(diǎn)到List中voidcreate(List&L){cout<<"請(qǐng)輸入平面上點(diǎn)的數(shù)目:

3、n";cin>>n;L.count=n;L.data=newNode[L.count];//動(dòng)態(tài)空間分配cout<<"輸入各點(diǎn)坐標(biāo):x_y):"<>L.data[i].x>>L.data[i].y;}//求距離的平方doublesquare(Nodea,Nodeb){return((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y));}//蠻力法voidBruteForce(constList&L,CloseNode&cnode,intbegin,inte

4、nd){for(inti=begin;i<=end;++i){for(intj=i+1;j<=end;++j){doublespace=square(L.data[i],L.data[j]);if(space

5、ti=0;ir[j+1].x){b=r[j].x;c=r[j].y;r[j].x=r[j+1].x;r[j].y=r[j+1].y;r[j+1].x=b;r[j+1].y=c;change=TRUE;}}}}//分治法中先將坐標(biāo)按X軸從小到大的順序排列voidpaixu(ListL){BubbleSort(L.data,L.count);//調(diào)用冒泡排序}//左右各距中線d的區(qū)域的最近對(duì)算法voidmiddle(constLis

6、t&L,CloseNode&cnode,intmid,doublemidX){inti,j;//分別表示中線左邊，右邊的點(diǎn)doubled=sqrt(cnode.space);i=mid;while(i>=0&&L.data[i].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.data[j].y<(L.data[i].y-d)

7、

8、L.data[j].y>(L.data[i].y+d))//判斷縱坐標(biāo)是否在左邊某固定點(diǎn)的2d區(qū)域內(nèi)co

9、ntinue;doublespace=square(L.data[i],L.data[j]);if(cnode.space>space)//在滿足條件的區(qū)域內(nèi)依次判斷{cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}《算法分析與設(shè)計(jì)》實(shí)驗(yàn)報(bào)告-7-}--i;}}//分治法求最近對(duì)voidDivideConquer(constList&L,CloseNode&closenode,intbegin,intend){if(begin!=end){intmid=(begin+end)/2;//排列后的中

10、間的那個(gè)點(diǎn)doublemidX=L.data[mid].x;Div