求最大字段的三種方法——-動態(tài)規(guī)劃-蠻力-分治算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 2011 2012 學(xué)年 第 1 學(xué)期 ）課程名稱：算法設(shè)計與分析 開課實驗室：信自樓應(yīng)用、網(wǎng)絡(luò)機(jī)房444 2011 年12月 14日年級、專業(yè)、班計科092學(xué)號4姓名徐興繁成績實驗項目名稱最大子段和問題指導(dǎo)教師 吳晟教師評語該同學(xué)是否了解實驗原理：A.了解B.基本了解C.不了解該同學(xué)的實驗?zāi)芰Γ篈.強(qiáng) B.中等 C.差 該同學(xué)的實驗是否達(dá)到要求：A.達(dá)到B.基本達(dá)到C.未達(dá)到實驗報告是否規(guī)范：A.規(guī)范B.基本規(guī)范C.不規(guī)范實驗過程是否詳細(xì)記錄：A.詳細(xì)B.一般 C.沒有 教師簽名： 年 月 日一、上機(jī)目的及內(nèi)容1.上機(jī)

2、內(nèi)容給定有n個整數(shù)（可能有負(fù)整數(shù)）組成的序列（a1,a2,an），求改序列形如的子段和的最大值，當(dāng)所有整數(shù)均為負(fù)整數(shù)時，其最大子段和為0。2.上機(jī)目的（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符號進(jìn)行時間復(fù)雜性分析；（3）上機(jī)實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間；（4）通

3、過分析對比，得出自己的結(jié)論。1、窮舉法很簡單，就是一個兩層循環(huán)或者是三層循環(huán)就能得到結(jié)果； 分治法是版問題分化，求各個子問題的解，最后合并的到問題的解； 動態(tài)規(guī)劃最重要的是求出動態(tài)規(guī)劃函數(shù)，然后根據(jù)動態(tài)規(guī)劃函數(shù)寫算法。 2、根據(jù)自己程序的算法的分析得到時間復(fù)雜性如下蠻力算法：O(n2) 分治算法：O(nlogn) 動態(tài)規(guī)劃：O（n）3、實驗的計數(shù)和計時在運行結(jié)果中體現(xiàn)4、實驗的結(jié)論是：動態(tài)規(guī)劃算法是最優(yōu)的，其次是分治算法。三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）1臺PC及VISUAL C+6.0軟件四、實驗方法、步驟（或：程序代碼或操作過程）根據(jù)自己的分析寫源代碼如下：#incl

4、ude"stdio.h"#include"stdlib.h"#include"time.h"int c1,c2,c3;/用于計數(shù)int MaxSum(int a,int left ,int right)int i,j,sum,center,leftsum,rightsum,s1,s2,lefts,rights;sum=0;if(left=right)if(aleft>0)sum=aleft;else sum=0;elsecenter=(left+right)/2;leftsum=MaxSum(a,left,center);rig

5、htsum=MaxSum(a,center+1,right);s1=0;lefts=0;for(i=center;i>=left;i-)c1+;lefts+=ai;if(lefts>s1)s1=lefts;s2=0;rights=0;for(j=center+1;j<=right;j+)c1+;rights+=aj;if(rights>s2)s2=rights;sum=s1+s2;if(sum<leftsum)sum=leftsum;if(sum<rightsum)sum=rightsum;return sum;/蠻力算法/窮舉法int Manli(int

6、a,int n)int i,j,sum=0,max=0;for(j=0;j<n;j+) sum=0;for(i=j;i<n;i+) c2+;sum=sum+ai;if(max<sum)max=sum;return max;int dtgh(int n,int a)int sum=0;int b10,i;b0=a0;for(i=1;i<=n;i+)c3+;if(bi-1>0)bi=bi-1+ai;else bi=ai;if(bi>sum)sum=bi;return sum;int main()clock_t start,end; double usetime;

7、int n=6;int i;int b10;int a6=-20,11,-4,13,-5,-2;i=Manli(a,6);printf("蠻力算法：%dn",i);i=MaxSum(a,0,5);printf("分治算法：%dn",i);i=dtgh(6,a);printf("動規(guī)算法：%dn",i); /時間復(fù)雜度printf("nn時間復(fù)雜度：n");printf("蠻力算法：O(n2)n");printf("分治算法：O(nlog(n)n");printf("

8、動規(guī)算法：O(n)n");/計數(shù)printf("nn計數(shù)：n");printf("蠻力算法：%dn",c1);printf("分治算法：%dn",c2);printf("動規(guī)算法：%dn",c3);/計算時間printf("nn計時：n");start=clock();i=;while(i!=0)Manli(a,6);i-;end=clock();usetime=end-start;printf("蠻力算法用時 %.f*10(-6) 豪秒n", usetime);

9、start=clock();i=;while(i!=0)MaxSum(a,0,5);i-;end=clock();usetime=end-start;printf("分治算法用時 %.f*10(-6) 豪秒n", usetime);start=clock();i=;while(i!=0)dtgh(6,a);i-;end=clock();usetime=end-start;printf("動規(guī)算法用時 %.f*10(-6) 豪秒n", usetime);五、實驗過程原始記錄( 測試數(shù)據(jù)、圖表、計算等)請給出各個操作步驟的截圖和說明；實驗結(jié)果截圖如下：測試數(shù)

10、據(jù)為教材數(shù)據(jù)：a6=-20,11,-4,13,-5,-2;從截圖可以看出三種算法的結(jié)果都正確，代碼成功。第二組測試數(shù)據(jù)：a6= 20,11,-4,13,-5,-2;把-20改為20實驗數(shù)據(jù)再次說明代碼成功：六、實驗結(jié)果、分析和結(jié)論（誤差分析與數(shù)據(jù)處理、成果總結(jié)等。其中，繪制曲線圖時必須用計算紙或程序運行結(jié)果、改進(jìn)、收獲）實驗結(jié)果：通過實驗結(jié)果得到的結(jié)果可以看出實驗成功，本次實驗最難得算法是分治算法，但分治算法的偽代碼在教材上有，我通過教材的偽代碼，我試著寫了自己的代碼。實驗分析：通過時間復(fù)雜度的分析，可以看出動態(tài)規(guī)劃算法是最優(yōu)的，其次是分治算法，最差的是蠻力算法，從計數(shù)得到的結(jié)果與預(yù)期的結(jié)果一致。但是本次試驗出現(xiàn)的問題是在計時器里顯示的數(shù)據(jù)分治算法的用時比蠻力算法的長，我認(rèn)為造成這種結(jié)果的因素有兩個：1、實驗數(shù)據(jù)特殊，數(shù)據(jù)樣本太小。2、因為蠻力算法程序只是一個兩層循環(huán)，而分治算法的代碼過長，導(dǎo)致我們的計時器得到的結(jié)果產(chǎn)生