算法分析與設計實驗報告學院：計算機科學與軟件學院班級：計131班姓名：張碩學號：133020實驗一利用分治算法，編程實現循環賽日程表安排問題一、實驗內容實現《網球循環賽》問題的分治算法，并進行算法時間復雜性分析。對實現的分治算法進行改進；對上述改進后算法進行時間復雜性分析，通過實驗結果分析對比，得出自己的結論和總結。設計的程序要滿足正確性，代碼中有關鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C++的模板，設計的程序通用性好，適合各種合理輸入，并能對不合理輸入做出正確的提示。二、實驗目的深刻理解并掌握“分治算法〃的設計思想；提高應用"分治算法〃設計技能；理解這樣一個觀點：用遞歸方法編寫的問題解決程序具有結構清晰，可讀性強等優點，且遞歸算法的設計比非遞歸算法的設計往往要容易一些，所以當問題本身是遞歸定義的，或者問題所涉及到的數據結構是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。三、程序清單(1)遞歸：#include<iostream.h>intp[128][128];voidfenpei(inta){intb=a/2;if(b>1){fenpei(b);for(inti=0;i<b;i++){for(intj=0;j<b;j++)p[i+b][j+b]=p[i][j];}for(i=0;i<b;i++){for(intj=0;j<b;j++)p[i+b][j]=p[i][j]+b;}for(i=0;i<b;i++){for(intj=0;j<b;j++)p[i][j+b]=p[i+b][j];}}else{p[0][0]=1;p[0][1]=2;p[1][0]=2;p[1][1]=1;}}intmain(){intnum;cout<<"請輸入參賽隊伍數：";cin>>num;fenpei(num);cout<<"";for(inti=1;i<num;i++){cout<<i<<""}cout<<endl;for(i=0;i<num;i++){for(intj=0;j<num;j++){cout<<p[i][j]<<"";}cout<<endl;}return0;}(2)非遞歸#include<iostream.h>intp[128][128];voidfenpei(inta){p[0][0]=1;p[0][1]=2;p[1][0]=2;p[1][1]=1;intb=2;while(b<a){for(inti=0;i<b;i++){for(intj=0;j<b;j++)p[i+b][j+b]=p[i][j];}for(i=0;i<b;i++){for(intj=0;j<b;j++)p[i+b][j]=p[i][j]+b;}for(i=0;i<b;i++){for(intj=0;j<b;j++)p[i][j+b]=p[i+b][j];}b=b*2;}}intmain(){intnum;cout<<"請輸入參賽隊伍數：";cin>>num;fenpei(num);cout<<"";for(inti=1;i<num;i++){cout<<i<<"";}cout<<endl;for(i=0;i<num;i++){for(intj=0;j<num;j++){cout<<p[i][j]<<"";cout<<endl;}return0;}四、調試步驟改正程序，無誤后運行程序，輸入測試數據，觀察輸出結果與預期結果，若有誤，則繼續改正程序，無誤后則程序完成。五、運行結果：遞歸法請輸入參賽隊伍數：1623456789101112131415TOC\o"1-5"\h\z234567891011121314151614365871091211141316154127856111291015161314321876512111091615141367812341314151691011125872143141316151091211856341215161314111291076543211615141312111091011121314151612345678912111413161521436587129101516131434127856111091615141343218765141516910111256781234131615109121165872143161314111291078563412151413121110987654321Pressanykeytocontinue非遞歸法請輸入參賽隊伍數：16123456789101112131415TOC\o"1-5"\h\z234567891011121314151614365871091211141316154127856111291015161314321876512111091615141367812341314151691011125872143141316151091211856341215161314111291076543211615141312111091011121314151612345678912111413161521436587129101516131434127856111091615141343218765141516910111256781234131615109121165872143161314111291078563412151413121110987654321Pressanykeytocontinue-六、分析與思考在輸入數據容量較龐大時，非遞歸算法要比遞歸算法速度快，但是遞歸算法在設計上較簡單，方便。實驗二利用動態規劃算法編程求解0-1背包問題一、實驗內容實現《0-1背包問題》問題的動態規劃法編程，動態規劃原理：動態規劃是一種將問題實例分解為更小的、相似的子問題，并存儲子問題的解而避免計算重復的子問題，以解決最優化問題的算法策略。并進行算法時間復雜性分析。對算法進行時間復雜性分析，通過實驗結果分析對比，得出自己的結論和總結。設計的程序要滿足正確性，代碼中有關鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C++的模板，設計的程序通用性好，適合各種合理輸入，并能對不合理輸入做出正確的提示。二、實驗目的熟練掌握動態規劃思想及教材中相關經典算法。掌握動態規劃算法求解問題的一般特征和步驟；使用動態規劃法編程，求解0/1背包問題。三、程序清單#include<iostream.h>intV[20][20],x[10];intmax(inta,intb){if(a>=b)returna;elsereturnb;}voidbag(intw[],intv[],intn,intC)//{inti,j;for(i=0;i<=n;i++)for(j=0;j<=C;j++)V[i][j]=0;for(i=1;i<=n;i++){for(j=1;j<=C;j++)if(j<w[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);}for(j=C,i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0；}}intmain(){intn,C,sum=0;intw[10],v[10];cout<<"請輸入物品數目："；cin>>n;cout<<"請輸入各物品重量："；for(inti=1;i<=n;i++){cin>>w[i];//x[i]=0;}cout<<"請輸入各物品價值："；for(i=1;i<=n;i++){cin>>v[i];//C+=v[i];}cout<<"請輸入限制重量："；cin>>C;bag(w,v,n,C);for(i=0;i<=n;i++){for(intj=0;j<=C;j++){cout<<V[i][j]<<'';}

