算法分析三个实验(分治／动归／回溯).doc

《算法分析三个实验(分治／动归／回溯).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析三个实验（分治/动归/回溯）I'm段凯越、人特别感谢郭鹏老师和蔡润身老师的耐心指导和帮助/***********************分治法_最近对问题*********************/#include#include#include#includebruteforce(x[],y[])/蛮力法{m=;n=0;k=；min;doubletemp[45];min=((x[]・x[])*(x[]-x[])+(y[

2、]-y[])*(y[]-y[]));for(i=();iv=8;i++)(j=；jv=-i;j++){temp[k]=sqr((x[i]-x[i+j])*(x[i]-x[i+j])+(y[i].y[i+j])*(y[i].y[i+j]));if(temp[k]

3、blex[],doubley[],intm,intn)〃冒泡排序{temp;intij；(i=m;iv=n_;i++)(j=i;jv=n;j++)(x[i]>x[j]){temp=x[i];x[i]=x[j];x

4、j]=temp;temp=y[i];y[i]=y[j];y[j]=temp;}doubledist(doublexl,doubleyl,doublex2,doubley2)〃计算距离{rsqrt((xl-x2)*(xl・x2)+(yl-y2)*(yl-y2));}getmin(x,y)，求最近

5、距离{if(xvy)X；elsey;}divideconquer(x[],y[]?start,end)〃分治法{intij,mid;(start==end)199999.(;(start==end-)dist(x[start],y[start],x[end],y[end]);if(start==end-2)returngetmin(getmin(dist(x[start],y[start],x[start+],y[start+]),dist(x[start+],y[start+],x[start+2],

6、y[start+])),dist(x[start],y[start],x[start+],y[start+]));mid=(start+end)/2;doublecurmin=getmin(divideconquer(x,y,start,mid),divideconquer(x,y,mid+,end));fb(i=start;iv=end;i++)(j=i+；jv=i+&&jv=end;j++){curmin=getmin(curmin,dist(x[i],y[i],x[j],y[j]));curmin

7、;main()W；doublex[10];//P0-±I；0Edoubley[lC']；//0>0-±I"OEsrand(timc(CI));(r=0;r<=9;r-H-){x[r]=()%;printf(Mn);(r=0;rv=9;r++){y[r]=ran()%;printf(”％.01f”,y[r]);}printfCn);bruteft)rce(x,y);sort(x,y,0,9);result=divideconquer(x,y,,);printf(n分治法：最短距离是％.51fW,

8、result);return0;/*********************动)态莉J戈lj一利J#includestd:XdivideMaxSum(a[],myleft,myright){rights,lefts,ij,rightsum,leftsum,sl?s2,b,center;sum=;(myleft==myright){(a[myleft]>)sum=a[myleft];elsesum=;}else(center=(myleft+myright)/;leftsum=di

9、videMaxSum(a,myleft,center);rightsum=divideMaxSum(a,center+,myright);sl=O;lefts=O;(i=center;i>=myleft;i—)(lefts+=a[i];(lefts>sl)sl=lefts;)s2=0;rights=0;(j=center+;jv=myright;j++){rights+=a

10、j];(rights>s2)s2=rights;}sum=sl+s