中南大學(xué)-算法實(shí)驗(yàn)報(bào)告

中南大學(xué)算法分析與設(shè)計(jì)中南大學(xué)算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告班級(jí)：物聯(lián)網(wǎng)****班學(xué)號(hào)：******姓名：*** 指導(dǎo)老師：沙莎 2012年12月28日１目錄分治法實(shí)驗(yàn)1.快速排序……………………22.歸并排序………43.最大最小值……………………7動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)多段圖……………10回溯法實(shí)驗(yàn)N皇后……………15分治法實(shí)驗(yàn)分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同。遞歸地求解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。快速排序快速排序是基于分治策略的一個(gè)排序算法實(shí)現(xiàn)快速排序的分治過(guò)程如下：分解：數(shù)組A[p..r]被劃分為兩個(gè)（可能空）子數(shù)組A[p..q-1]和A[q+1..r],使得A[p..q-1]中的每個(gè)元素都小于等于A(q),而且，小于等于A[q+1..r]中的元素。下標(biāo)q也在這個(gè)劃分過(guò)程中進(jìn)行計(jì)算。解決：通過(guò)遞歸調(diào)用快速排序，對(duì)子數(shù)組A[p..q-1]和A[q+1..r]排序合并：因?yàn)閮蓚€(gè)子數(shù)組是就地排序的，將它們的合并不需要操作，整個(gè)數(shù)組A[p..r]已排序。實(shí)驗(yàn)代碼如下：#include<iostream>usingnamespacestd;intnum;voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}//交換元素位置voidPrintArray(int*arr){for(inti=1;i<=num;++i)cout<<arr[i]<<"";cout<<endl;}intPartition1(int*arr,intp,intr){intx=arr[r];inti=p-1;intj;for(j=p;j<=r-1;j++){if(arr[j]<=x){i=i+1;swap(arr[i],arr[j]); }}swap(arr[i+1],arr[r]);returni+1;}//對(duì)子數(shù)組A[p..r]進(jìn)行就地重排voidQuickSort(int*arr,intp,intr){if(p<r){intq=Partition1(arr,p,r);QuickSort(arr,p,q-1);QuickSort(arr,q+1,r);}}//該過(guò)程實(shí)現(xiàn)快速排序intmain(){intarr[100];cout<<"請(qǐng)輸入元素個(gè)數(shù):\n";cin>>num;cout<<"請(qǐng)輸入元素大小:\n";for(inti=1;i<=num;++i)cin>>arr[i];QuickSort(arr,1,num);cout<<"最后結(jié)果:";PrintArray(arr);return0;}運(yùn)行結(jié)果如下圖所示:實(shí)驗(yàn)收獲與體會(huì)：通過(guò)證明可以得到該算法在最壞情況下的時(shí)間復(fù)雜性為T(n)=O(n^2),平均情況下的時(shí)間復(fù)雜性是O(nlogn)，通過(guò)該實(shí)驗(yàn)對(duì)分治法基本思想有了了解。歸并排序:基本操作如下：分解：將n個(gè)元素分成各含n/2個(gè)元素的子序列解決：用合并排序法對(duì)兩個(gè)子序列遞歸地排序合并：合并兩個(gè)已排好序的子序列得到排序結(jié)果在對(duì)子序列排序時(shí)，其長(zhǎng)度為1時(shí)遞歸結(jié)束。單個(gè)元素被視為是已排好序的。實(shí)驗(yàn)代碼如下：#include<iostream.h>#include<string.h>template<classT>voidMerge(Tc[],Td[],intl,intm,intr){//把c[l:m]和c[m:r]歸并到d[l:r] inti,j,k; i=l;//第一段游標(biāo) j=m+1;//第二段游標(biāo) k=l;//結(jié)束游標(biāo) while((i<=m)&&(j<=r)) if(c[i]<=c[j]) d[k++]=c[i++]; elsed[k++]=c[j++]; if(i>m)for(intq=j;q<=r;q++) d[k++]=c[q]; elsefor(intq=i;q<=m;q++) d[k++]=c[q];}template<classT>voidMergePass(Tx[],Ty[],ints,intn){ //歸并大小為s的相鄰的段 inti=0; while(i<=n-2*s){ //歸并兩個(gè)大小為s的相鄰段 Merge(x,y,i,i+s-1,n-1); i=i+2*s; } //剩下不足兩個(gè)元素 if(i+s<n)Merge(x,y,i,i+s-1,n-1); elsefor(intj=i;j<=n-1;j++) //把最后一段復(fù)制到y(tǒng) y[j]=x[j];}template<classT>voidMergeSort(Ta[],intn){T*b=newT[n];ints=1;while(s<n){ MergePass(a,b,s,n); s+=s; MergePass(b,a,s,n); s+=s;}}intmain(){ intn,i,j=0; double*Input; cout<<"請(qǐng)輸入您要排序的元素個(gè)數(shù)"<<endl; cin>>n; Input=newdouble[100000];//定義排序數(shù)組 cout<<"請(qǐng)輸入您要排序的元素："<<endl; for(i=0;i<n;i++) cin>>*(Input+i); MergeSort(Input,n);//調(diào)用排序函數(shù) cout<<"排序后的數(shù)組元素為："<<endl; for(i=0;i<n;i++) { cout<<Input[i]<<""; j++; if(j%10==0) cout<<endl; } delete[]Input;//釋放內(nèi)存；}運(yùn)行結(jié)果如下圖所示：實(shí)驗(yàn)收獲與體會(huì)：通過(guò)歸并排序的實(shí)驗(yàn)對(duì)分治法在排序中的應(yīng)用有了更深刻的了解，與快速排序?qū)Ρ?，歸并排序相對(duì)較“穩(wěn)定”些。3.最大最小值問(wèn)題：每次將問(wèn)題分成大致相等的兩部分，分別在這兩部分中找出最大值與最小值，再將這兩個(gè)子問(wèn)題的解組合成原問(wèn)題的解，就可得到該問(wèn)題的分治算法。算法描述：如果MAX1和MIN1是I1中的最大和最小元素，MAX2和MIN2是I2中的最大和最小元素，MAX1和MAX2中的大者就是I中的最大元素MAX，MIN1和MIN2中的小者是I中的最小元素MIN。如果I只包含一個(gè)元素，則不需要作任何分割直接就可得到其解。實(shí)驗(yàn)代碼如下：#include"stdio.h"#defineN100voidmaxmin2(intA[],inti,intj,int*max,int*min){ intmid,max1,max2,min1,min2;if(j==i){ *max=*min=A[i]=A[j]; return;}if(j-1==i){ if(A[i]>A[j]) { *max=A[i]; *min=A[j]; } else { *max=A[j]; *min=A[i]; } return; }mid=(i+j)/2;maxmin2(A,mid+1,j,&max2,&min2);maxmin2(A,i,mid,&max1,&min1);if(max1>max2) *max=max1;else *max=max2;if(min1>min2) *min=min2;else *min=min1;}main(){ inti,n; intA[N]; intmax,min; printf("請(qǐng)輸入要比較的數(shù)據(jù)的個(gè)數(shù)："); scanf("%d",&n); for(i=0;i<n;i++) { printf("請(qǐng)輸入第%d個(gè)數(shù)",i+1); scanf("%d",&A[i]); } maxmin2(A,0,n-1,&max,&min);printf("最大值為：%d最小值為：%d",max,min);}運(yùn)行結(jié)果如下圖所示：實(shí)驗(yàn)收獲與體會(huì)：通過(guò)該實(shí)驗(yàn)對(duì)分治法掌握的更加透徹，明白了分治法發(fā)揮的作用。動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)對(duì)于一個(gè)多階段過(guò)程問(wèn)題，是否可以分段實(shí)現(xiàn)最優(yōu)決策，信賴于該問(wèn)題是否有最優(yōu)子結(jié)構(gòu)性質(zhì)，能否采用動(dòng)態(tài)規(guī)劃的方法，還要看該問(wèn)題的子問(wèn)題是否具有重疊性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解子問(wèn)題的重疊性質(zhì)：每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素動(dòng)態(tài)規(guī)劃一般方法1.找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征2.遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）3.以自底向上的方式計(jì)算出最優(yōu)值多段圖多段圖算法：112345678111009129732811116535524644211127ProcedureFGRAPH（E,k,n,P）//輸入是按段的順序給結(jié)點(diǎn)編號(hào)的，有n個(gè)結(jié)點(diǎn)的k段圖。E是邊集，c（i，j）是邊<i，j>的成本。P（1：k）是最小成本路徑。//realCOST(n),integer(n-1),P(k),r,j,k,nCOST(n)<-0forj<-n-1to1by-1do//計(jì)算COST（j）//設(shè)r是一個(gè)這樣的結(jié)點(diǎn)，（j，r）E且使c（j，r）+COST（r）取最小值COST（j）<-c（j，r）+COST（r）;D(j)<-r;Repeat//向前對(duì)j-1進(jìn)行決策//P（1）<-1;P（k）<-n;forj<-2tok-1do//找路徑上的第j個(gè)節(jié)點(diǎn)//P（j）<-D(P(j-1));repeat;endFGRAPH實(shí)驗(yàn)代碼如下：#include<iostream>usingnamespacestd;#defineMAX100#definen12//圖的總頂點(diǎn)數(shù)#definek5//圖的段數(shù)intc[n][n];voidinit(intcost[])//初始化圖{ inti,j; for(i=0;i<13;i++) { for(j=0;j<13;j++) { c[i][j]=MAX;//初始化每條邊長(zhǎng)度為MAX } } c[1][2]=9; c[1][3]=7; c[1][4]=3; c[1][5]=2; c[2][6]=4; c[2][7]=2; c[2][8]=1; c[3][6]=2; c[3][7]=7; c[4][8]=11; c[5][7]=11; c[5][8]=8; c[6][9]=6; c[6][10]=5; c[7][9]=4; c[7][10]=3; c[8][10]=5; c[8][11]=6; c[9][12]=4; c[10][12]=2;c[11][12]=5; //給每條邊賦值}voidfront(intcost[],intpath[],intd[])//向前遞推算法求多段圖的最短路徑{ intr,j,temp,min; for(j=0;j<=n;j++) cost[j]=0; for(j=n-1;j>=1;j--) { temp=0; min=c[j][temp]+cost[temp];//初始化當(dāng)前路徑長(zhǎng)度的最小值 for(r=0;r<=n;r++) { if(c[j][r]!=MAX) { if((c[j][r]+cost[r])<min)//找到最小的r，使c[j][r]+cost[r]取最小值 { min=c[j][r]+cost[r]; temp=r; } } } cost[j]=c[j][temp]+cost[temp]; d[j]=temp; }//向前對(duì)j-1進(jìn)行決策 path[1]=1;//第一段所取節(jié)點(diǎn) path[k]=n;//最后一段所取節(jié)點(diǎn) for(j=2;j<k;j++) path[j]=d[path[j-1]];//找到路徑上第j個(gè)節(jié)點(diǎn)}voidback(intbcost[],intpath1[],intd[])//使用向后遞推算法求多段圖的最短路徑{ intr,j,temp,min; for(j=0;j<=n;j++) bcost[j]=0; for(j=2;j<=n;j++) { temp=12; min=c[temp][j]+bcost[temp];//初始化當(dāng)前路徑長(zhǎng)度最小值 for(r=0;r<=n;r++) { if(c[r][j]!=MAX) { if((c[r][j]+bcost[r])<min)//找到最小的r使c[r][j]+bcost[r]最小 { min=c[r][j]+bcost[r]; temp=r; } } } bcost[j]=c[temp][j]+bcost[temp]; d[j]=temp; } path1[1]=1; path1[k]=n; for(inti=4;i>=2;i--) { path1[i]=d[path1[i+1]]; }//找出各段的節(jié)點(diǎn)}intmain(){intcur=-1;intj; intcost[13],d[12],bcost[13]; intpath[k];intpath1[k]; cout<<"\t\t\t\t多段圖問(wèn)題"<<endl; cout<<"\n\n";init(cost);front(cost,path,d);cout<<"向前遞推算法求得的最短路徑:\n\n"; for(inti=1;i<=5;i++) { if(i==5) cout<<path[i]<<""; else cout<<path[i]<<"->"; } cout<<"\n"; cout<<endl<<"最短路徑:"<<cost[1]<<endl; cout<<"\n";cout<<"向后遞推算法求得的最短路徑:\n\n"; back(bcost,path1,d); for(j=1;j<=5;j++) {if(j==5) cout<<path[j]<<""; else cout<<path1[j]<<"->"; } cout<<"\n"; cout<<endl<<"最短路徑:"<<bcost[12]<<endl; cout<<"\n";}運(yùn)行結(jié)果如下圖所示:實(shí)驗(yàn)收獲與體會(huì)：通過(guò)多段圖實(shí)驗(yàn)對(duì)動(dòng)態(tài)規(guī)劃的思想有了更深理解，動(dòng)態(tài)規(guī)劃與分治法類似，基本思想也是將待求解問(wèn)題分成若干個(gè)子問(wèn)題，但是分解得到的子問(wèn)題往往不是互相獨(dú)立的。回溯法實(shí)驗(yàn)回溯法在問(wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否滿足約束。如果不滿足，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。N皇后：基本思想：(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間，使N個(gè)皇后不在同行同列，對(duì)角線上；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。實(shí)驗(yàn)代碼如下：#include<iostream.h>#include"math.h"classQUEEN{public: friendintnQueen(int); private: boolPlace(intk); voidBacktrack(intt); intn,*x; longsum;};intnQueen(intn){ QUEENx; x.n=n; x.sum=0; int