最大子段和問題實驗報告

1、實驗四最大子段和問題1掌握動態(tài)規(guī)劃的設計思想并能熟練運用；2理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復努力和 重新修正的結果；1分別用蠻力法、分治法和動態(tài)規(guī)劃法設計最大子段和問題的算法;2比擬不同算法的時間性能；3給出測試數(shù)據(jù)，寫出程序文檔；3. 實驗設備和軟件環(huán)境操作系統(tǒng)： Windows 7 64x開發(fā)工具：Visual Studio 20224. 實驗步驟以下實驗數(shù)據(jù)都是以數(shù)組 a=-2, 11, -4, 13, -5, -2為例子；蠻力法蠻力法是首先通過兩個for循環(huán)去求出所有子段的值，然后通過if語句查找出maxsum返回子序列的最大子段和；分治法(1) 劃

2、分：按照平衡子問題的原那么，將序列a1, a2,，an劃分成長度相同的兩個子序列a1, a2, ., an/2和an/2+1,ad ;(2) 求解子問題：對與劃分階段的情況和可遞歸求解，情況需要分別計算s1=maxE ；= ak(1=i=n/2),s2=max 刀=n+1 ak (n/2+1=j0 時，bj=bj -1+aj。2、當 bj-10 時，bj=aj然后做遞歸操作求出最大子段和；5. 實驗結果蠻力法#in elude #in elude using namespaeestd;/* */int manlifa( int a, int x)int i, j,sum=0,maxsum=0;

3、for (i = 0; i x; i+)for (j = i+1; j sum)sum = ai;if(summaxsum)maxsum = sum;int main()int y,sum;int a = -20, 11, -4, 13, -5, -2 ；int c = sizeof (a)/ sizeof (int );sum = man lifa(a, c);cout y;return 0;分治法#in clude#in cludeusing namespacestd;int MaxSum(nt a, int left , int right )int sum = 0, midSum =

4、0, leftSum = 0, rightSum = 0;int center, s1, s2, lefts, rights;if ( left = right )sum = a left ;elsecenter = ( left + right ) / 2;leftSum = MaxSum( a, left , center);rightSum = MaxSum( a, center + 1, right ); s1 = 0;lefts = 0;for ( int i = center; i =left ; i-)lefts +=ai;if (lefts s1) s1 = lefts;s2

5、= 0;rights = 0;for ( int j = center + 1; j s2) s2 = rights;midSum = si + s2;if (midSum leftSum) sum = leftSum;elsesum = midSum;if (sum rightSum) sum = rightSum;return sum;int main()/*i nt sum;/int a = -20, 11, -4, 14, -5, -2 ;sum1 = MaxSum(a, 0, 5);cout sum1 en dl;*/int j,n;int b100;cout n;cout 請輸入序

6、列子段.1!. )for (j = 0;j n; j+)sum = MaxSum(b, 0, 5); cout sum i;return 0;動態(tài)規(guī)劃法#in elude using namespacestd;int MaxSum(nt n, int * a)int sum = 0, b = 0;for ( int i = 1; i = n; i+) sum = b;return sum;int a = -2, 11, -4, 13, -5, -2 ;for ( int i = 0; i6; i+) cout ai cout en dl;cout 數(shù)組a的最大連續(xù)子段和為： MaxSum(6, a) k;return 0;6. 討論和分析在一開始做最大子段問題的實驗的時候， 對于蠻力法和分治法的理解還是可以的， 但是對于 動態(tài)規(guī)劃法的理解還不是那么明確透徹， 通過網(wǎng)上的一些解釋和結合自己書本上的知識， 對 動態(tài)規(guī)劃法得到了進一步的理解，接下來是三種算法時間性能的比擬：蠻力法：時間復