1、淮海工學(xué)院計(jì)算機(jī)工程學(xué)院實(shí)驗(yàn)報(bào)告書課程名： 算法分析與設(shè)計(jì) 題 目： 實(shí)驗(yàn)2 最大子段和問(wèn)題 班 級(jí)： 學(xué) 號(hào)： 姓 名： 評(píng)語(yǔ)：成績(jī)： 指導(dǎo)教師： 批閱時(shí)間： 年 月 日實(shí)驗(yàn)2 最大子段和問(wèn)題實(shí)驗(yàn)?zāi)康暮鸵螅?）深刻掌握動(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ù)，寫出程序文檔。 實(shí)驗(yàn)內(nèi)容給定由n個(gè)整數(shù)（可能有負(fù)整數(shù)）組成的序列（a1，a2，an），求該序列形如的子段和的最大值，當(dāng)所有整數(shù)均為負(fù)整

2、數(shù)時(shí)，其最大子段和為0。實(shí)驗(yàn)環(huán)境 Turbo C 或VC+實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)，必做實(shí)驗(yàn)核心源代碼蠻力法#includeusing namespace std;void main()int i,j,n;double num100,a100,max;coutn;coutendl;cout請(qǐng)輸入要求的最大子段和中的數(shù)據(jù)元素:endl;for(i=1;inumi;max=num0;for(i=1;i=n;i+)if(maxnumi)max=numi;a1=num1;for(i=1;i=n;i+)for(j=i+1;j=n;j+)ai+=numj;if(maxai)max=ai;if(max0)max=0

3、;coutendl;cout該數(shù)據(jù)段的最大字段和為：maxendlendl;分治法#includeusing namespace std;#define max 50int MaxSum(double a,int left,int right)int center,i,j;double sum,leftsum,rightsum,lefts,rights,s1,s2;sum=0;if(left=right)if(aleft0)sum=aleft;elsesum=0;elsecenter=(left+right)/2;leftsum=MaxSum(a,left,center);rightsum=M

4、axSum(a,center+1,right);s1=0;lefts=0;for(i=center;i=left;i-)lefts+=ai;if(leftss1)s1=lefts;s2=0;rights=0;for(j=center+1;js2)s2=rights;sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;return sum;void main()int n,i;double nummax;coutn;coutendl;cout請(qǐng)依次輸入要求最大子段和的數(shù)據(jù)：endl;for(i=1;inumi;coutendl;cout求得的最大子段和為：MaxSum(num,1,n)endlendl;動(dòng)態(tài)規(guī)劃法#includeusing namespace std;#define Max 50void main()int n,i;float aMax,bMax,sum=0; coutn;coutendl;cout請(qǐng)依次輸入要求最大子段和的數(shù)據(jù)：endl;for(i=1;iai;coutendl;b0=a0;cout求得的最大子段和為：;for(i=1;i