算法設計與分析試驗報告

學生學號0121010680524實驗課成績武漢理工大學學生實驗報告書實驗課程名稱《算法設計與分析》開課學院計算機科學與技術(shù)學院指導老師姓名何九周學生姓名王鵬學生專業(yè)班級軟件10042012—2013學年第1學期實驗課程名稱：算法設計與分析實驗項目名稱分治法應用及設計實驗成績實驗者王鵬專業(yè)班級軟件1004組別同組者實驗日期年月日第一部分：實驗分析與設計（可加頁）實驗內(nèi)容描述（問題域描述）實驗描述：利用分治法，解決檢索和排序中的兩個問題，在計算機上實現(xiàn)，同時進行時間復雜性分析。本實驗是綜合型、設計型實驗，在實驗中需要綜合運用《數(shù)據(jù)結(jié)構(gòu)》中的遞歸方法和樹的知識；《程序設計》中的數(shù)組、條件控制、循環(huán)控制和《算法設計與分析》中的分治法、計算時間的漸進表示和算法的時間復雜性分析等等方面的知識。實驗內(nèi)容：利用分治法，寫一個二分檢索的遞歸算法，并利用任何一種語言，在計算機上實現(xiàn)，同時進行時間復雜性分析。用分治法，實現(xiàn)對n個元素進行排序的算法，并進行時間復雜性分析。實驗要求：首先要對實驗內(nèi)容進行描述，用偽代碼設計算法，并對算法在最好，最差和平均情況下的時間復雜性進行分析，然后C/C++或JAVA語言編寫程序?qū)λ惴▽崿F(xiàn)，同時用具用代表性的數(shù)據(jù)進行測試，實驗后，進行實驗總結(jié)，描述設計過程步驟及各步驟含義。其中實驗內(nèi)容1要求用遞歸方法實現(xiàn)，實驗內(nèi)容2要求用非遞歸方式實現(xiàn)。實驗基本原理與設計（包括實驗方案設計，實驗手段的確定，試驗步驟等，用硬件邏輯或者算法描述）實驗一代碼：#include<stdio.h>//比較x和yintcompare(intx,inty){if(x<y)return-1;elseif(x==y)return0;elsereturn1;}//二分查找(折半查找)的遞歸(迭代)算法，返回查找到的值在數(shù)組中的位置下標intBinSearch(intlist[],intsearchnum,intLeft,intRight){intmiddle;if(Left<=Right){middle=(Left+Right)/2;printf("middle=%d\n",middle);switch(compare(list[middle],searchnum)){case-1:returnBinSearch(list,searchnum,middle+1,Right);case0:returnmiddle;case1:returnBinSearch(list,searchnum,Left,middle-1);}}}voidmain(){intlist[10]={1,2,3,4,5,6,7,8,9,10};intsearchnum=5;intLeft=0;intRight=9;intnum=BinSearch(list,searchnum,Left,Right);printf("返回%d\n",num);}實驗二代碼：#include<iostream>#include<cstdlib>usingnamespacestd;intmerge(intc[],intd[],intl,intm,intr){inti=l,j=m+1,k=l,q;while(i<=m&&j<=r){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m)for(q=j;q<=r;q++)d[k++]=c[q];if(j>r)for(q=i;q<=m;q++)d[k++]=c[q];return0;}intmergePass(intx[],inty[],ints,intn){inti=0,j;while(i<=n-2*s){//合并大小為S的相鄰子段merge(x,y,i,i+s-1,i+2*s-1);i+=2*s;}//剩下的元素個數(shù)少于2sif(i+s<n)merge(x,y,i,i+s-1,n-1);elsefor(j=i;j<=n-1;j++)y[j]=x[j];return0;}//合并數(shù)組intmergeSort(inta[],intn){ints=1;int*b=newint[n];//int*b=(int*)malloc(n*sizeof(int));//動態(tài)的給b分配n個int類型空間while(s<n){mergePass(a,b,s,n);//合并到數(shù)組bs+=s;mergePass(b,a,s,n);s+=s;}return0;}intmain(){inti,n;cout<<"請輸入數(shù)組元素的個數(shù)：";cin>>n;int*a=newint[n];cout<<"請輸入數(shù)組a的元素:";for(i=0;i<n;i++)cin>>a[i];mergeSort(a,n);cout<<endl;for(i=0;i<n;i++)cout<<a[i]<<"";return0;}主要儀器設備及耗材個人計算機,Visualstudio2012第二部分：實驗調(diào)試與結(jié)果分析（可加頁）調(diào)試過程（包括調(diào)試方法描述、實驗數(shù)據(jù)記錄，實驗現(xiàn)象記錄，實驗過程發(fā)現(xiàn)的問題等）實驗一：調(diào)試方法：直接在函數(shù)體內(nèi)定義測試，負責初始化查找的有序表。沒有設定好中值點，忘記在兩個端點的差值上增加左邊端點的內(nèi)容。遞歸調(diào)用時，錯誤使用了邊界條件，導致結(jié)果不正確。實驗二：調(diào)試方法：直接在函數(shù)體內(nèi)定義測試，負責初始化分治法排序的列表。對于算法沒有理解透徹，沒有用好邊界條件。對于算法的交換應該是首先保存舊值，在第一次也就是從右側(cè)開始時把右側(cè)的值傳至左側(cè)，把左側(cè)的值保存，用來給從左側(cè)開始進行的查找。實驗結(jié)果及分析（包括結(jié)果描述、實驗現(xiàn)象分析、影響因素討論、綜合分析和結(jié)論等）（1）查找均為正確結(jié)果。時間復雜度：O(nlogn)空間復雜度：無需大量增加空間，仍為O(n)（2）時間復雜度：最好：O(n)平均：O(nlog2n)最差：O(n2)空間復雜度：O(n)實驗小結(jié)、建議及體會初次涉及這方面的編程，由開始的無所適從，到慢慢有了頭緒，直到完成。每到遇到難題，心中不免煩悶，每獲成功，又不由有些自豪。編程的樂趣莫過于此。實驗課程名稱：算法設計與分析實驗項目名稱動態(tài)規(guī)劃算法應用及設計實驗成績實驗者王鵬專業(yè)班級軟件1004組別同組者實驗日期年月日第一部分：實驗分析與設計（可加頁）實驗內(nèi)容描述（問題域描述）實驗描述：將動態(tài)規(guī)劃算法應用于貨郎擔問題和工程中的資金分配問題的求解，設計出高效的算法。本實驗是綜合型、設計型實驗，在實驗中需要綜合運用《離散數(shù)學》中的數(shù)理邏輯、圖；《數(shù)據(jù)結(jié)構(gòu)》中的集合、隊列、樹；《程序設計》中的數(shù)組、條件控制、循環(huán)控制、指針、結(jié)構(gòu)體和《算法設計與分析》中的動態(tài)規(guī)劃算法、多段圖、以及計算時間的漸進表示和算法的時間復雜性分析等等方面的知識。實驗內(nèi)容：1）利用動態(tài)規(guī)劃思想，求貨郎擔問題，并利用任何一種語言，在計算機上實現(xiàn)，同時進行時間復雜性分析。2）已知資金總數(shù)為a（萬元）,工程數(shù)n，以及利潤值g(i,j)(表示對工程i投資j萬元所獲得的利潤，其中，且j只取整數(shù))，試用動態(tài)規(guī)劃方法求出如何分配資金才能使獲得的利潤最大（資金的分配以萬元為單位）。實驗要求首先要對實驗內(nèi)容進行描述，用SPARK語言設計算法，然后C/C++或JAVA語編寫程序?qū)λ惴▽崿F(xiàn)，同時用具用代表性的數(shù)據(jù)(給3組典型輸入數(shù)據(jù))進行測試，實驗后，進行實驗總結(jié)，描述設計過程步驟及各步驟含義。其中實驗內(nèi)容1）還要求對算法的時間復雜性進行分析，實驗內(nèi)容2）還要求寫出動態(tài)規(guī)劃遞推關(guān)系式。實驗基本原理與設計（包括實驗方案設計，實驗手段的確定，試驗步驟等，用硬件邏輯或者算法描述）實驗一：算法分析，比較次數(shù)的遞推關(guān)系式：C(n)=1n=2C(n)=2C(n/2)+2n>2求解關(guān)系式：C(n)=3n/2–2當且僅當n是2的冪時的最優(yōu)解。否則，C(n)取其遞推式向上取整數(shù)。代碼：#include<iostream>#include<math.h>#defineNUM4usingnamespacestd;int num=(int)pow(2,NUM-1);classsubset{public: boolcontains[NUM-1]; //除了開始結(jié)點外，包含哪個城市就把相應的contains設置為1； boolis_in(inti) { i--; if(contains[i])returntrue; elsereturnfalse; }//判斷第i個城市是否在子集中，如果在返回true，否則false；};//所有節(jié)點城市的子集。voidset_ct(subset*s,intbegin,intend,intprocess){ if(NUM-2==process) { s[begin].contains[process]=false; s[end].contains[process]=true; } else { intmiddle=(end+begin)/2; inti; for(i=begin;i<=middle;i++) s[i].contains[process]=false; set_ct(s,begin,middle,process+1); for(i=middle+1;i<=end;i++) s[i].contains[process]=true; set_ct(s,middle+1,end,process+1); }}//用遞歸的方法初始化子集結(jié)點；intcombian(inta,intb){ if(b>=0&&a>=b) { if(0==b||a==b)return1; else { if(a-b<b)b=a-b; //組合數(shù)的性質(zhì)； inti,result=1; for(i=a-b+1;i<=a;i++) result*=i; for(i=2;i<=b;i++) result/=i; returnresult; } } elsereturn-1;}//組合數(shù)（a選b）的計算,數(shù)據(jù)合法返回正確的值，否則返回-1，intget_h(bool*c,intn){ inti,result=0; for(i=0;i<NUM-1;i++) { if(i!=n&&c[i])result+=(int)pow(2,NUM-2-i); } returnresult;}//計算table_d表的橫坐標horizontal，intmain(){ int **cities=newint*[NUM]; //存儲個城市之間的代價矩陣 int **table_d=newint*[NUM]; //存儲動態(tài)距離表 int **table_p=newint*[NUM]; //存儲動態(tài)結(jié)點選在表 subset *sbst=newsubset[num]; //所有城市節(jié)點的子集。 int i,j,k,temp,horizontal; for(i=0;i<NUM;i++) { cities[i]=newint[NUM]; table_d[i]=newint[num]; table_p[i]=newint[num]; for(j=0;j<NUM;j++) cin>>cities[i][j]; table_d[i][0]=cities[i][0]; //初始化距離表的第一列 } set_ct(sbst,0,num-1,0); for(j=1;j<num-1;j++) { for(i=1;i<NUM;i++) { if(!sbst[j].contains[i-1]) { table_d[i][j]=32767; for(k=1;k<NUM;k++) { if(sbst[j].contains[k-1]) { horizontal=get_h(sbst[j].contains,k-1); //計算出此時的table_d的橫坐標。 temp=cities[i][k]+table_d[k][horizontal]; if(temp<table_d[i][j]){ table_d[i][j]=temp; //將最短距離存入距離表 table_p[i][j]=k; //將選擇的結(jié)點存入節(jié)點表； } } }//對子集中的每一個元素計算各自被選擇時的距離，然后選擇最少的。 }//子集j中不包含i時 }//掃描該列的每一行 }//逐列掃描； table_d[0][num-1]=32767; for(i=NUM-1;i>0;i--){ horizontal=get_h(sbst[num-1].contains,i-1); temp=cities[0][i]+table_d[i][horizontal]; if(temp<table_d[0][num-1]) { table_d[0][num-1]=temp; table_p[0][num-1]=i; } } cout<<"Theshortestdistanceis:"<<table_d[0][num-1]<<endl; cout<<"Thepathis:0->"<<table_p[0][num-1]<<"->"; temp=table_p[0][num-1]; horizontal=get_h(sbst[num-1].contains,temp-1); for(i=1;i<NUM-1;i++){ cout<<table_p[temp][horizontal]<<"->"; temp=table_p[temp][horizontal]; horizontal=get_h(sbst[horizontal].contains,temp-1); } cout<<0; return0;}實驗二：算法分析，求出一個a的分劃x1,x2,…..,xn,0≦xi≦a,且∑xi≦a,使得以下式表示的利潤為最大： n G(a)=∑Gi(xj)0≦xj≦ai=1 i=1其中Gi(xj)是把資源xj分配給第I項工程能獲得的最大利潤。代碼：#include<iostream>#include<stdlib.h>usingnamespacestd;#define N5 //工程數(shù)；#defineA10 //資金總數(shù);intmain(){ int **g=newint*[N]; //NXA的矩陣，存儲對工程i投資j萬元的利潤； int **table=newint*[N+1]; //(N+1)X(A+1)矩陣,存入動態(tài)決策表； int **cash=newint*[N]; //NXA的矩陣，存儲各工程的投資數(shù) int *result=newint[N]; //記錄最終結(jié)果，用于輸出； int i,j,k,temp; for(i=0;i<N;i++){ cash[i]=newint[A]; g[i]=newint[A]; table[i]=newint[A+1]; table[i][0]=0; //table的第一列賦0； }//給各矩陣分配空間； table[N]=newint[A+1]; table[N][0]=0; for(i=A;i>0;i--)table[0][i]=0; //table第一行賦0； cout<<"Theprofitofj*10000yuaninvesttoprojectiare:"<<endl; for(i=0;i<N;i++){ for(j=0;j<A;j++){ g[i][j]=rand()%5; cout<<g[i][j]<<'\t'; } cout<<endl; }//為了方便，隨機給利潤矩陣g賦值； cout<<endl; for(i=1;i<=N;i++) //對每一列： for(j=1;j<=A;j++){ //對該列的每一個元素 table[i][j]=table[i-1][j]; cash[i-1][j-1]=0; for(k=1;k<=j;k++){temp=table[i-1][j-k]+g[i-1][k-1];//有遞