最近对问题-递归与分治算法.doc

《最近对问题-递归与分治算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验报告-7-实验1递归与分治算法一，实验目的和要求（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。（3）分别用蛮力法和分治法求解最近对问题；（4）分析算法的时间性能，设计实验程序验证分析结论。二，实验内容设p1=(x1,y1),p2=(x2,y2),…,pn=(xn,yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。三，实验环境TurboC或VC++四，实验学时2学时，必做实验五，数据结构与算法#inclu

2、de#include#defineTRUE1#defineFALSE0typedefstructNode{doublex;doubley;}Node;//坐标typedefstructList{Node*data;//点intcount;//点的个数}List;typedefstructCloseNode{《算法分析与设计》实验报告-7-Nodea;Nodeb;//计算距离的两个点doublespace;//距离平方}CloseNode;intn;//点的数目//输入各点到Lis

3、t中voidcreate(List&L){cout<<"请输入平面上点的数目:";cin>>n;L.count=n;L.data=newNode[L.count];//动态空间分配cout<<"输入各点坐标: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));}/

4、/蛮力法voidBruteForce(constList&L,CloseNode&cnode,intbegin,intend){for(inti=begin;i<=end;++i){for(intj=i+1;j<=end;++j){doublespace=square(L.data[i],L.data[j]);if(space

5、r[],intlength){《算法分析与设计》实验报告-7-intchange,n;n=length;change=TRUE;doubleb,c;for(inti=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;}}}}//分治法中先将坐标按X

6、轴从小到大的顺序排列voidpaixu(ListL){BubbleSort(L.data,L.count);//调用冒泡排序}//左右各距中线d的区域的最近对算法voidmiddle(constList&L,CloseNode&cnode,intmid,doublemidX){inti,j;//分别表示中线左边，右边的点doubled=sqrt(cnode.space);i=mid;while(i>=0&&L.data[i].x>=(midX-d))//在左边的d区域内{j=mid;while(L.data[++j]

7、.x<=(midX+d)&&j<=L.count)//在右边的d区域内{if(L.data[j].y<(L.data[i].y-d)

8、

9、L.data[j].y>(L.data[i].y+d))//判断纵坐标是否在左边某固定点的2d区域内continue;doublespace=square(L.data[i],L.data[j]);if(cnode.space>space)//在满足条件的区域内依次判断{cnode.a=L.data[i];cnode.b=L.data[j];cnode.space=space;}《算

10、法分析与设计》实验报告-7-}--i;}}//分治法求最近对voidDivideConquer(constList&L,CloseNode&closenode,intbegin,intend){if(begin!=end){intmid=(begin+end)/2;//排列后的中间的那个点doublemidX=L.data[mid].x;Div