最大字段和問題動態(tài)規(guī)劃法

1、淮海工學(xué)院計算機(jī)工程學(xué)院實驗報告書課程名：算法分析與設(shè)計題 目： 實驗2 動態(tài)規(guī)戈U算法最大子段和問題班級：軟件081班學(xué)號：110831116姓 名：陳點點評語:成績： 指導(dǎo)教師： 批閱時間:算法分析與設(shè)計實驗報告-5 -實驗2動態(tài)規(guī)劃算法實驗?zāi)康暮鸵?1) 深刻掌握動態(tài)規(guī)劃法的設(shè)計思想并能熟練運用；(2) 理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復(fù)努力和重新修正的結(jié)果。(3) 分別用蠻力法、分治法和動態(tài)規(guī)劃法設(shè)計最大子段和問題的算法；(4) 比較不同算法的時間性能；(5) 給出測試數(shù)據(jù)，寫出程序文檔實驗內(nèi)容j給定由n個整數(shù)組成的序列(al, a2,an),求該序

2、列形如的子段和的最大值，當(dāng)所有整數(shù)均為負(fù)整數(shù)時，其最大子段和為0。實驗環(huán)境Turbo C 或 VC+實驗學(xué)時2學(xué)時，必做實驗數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：程序中所用的數(shù)據(jù)都是儲存在數(shù)組當(dāng)中算法：蠻力法函數(shù) MaxSum(int a,int n,int &besti,int &bestj)分治法函數(shù) MaxSum(int a,int left,int right)動態(tài)規(guī)劃法函數(shù) MaxSum(i nt n,i nt a)核心源代碼1, 蠻力法T(n)=0(n2)。#in clude<iostream.h>int MaxSum(int a,int n,int &bes

3、ti,int &bestj)int sum=0;int i,j,k;for(i=1;i<=n ;i+)int asum=0;for(j=i;j<=n;j+)asum+=aj;if(asum>sum)sum=asum;besti=i;bestj=j;return sum;void mai n()int n ,a100,m,i,j,maxsum;cout<<"請輸入整數(shù)序列的元素個數(shù)n:"<<e ndl;cin»n;cout<<"請輸入各元素的值(一共"<<*<&quo

4、t;個):"<<endl;for(m=1;m <=n; m+)cin> >am;maxsum=MaxSum(a, n,i,j);cout<<"整數(shù)序列的最大子段和是："<<maxsum<<e ndl;2, 分治法T( n)=0( nlog( n)。#in clude<iostream.h>int MaxSum(int a,int left,int right)int sum=0;if (left=right) / 如果序列長度為1，直接求解if (aleft>0)sum=aleft

5、;elsesum=0;elseint cen ter=(left+right)/2;in t leftsum=MaxSum(a,left,ce nter);int rightsum=MaxSum(a,ce nter+1,right);int s1=0;in t lefts=0;for(int i=center;i>=left;i-)lefts+=ai;if(lefts>s1)s1=lefts;int s2=0;int rights=O;for(i nt j=ce nter+1;j<=right;j+)rights+=aj;if(rights>s2)s2=rights;s

6、um=s1+s2;if(sum<leftsum)sum=leftsum; /合并，在 sum、leftsum 禾口 rightsum 中取較大者if(sum<rightsum)sum=rightsum;return sum;void mai n()int n ,a100,m,maxsum;cout<<"請輸入整數(shù)序列的元素個數(shù)n:"<<e ndl;cin»n;cout<<"請輸入各元素的值(一共"<<*<"個):"<<endl;for(m=1;m

7、<=n; m+)cin> >am;maxsum=MaxSum(a,1, n);cout<<"整數(shù)序列的最大子段和是："<<maxsum<<e ndl;3, 動態(tài)規(guī)劃法T(n)=0(n)。#in clude<iostream.h>void MaxSum(int n,int a)int sum=0;int b=0;for(i nt i=1;i<=n ;i+)if(b>0)b+=ai;elseb=ai;if(b>sum)sum=b;cout<<"整數(shù)序列的最大子段和是：&qu

8、ot;<<sum<<endl;void mai n()int n ,a100,m,maxsum;cout<<"請輸入整數(shù)序列的元素個數(shù)n:"<<e ndl;cin»n;cout<<"請輸入各元素的值(一共"<<*<"個):"<<endl;for(m=1;m <=n; m+)cin> >am;MaxSum( n,a);實驗結(jié)果1,蠻力法:2,分治法:3,動態(tài)規(guī)劃法:實驗體會同樣的問題可以用不同的方法解決，一個好的算法是反復(fù)努力和重新修正的結(jié)果。