算法分析與設計實驗2 動態(tài)規(guī)劃算法

1、淮海工學院計算機工程學院實驗報告書課程名：算法分析與設計題日：實驗2動態(tài)規(guī)劃算法班級：*學號：201*姓名：*實驗2動態(tài)規(guī)劃算法一、實驗目的和要求深刻掌握動態(tài)規(guī)劃法的設計思想并能熟練運用；理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復努 力和重新修正的結(jié)果；分別用蠻力法、分治法和動態(tài)規(guī)劃法設計最大子段和問題的算法；比較不同算法的時間性能；給出測試數(shù)據(jù)，寫出程序文檔。二、實驗內(nèi)容給定由n個整數(shù)(可能有負整數(shù))組成的序列(a1,a2,an)，求該序列形如習k=,jak 的子段和的最大值，當所有整數(shù)均為負整數(shù)時，其最大子段和為0。實驗環(huán)境Turbo C 或 VC+三、實驗學時2

2、學時，必做實驗四、核心源代碼1、蠻力法：#includeint MaxSum(int a,int n)int sum=0;int i,j;for(i=1;i=n;i+)int asum=0;for(j=i;jsum)sum=asum;return sum;void main()int n,a100,m,i,j,maxsum;cout用蠻力法求最大子段和：nendl;cout請輸入整數(shù)序列的元素個數(shù)：n;cout請輸入各元素的值：endl;for(m=1;mam;maxsum=MaxSum(a,n);coutn最大子段和是：maxsumendl;2、分治法：#includeint MaxSum(

3、int a,int left,int right)int sum=0;if (left=right)if(aleft0)sum=aleft;elsesum=0;elseint 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+

4、1;js2)s2=rights;sum=s1+s2;if(sumleftsum) sum=leftsum;if(sumrightsum) sum=rightsum;return sum;void main()int n,a100,m ,maxsum;cout請輸入整數(shù)序列的元素個數(shù)：n;cout請輸入各元素的值：endl;for(m=1;mam;maxsum=MaxSum(a,1,n);cout最大子段和是：maxsumendl;3、動態(tài)規(guī)劃法：#includevoid MaxSum(int a,int n)int sum=0;int b=0;for(int i=1;i0)b+=ai;elseb=ai;if(bsum)sum=b;coutn最大子段和是： sumendl;void main()int n,a100,m ;cout用動態(tài)規(guī)劃法求最大子段和：nendl;cout請輸入整數(shù)序列的元素個數(shù)：n;cout請輸入各元素的值：endl;for(m=1;m=n;m+)MaxSum(a,n);六、實驗結(jié)果1、蠻力法：2、分治法： * E:C+ 4-Debu.exeW_回啊分治法求最大子段和:青輸入整數(shù)序列的元素個數(shù):