2023年最大子段和問題實驗報告

實驗四最大子段和問題L實驗?zāi)康?1)掌握動態(tài)規(guī)劃的設(shè)計思想并能純熟運用;(2)理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復(fù)努力和重新修正的結(jié)果;.實驗規(guī)定(D分別用蠻力法、分治法和動態(tài)規(guī)劃法設(shè)計最大子段和問題的算法;(2)比較不同算法的時間性能；(3)給出測試數(shù)據(jù)，寫出程序文檔；.實驗設(shè)備和軟件環(huán)境操作系統(tǒng):Windows7(64x)開發(fā)工具：VisualStudio2023.實驗環(huán)節(jié)以下實驗數(shù)據(jù)都是以數(shù)組a[]={-2,11,-4,13,-5,-2}為例子；蠻力法蠻力法是一方面通過兩個f。r循環(huán)去求出所有子段的值，然后通過if語句查找出maxsum,返回子序列的最大子段和;分治法(1)劃分:按照平衡子問題的原則，將序列(al,a2，…,an)劃提成長度相同的兩個子序列(al,a2,...,an/2^ri(an/2+1,...,an);(2)求解子問題：對與劃分階段的情況①和②可遞歸求解,情況③需要分別計算s1=maxV'1/2akX!?ak{乙k=i}(i<=i<=n/2),s2=max{k_2+1}(n/2+lV=jV=n),則s1+s2為情況③的最大子段和。(3)合并:比較在劃分階段三種情況下的最大子段和，取三者中比較大者為原問題的解。動態(tài)規(guī)劃法劃分子問題(1)劃分子問題；(2)擬定動態(tài)規(guī)劃函數(shù)；(3)填寫表格；分為兩種情況：(1)、當(dāng)b[j-1]>0時，b[j]=b[j-l]+a[j]0(2)、當(dāng)b[j-l]<0W,b(j]=a[j]然后做遞歸操作求出最大子段和；5.實驗結(jié)果蠻力法#inc1ude<iostream>#include<math.h>usingnamespacestd；intmanlifa(inta[],intx)inti,j,sum=O,maxsum=O;*for(i=0;i<x；i++)(?for(j=i+1;j<x;j++)(。?sum=a[i]；°a[i]+=a[j];。。。if(a[i]>sum)o0(。sum=a[i];oo}ooif(sum>maxsum)。(3maxsum=sum：。)0})。returnmaxsum;)intmain()oiniy,sum;inta[]={-20,11,-4,13,-5,—2);intc=sizeof(a)/sizeof(int);sum=manlifa(a,c);cout<<sum;cin?y：。return0；}分治法#include<iostream>#include<math.h>usingnamespacestd;intMaxSum(inta[],intleft,intright)(。intsum=0,midSum=0,1eftSum=0,rightSum=0;。intcenter,s1,s2,lefts,rights;。if(left==right)，sum=a[left];else(。。center=(left+righl)/2;leftSum=MaxSum(a,left,center)；。rightsum=MaxSum(a,ccnter+1,right);efts=0;3for(inti=center;i>=1eft;i―)?0(。lefts+=a[i]：，if(lefts>si)si=1efts：。}…s2=0;s?rights=0：，for(intj=center+1;j<=right;j++)O0{。rights+=a[j]；(rights>s2)s2=rights;。}。midSum=si+s2;。if(midSum<leftSum)sum=leftSum;selse。sum=midSum;?if(sum<rightsum)sum=rightSum：。)returnsum;)intmain()(。/*intsum;。//inta口={-20,11,-4,14,-5,-2};。//suml=MaxSum(a,0,5);cout<<sum1?endl;*/intj,n;intb[100]；。cout?"請輸入序列長度："；cin?n：。cout?"請輸入序列子段："；for(j=0:j<n;J++)(，cin>>b[j]：}intsum,i;。sum=MaxSum(b,0,5)：cout<<sum<<endl;oc\n>>i;return0;)動態(tài)規(guī)劃法#include<iostream>usingnamespacestd;intMaxSum(intn,int*a)intsum=0,b=0;

oofor(intoofor(int1：i<=n：i++)，if(b>0)。(。。。b+=a[i];，}。else。(b=a[i]:。)。if(b>sum)00{。osum=b：。}。}。returnsum;}intmainO(。intk：inta[]={-2,11,—4,13,-5,-2);for(inti=0;i<6;i++)cout<<a[i]?cout<<end1；cout<<”數(shù)組a的最大連續(xù)子段和為："<<MaxSum(6,a)?endl;。cin?k;。return0；)6.討論和分析在一開始做最大了段問題的實驗的時候，對于蠻力法和分治法的理解還是可以的，但是對于動態(tài)規(guī)劃法的理解還不是那么明確透徹，通過網(wǎng)上的一些解釋和結(jié)合自己書本上