cout<<'\n';}cout<<"所選商品序列為：”；for(i=1;i<=n;i++){cout<<x[i]<<"";if(x[i]==1)sum+=v[i];}cout<<"總價值為："<<sum<<endl;return0;}四、調試步驟修改調試程序直至能正確得出預期結果。五、運行結果■?E：謨面\'算法分折\2~1\施血或2.畋?7891011007891011000013000044444444444440045559999999990045551010101415151E0045551011111415161E004555101113141517IE?選商品序列為110總價值為ressanykeytocontinue六、分析與思考動態規劃法的時間復雜度較高，且后續結果是依靠前面結果產生的。實驗三利用貪心算法編程求解背包問題和TSP問題一、實驗內容實現背包問題的貪心算法編程，利用背包問題的三種貪心策略，（1）選擇價值最大的物品；(2)選擇重量最輕的物品；(3)選擇單位重量價值最大的物品。重點應用第三種貪心策略。對算法進行時間復雜性分析，通過實驗結果分析對比，得出自己的結論和總結。設計的程序要滿足正確性，代碼中有關鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，利用C++的模板，設計的程序通用性好，適合各種合理輸入，并能對不合理輸入做出正確的提示。二、實驗目的掌握動態規劃算法求解問題的一般特征和步驟；使用動態規劃法編程，求解背包問題和TSP問題。三、程序清單1、0-1背包#include<iostream.h>inty[10];doublex[10];voidtanxin1(intw[],intv[],intn,intC){〃價值最大intW=0,temp=0,v1[10];doubleV=0;for(inti=0;i<n;i++){x[i]=0;y[i]=i;v1[i]=v[i];}for(i=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(v1[j]>v1[i]){temp=v1[j];v1[j]=v1[i];v1[i]=temp;temp=y[i];y[i]=y[j];y[j]=temp;}}}for(i=0;i<n;i++){if((W+w[y[i]])<=C){x[y[i]]=1;W+=w[y[i]];V+=v1[i];}else{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;}}cout<<"價值最大優先法所選商品序列為："；for(i=0;i<n;i++){cout<<x[i]<<"";}cout<<"總價值為"<<V<<endl;}voidtanxin2(intw[],intv[],intn,intC){〃重量最輕intW=0,temp=0,v1[10];doubleV=0;for(inti=0;i<n;i++){x[i]=0;y[i]=i;v1[i]=v[i];}for(i=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(w[y[j]]<w[y[i]]){temp=v1[j];v1[j]=v1[i];v1[i]=temp;temp=y[i];y[i]=y[j];y[j]=temp;}}}for(i=0;i<n;i++){if((W+w[y[i]])<=C){x[y[i]]=1;W+=w[y[i]];V+=v1[i];}else{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;}}for(i=0;i<n;i++){cout<<x[i]<<"";}cout<<"總價值為"<<V<<endl;}voidtanxin3(intw[],intv[],intn,intC){〃價值/重量比最大intW=0,temp=0,v1[10];doubleV=0;for(inti=0;i<n;i++){x[i]=0;y[i]=i;v1[i]=v[i];}for(i=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(v1[j]/w[y[j]]>v1[i]/w[y[i]]){temp=v1[i];v1[i]=v1[j];v1[j]=temp;//temp=w[i];w[i]=w[j];w[j]=temp;temp=y[i];y[i]=y[j];y[j]=temp;}}//cout<<v[i]<<"";}for(i=0;i<n;i++){if((W+w[y[i]])<=C){x[y[i]]=1;W+=w[y[i]];V+=v1[i];}else{x[y[i]]=(double)(C-W)/w[y[i]];V+=v1[i]*x[y[i]];break;}}for(i=0;i<n;i++){cout<<x[i]<<"";}cout<<"總價值為"<<V<<endl;}intmain(){intn,C;intw[10],v[10];cout<<"請輸入物品數目："；cin>>n;cout<<"請輸入各物品重量："；for(inti=0;i<n;i++){cin>>w[i];}cout<<"請輸入各物品價值："；for(i=0;i<n;i++){cin>>v[i];}cout<<"請輸入限制重量："；cin>>C;for(i=0;i<n;i++){x[i]=0;}tanxin1(w,v,n,C);cout<<"重量最輕優先法所選商品序列為："；tanxin2(w,v,n,C);cout<<"價值重量比最大優先法所選商品序列為：";tanxin3(w,v,n,C);return0;}2、Tsp#include<iostream.h>intt[10][10];ints[10];intTsp(intn){inti,j,dis,temp,no=0,a=1,sym,sum=0,I;s[0]=0;sym=1;while(sym<n){dis=t[no][1];for(i=1;i<n;i++){I=0;for(j=0;j<sym;j++){if(i!=s[j])I++;}if(I==sym&&i!=no){if(dis>=t[no][i]){dis=t[no][i];temp=i;}}}sum+=dis;s[sym]=temp;sym+=1;no=temp;}sum+=t[no][0];s[sym]=0;returnsum;}voidmain(){inti,j,n,distance;cout<<"請輸入城市數目：”；cin>>n;cout<<"請輸入距離矩陣(行到列的距離,100為不可達):"<<endl;for(i=0;i<n;i++){for(j=0;j<n;j++)cin>>t[i][j];}distance=Tsp(n);cout<<"路徑為："；for(i=0;i<n;i++){cout<<s[i]<<"-->";}cout<<"0"<<endl;cout<<"總路徑長度為："<<distance<<endl;}四、調試步驟修改調試程序直至能正確得出預期結果。五、運行結果1、0-1背包■吒：謨面\'算法分折\*1\施血叭*1.畋.青輸入物品數目：7,青輸入各物品重量：2357141青輸入各物品價值：1051576183青輸入限制重量：10價值最大優先法所選商品序列為：15。1。。1。總價值為38亶量最輕優先法所選商品序列為：110011751總價值為第.5價值重量比最大優先法所選商品序列為：1。Q.6。11。總價值為43-■ressanykeytocontinue2、Tsp??E:謨面供哈'算法分忻\3~2\Debu酢3~2.effi?請輸入城市數目：5請輸入距離矩陣（行到列的距離,100為不可達）：1003326TOC\o"1-5"\h\z3100732371002523210036253100路徑為：0—>3—>2—>4—>1—>0總路徑長度為：14Pressanykeytocontinue六、分析與思考貪心算法雖然不能保證一定是最優解，但是在算法難度上較低，容易實現，所得解也可能為最優解。實驗四利用回溯法編程求解0-1背包問題一、實驗內容利用回溯法試設計一個算法求出0-1背包問題的解，也就是求出一個解向量xi（xi=0或1，xi=0表示物體i不放入背包，xi=1表示把物體i放入背包），使得盡量多的價值裝入背包。★數據輸入由文件input.txt提供輸入數據n，c，及每個物品的重量w[]和價值v[]。★結果輸出程序運行結束時，將最優解輸出到文件output.txt中。

輸入文件示例輸出文件示例input.txtoutput.txt12102015二、實驗目的掌握回溯法的設計思想；掌握解空間樹的構造方法，以及在求解過程中如何存儲求解路徑；考