《算法分析與設計實驗2動態(tài)規(guī)劃算法》由會員分享，可在線閱讀，更多相關《算法分析與設計實驗2動態(tài)規(guī)劃算法（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、淮海工學院計算機工程學院
實驗報告書
課程名：
《算法分析與設計》
題
日：
實驗2動態(tài)規(guī)劃算法
班
級：
*******
學
號：
201*******
姓
名：
***
實驗2動態(tài)規(guī)劃算法
一、 實驗目的和要求
(1) 深刻掌握動態(tài)規(guī)劃法的設計思想并能熟練運用；
(2) 理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復努 力和重新修正的結果；
(3) 分別用蠻力法、分治法和動態(tài)規(guī)劃法設計最大子段和問題的算法；
(4) 比較不同算法的時間性能；
(5) 給出測試數(shù)據(jù)，寫出程序文檔。
二、 實驗內(nèi)容
給定由
2、n個整數(shù)(可能有負整數(shù))組成的序列(a1,a2,…,an)，求該序列形如習[k=,j]ak 的子段和的最大值，當所有整數(shù)均為負整數(shù)時，其最大子段和為0。
實驗環(huán)境
Turbo C 或 VC++
三、 實驗學時
2學時，必做實驗
四、 核心源代碼
1、蠻力法：
#include
int MaxSum(int a[],int n)
{
int sum=0;
int i,j;
for(i=1;i<=n;i++)
{
int asum=0;
for(j=i;j<=n;j++)
{
asum+=a[j];
if(asum>sum)
{
su
3、m=asum;
}
}
}
return sum;
}
void main()
{
int n,a[100],m,i,j,maxsum;
cout<<"用蠻力法求最大子段和："<<'\n'<>n;
cout<<"請輸入各元素的值："<>a[m];
maxsum=MaxSum(a,n);
cout<<'\n'<<"最大子段和是："<
4、int MaxSum(int a[],int left,int right)
{
int sum=0;
if (left==right)
{
if(a[left]>0)
sum=a[left];
else
sum=0;
}
else
{
int 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+
5、=a[i];
if(lefts>s1) s1=lefts;
}
int s2=0;
int rights=0;
for(int j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum
6、dl;
cin>>n;
cout<<"請輸入各元素的值："<>a[m];
maxsum=MaxSum(a,1,n);
cout<<"最大子段和是："<
void MaxSum(int a[],int n)
{
int sum=0;
int b=0;
for(int i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
cout
7、<<'\n'<<"最大子段和是："<< sum<>n;
cout<<"請輸入各元素的值："<
8、值：
12345 -6 103
成大子段和是：15
Press any key to continue
3、動態(tài)規(guī)劃法:
七、實驗體會
***********************************************************************
***************************************************************************
*************************************************************************** **
算法分析與設計實驗2動態(tài)規(guī)劃算法
