《算法設(shè)計與分析》分治法實驗報告一

寧波工程學(xué)院電信學(xué)院計算機教研室實驗報告課程名稱：算法設(shè)計與分析實驗項目：實驗一：分治法指導(dǎo)教師：蘇日娜實驗位置：計算機中心二樓姓名：梅胤班級：計科094學(xué)號：29日期：2011/10/17實驗?zāi)康耐ㄟ^上機實驗，要求掌握分治法算法的問題描述、算法設(shè)計思想、程序設(shè)計和算法復(fù)雜性分析等。二、實驗環(huán)境：VC6.0三、實驗內(nèi)容用分治法算法解最接近點對問題（1）問題的描述給定平面上n個點，找其中的一對點，使得在n個點組成的所有點對中，該點對間的距離最小。（2）算法設(shè)計思想將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題解合并得到原問題的解。（3）程序設(shè)計#include<iostream>#include<cstdlib>#include<ctime>#include<cmath>usingstd::cout;usingstd::endl;#defineN5intx[N],y[N],record[N];//產(chǎn)生原始點數(shù)據(jù)，x坐標(biāo)放在x[]中，y坐標(biāo)放在y[]中。doubleMin;/////////////////////////產(chǎn)生隨機數(shù)組/////////////////////////////voidrandnum(){inti;srand(time(0));for(i=0;i<N;i++){x[i]=rand()%N;cout<<x[i]<<'';}cout<<endl;for(i=0;i<N;i++){y[i]=rand()%N;cout<<y[i]<<'';}cout<<endl;}///////////////////////////交換數(shù)組元素///////////////////////////voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}//求平方//intsquare(intx){returnx*x;}//求兩點之間距離//doublelengthf(intx1,inty1,intx2,inty2){returnsqrt(square(x1-x2)+square(y1-y2));}//求兩者中最小者//doublemin(doublea,doubleb){if(a>=b)returnb;elsereturna;}//對平面數(shù)組排序//voidsort(intA[]){inti,j;for(i=0;i<N;i++)record[i]=i;for(j=1;j<N;j++){i=j;while(i>=0&&A[i]<A[i-1]){swap(A[i],A[i-1]);swap(record[i-1],record[i]);//得到x排序后對應(yīng)的原y的坐標(biāo)i--;}}cout<<"排序后的元素數(shù)組："<<endl;for(i=0;i<N;i++)cout<<A[i]<<'';cout<<endl;for(i=0;i<N;i++)cout<<record[i]<<'';cout<<endl;}//分治法//doublemerge(intleft,intright){doublemlength;if(right==left)mlength=10e-6;if(right==left+1)mlength=lengthf(x[right],y[record[right]],x[left],y[record[left]]);//兩個點時求最小值if(right-left==2)mlength=min(min(lengthf(x[right-1],y[record[right-1]],x[left],y[record[left]]),lengthf(x[right],y[record[right]],x[left+1],y[record[left+1]])),lengthf(x[right],y[record[right]],x[left],y[record[left]]));//三個點時求最大值returnmlength;}doubledivide(intleft,intright){if(right-left<=2){Min=merge(left,right);}else{doublel1,l2,mi;//l1記錄劃分區(qū)域后左半面最小距離，l2記錄右半面最小距離，min為兩者中較小者，m為全部中的最小者intrem1,rem2,l;//記錄獲得最短距離對應(yīng)的兩個點//intil,jl,ir,jr;inti,j;intR,L;R=L=0;//記錄劃分小區(qū)域后的左半塊和右半塊個有多少元素l1=l2=Min=100;l=(right-left+1)/2-1;//中線位置///////////////////////////////////////////////////l1=divide(left,l);l2=divide(l+1,right);if(l1<l2){Min=l1;//cout<<"兩半面最短距離是："<<min;}else{Min=l2;//cout<<"兩半面最短距離是："<<min;}///////////////////得到右半塊元素數(shù)R//cout<<"min="<<min<<endl;for(i=l+1;i<N;i++){if(x[i]-x[l]<=Min)R++;elsebreak;}//cout<<"R="<<R<<endl;/////////////////////得到左半塊元素數(shù)Lfor(i=l;i>=0;i--){if(x[l]-x[i]<=Min)L++;elsebreak;}//cout<<"L="<<L<<endl;if(L!=0&&R!=0){for(i=l-L+1;i<=l;i++)for(j=l+1;j<=l+R;j++){if(y[record[j]]-y[record[i]]<Min||-Min<y[record[j]]-y[record[i]]){mi=lengthf(x[i],y[record[i]],x[j],y[record[j]]);if(mi<Min){Min=mi;rem1=i;rem2=j;}}}//cout<<"min="<<min<<endl;//cout<<"rem1="<<rem1<<endl<<"rem2="<<rem2<<endl;}}returnMin;}/***********************************************************************///主函數(shù)//intmain(){//doublea;randnum();cout<<"*********************分治法********************"<<endl;sort(x);divide(0