最大子段和問題實(shí)驗(yàn)報(bào)告

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

2、分：按照平衡子問題的原那么，將序列a1, a2,，an劃分成長(zhǎng)度相同的兩個(gè)子序列a1, a2, ., an/2和an/2+1,ad ;(2) 求解子問題：對(duì)與劃分階段的情況和可遞歸求解，情況需要分別計(jì)算s1=maxE ；= ak(1=i=n/2),s2=max 刀=n+1 ak (n/2+1=j0 時(shí)，bj=bj -1+aj。2、當(dāng) bj-10 時(shí)，bj=aj然后做遞歸操作求出最大子段和；5. 實(shí)驗(yàn)結(jié)果蠻力法#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 請(qǐng)輸入序

6、列子段.1!. )for (j = 0;j n; j+)sum = MaxSum(b, 0, 5); cout sum i;return 0;動(dòng)態(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. 討論和分析在一開始做最大子段問題的實(shí)驗(yàn)的時(shí)候， 對(duì)于蠻力法和分治法的理解還是可以的， 但是對(duì)于 動(dòng)態(tài)規(guī)劃法的理解還不是那么明確透徹， 通過網(wǎng)上的一些解釋和結(jié)合自己書本上的知識(shí)， 對(duì) 動(dòng)態(tài)規(guī)劃法得到了進(jìn)一步的理解，接下來是三種算法時(shí)間性能的比擬：蠻力法：時(shí)間復(fù)