最大字段和問(wèn)題動(dòng)態(tài)規(guī)劃法

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

2、列形如的子段和的最大值，當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)，其最大子段和為0。實(shí)驗(yàn)環(huán)境Turbo C 或 VC+實(shí)驗(yàn)學(xué)時(shí)2學(xué)時(shí)，必做實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)：程序中所用的數(shù)據(jù)都是儲(chǔ)存在數(shù)組當(dāng)中算法：蠻力法函數(shù) MaxSum(int a,int n,int &besti,int &bestj)分治法函數(shù) MaxSum(int a,int left,int right)動(dòng)態(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<<"請(qǐng)輸入整數(shù)序列的元素個(gè)數(shù)n:"<<e ndl;cin»n;cout<<"請(qǐng)輸入各元素的值(一共"<<*<&quo

4、t;個(gè)):"<<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) / 如果序列長(zhǎng)度為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<<"請(qǐng)輸入整數(shù)序列的元素個(gè)數(shù)n:"<<e ndl;cin»n;cout<<"請(qǐng)輸入各元素的值(一共"<<*<"個(gè)):"<<endl;for(m=1;m

7、<=n; m+)cin> >am;maxsum=MaxSum(a,1, n);cout<<"整數(shù)序列的最大子段和是："<<maxsum<<e ndl;3, 動(dòng)態(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<<"請(qǐng)輸入整數(shù)序列的元素個(gè)數(shù)n:"<<e ndl;cin»n;cout<<"請(qǐng)輸入各元素的值(一共"<<*<"個(gè)):"<<endl;for(m=1;m <=n; m+)cin> >am;MaxSum( n,a);實(shí)驗(yàn)結(jié)果1,蠻力法:2,分治法:3,動(dòng)態(tài)規(guī)劃法:實(shí)驗(yàn)體會(huì)同樣的問(wèn)題可以用不同的方法解決，一個(gè)好的算法是反復(fù)努力和重新修正的結(jié)果。