算法分析與設(shè)計-實驗三-最大子段和問題

1、昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 201 201 學(xué)年 第 1 學(xué)期 ）課程名稱：算法分析與設(shè)計 開課實驗室： 年 月 日年級、專業(yè)、班 學(xué)號 姓名 成績實驗項目名稱最大子段和問題指導(dǎo)教師 教師評語該同學(xué)是否了解實驗原理：A.了解B.基本了解C.不了解該同學(xué)的實驗?zāi)芰Γ篈.強 B.中等 C.差 該同學(xué)的實驗是否達到要求：A.達到B.基本達到C.未達到實驗報告是否規(guī)范：A.規(guī)范B.基本規(guī)范C.不規(guī)范實驗過程是否詳細記錄：A.詳細B.一般 C.沒有 教師簽名： 年 月 日一、上機目的及內(nèi)容1.上機內(nèi)容給定有n個整數(shù)（可能有負整數(shù)）組成的序列（a1,a2,an），求改序列形如的子段和的

2、最大值，當(dāng)所有整數(shù)均為負整數(shù)時，其最大子段和為0。2.上機目的（1）復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識，實現(xiàn)課程間的平滑過渡；（2）掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復(fù)雜程度不同，解題效率也不同。二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）分別用窮舉法、分治法和動態(tài)規(guī)劃法設(shè)計最大子段和問題的算法；（2）對所設(shè)計的算法采用大O符號進行時間復(fù)雜性分析；（3）上機實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間；（4）通過分析對比，得出自己的結(jié)論。窮舉法是用一個二維數(shù)組將從i到j(luò)的和都記錄下來，再比較各元素

3、的大小，時間復(fù)雜性為O（n2），分治法的設(shè)計思想是不斷將問題為子問題，然后求解子問題，最后對解進行合并，時間復(fù)雜性為O(nlogn)，動態(tài)規(guī)劃法的設(shè)計思想是將問題劃分為若干個子問題，時間復(fù)雜度為O(n)。分治法流程圖：窮舉法流程圖： 動態(tài)規(guī)劃法流程圖：三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）1臺PC及VISUAL C+6.0軟件四、實驗方法、步驟（或：程序代碼或操作過程）程序代碼：/窮舉法#includevoid main()int i,j,n;int num100,a100,max;printf(ttt 最大子段和問題（窮舉法）nn); printf(請輸入所要求最大字段和整數(shù)

4、的個數(shù):n);scanf(%d,&n);printf(請分別輸入這%d個整數(shù)的值:n,n);for(i=0;in;i+)scanf(%d,&numi);max=num0;for(i=1;i=n;i+)if(maxnumi)max=numi;a1=num1;for(i=1;i=n;i+)for(j=i+1;j=n;j+)ai+=numj;if(maxai)max=ai;if(max0)max=0;printf(這%d個整數(shù)組成的序列的最大子段和是：%dn,n,max);/分治法#includeint MaxSum(int a,int left,int right) int sum=0; if (

5、left=right) if (aleft0) sum=aleft; else sum=0; else int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=MaxSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i=left;i-) lefts+=ai; if(leftss1) s1=lefts; int s2=0; int rights=0; for(int j=center+1;js2) s2=rights; sum=

6、s1+s2; if(sumleftsum)sum=leftsum; if(sumrightsum)sum=rightsum; return sum;void main() int n,a100,m,maxsum; printf(ttt 最大子段和問題（分治法）nn); printf(請輸入所要求最大字段和整數(shù)的個數(shù):n); scanf(%d,&n); printf(請分別輸入這%d個整數(shù)的值:n,n); for(m=1;m=n;m+) scanf(%d,&am); maxsum=MaxSum(a,1,n);printf(這%d個整數(shù)組成的序列的最大子段和是：%dn,n,maxsum);/動態(tài)規(guī)

7、劃法#includevoid MaxSum(int n,int a) int sum=0; int b=0; for(int i=1;i0)b+=ai; else b=ai; if(bsum)sum=b; printf(這%d個整數(shù)組成的序列的最大子段和是：%dn,n,sum); void main() int n,a100,m,maxsum;printf(ttt最大子段和問題（動態(tài)規(guī)劃法）nn); printf(請輸入所要求最大字段和整數(shù)的個數(shù):n); scanf(%d,&n); printf(請分別輸入這%d個整數(shù)的值:n,n); for(m=1;m=n;m+) scanf(%d,&am);MaxSum(n,a);五、實驗過程原始記錄( 測試數(shù)據(jù)、圖表、計算等)程序運行截圖：六、實驗結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時必須用計算紙或程序運行結(jié)果、改進、收獲）這次實驗我們是用窮舉法、