3 演算法求最大子段和問題實驗報告格式 2

昆明理工大學資訊工程與自動化學院學生實驗報告

（ 2011 —2012 學年第 1 學期）

課程名稱：演算法設計與分析開課實驗室：信自樓應用、網路機房445 2011 年12月 21日

一、上機目的及內容

1.上機內容

給定有n個整數（可能有負整數）組成的序列（a1,a2,…,an），求改序列形如的子段和的最大值，當所有整數均為負整數時，其最大子段和為0。

2.上機目的

（1）複習資料結構課程的相關知識，實現課程間的平滑過渡；

（2）掌握並應用演算法的數學分析和後驗分析方法；

（3）理解這樣乙個觀點：不同的演算法能夠解決相同的問題，這些演算法的解題思路不同，複雜程度不同，解題效率也不同。

二、實驗原理及基本技術路線圖（方框原理圖或程式流程圖）

（1）分別用窮舉法、分治法和動態規劃法設計最大子段和問題的演算法；

（2）對所設計的演算法採用大o符號進行時間複雜性分析；

（3）上機實現演算法，並用計數法和計時法分別測算演算法的執行時間；

（4）通過分析對比，得出自己的結論。

蠻力演算法：o(n2)

分治演算法：o(nlog2(n))

動態規劃：o（n）

三、所用儀器、材料（裝置名稱、型號、規格等或使用軟體）

1臺pc及visual c++6.0軟體

四、實驗方法、步驟（或：程式**或操作過程）

#include""

int count1,count2,count3;//用於計數

分治法求最大字段問題,時間法度為：o(nlog2n

int maxsum(int a,int left,int right)

else

s2=0再求s2

rights=0;

for(j=center;j<=rights;j--)

sum=s1+s2計算3的最大欄位和

if(sum sum=leftsum;

if(sum sum=rightsum;

} return sum;

}蠻力演算法或窮舉法

int maxsumsp(int a,int n)

}return maxsum;

}動態規約

int maxsumdp(int n,int a)

return sum;

}int main()

; printf("please enter:\n");

i=maxsum(a,0,5);

printf("分治演算法：%d\n",i);

i=maxsumsp(a,6);

printf("蠻力演算法：%d\n",i);

i=maxsumdp(6,a);

printf("動規演算法：%d\n",i);

//時間複雜度

printf("\n\n時間複雜度：\n");

printf(" 蠻力演算法：o(n^2)\n");

printf(" 分治演算法：o(nlog2(n))\n");

printf(" 動規演算法：o(n)\n");

//計數

printf("\n\n計數：\n");

printf("分治演算法：%d\n",count1);

printf("蠻力演算法：%d\n",count2);

printf("動規演算法：%d\n",count3);

//計算時間

printf("\n\n計時：\n");

start=clock();

i=1000000;

while(i!=0)

end=clock();

usetime=end-start;

printf("分治演算法用時:%.f*10^(-6)ms\n",usetime);

start=clock();

i=1000000;

while(i!=0)

end=clock();

usetime=end-start;

printf("蠻力演算法用時:%.f*10^(-6)ms\n",usetime);

start=clock();

i=1000000;

while(i!=0)

end=clock();

usetime=end-start;

printf("動態規約演算法用時:%.f*10^(-6)ms\n",usetime);

return 0;

}五、實驗過程原始記錄( 測試資料、圖表、計算等)

流程圖圖1蠻力法實現流程

圖2動態規約實現流程圖

六、實驗結果、分析和結論（誤差分析與資料處理、成果總結等。其中，繪製曲線圖時必須用計算紙或程式執行結果、改進、收穫）

執行截圖

通過上機實驗，我了解並掌握了了蠻力法、分治法以及動態規約法的基本實現原理和過程，對它們有了乙個比較清楚的了解和認識。蠻力法是一種從一到n的執行過程，它沒有什麼演算法，實現起來相對較費力。然而分治法，是將其分為兩部分，這樣實現起來，相對就容易些，耗時也將減少；動態規約實現也是相對很好的，是一種比較好的方法。

實驗結果：通過實驗結果得到的結果可以看出實驗成功，本次實驗最難得演算法是分治演算法。動態規約法，不但執行的次數少，而且執行時間最短，是一種最優的方式。

實驗分析：通過時間複雜度的分析，可以看出動態規劃演算法是最優的，其次是分治演算法，最差的是蠻力演算法，從計數得到的結果與預期的結果一致。但是本次試驗出現的問題是在計時器裡顯示的資料分治演算法的用時比蠻力演算法的長，我認為造成這種結果的因素有兩個：

1、實驗資料特殊，資料樣本太小。

2、因為蠻力演算法程式只是乙個兩層迴圈，而分治演算法的**過長，導致我們的計時器得到的結果產生錯誤。

實驗結論：本次實驗成功得到結果，實驗順利完成。通過本次實驗我進一步加深了演算法的設計是多麼的重要，乙個好的演算法意味著很多東西，不僅節約空間，最重要的是我們等待的時間。

3 演算法求最大子段和問題實驗報告格式 2

n皇后問題演算法實驗報告

頁面置換演算法問題實驗報告

演算法實驗報告01揹包問題

3 演算法 求最大子段和問題 實驗報告格式 2

n皇后問題演算法實驗報告

頁面置換演算法問題實驗報告

演算法實驗報告01揹包問題

相關推薦

3 演算法求最大子段和問題實驗報告格式 2