2023年最大子段和问题实验报告

实验四最大子段和问题L实验目的(1)掌握动态规划的设计思想并能纯熟运用;(2)理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果;.实验规定(D分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法;(2)比较不同算法的时间性能；(3)给出测试数据，写出程序文档；.实验设备和软件环境操作系统:Windows7(64x)开发工具：VisualStudio2023.实验环节以下实验数据都是以数组a[]={-2,11,-4,13,-5,-2}为例子；蛮力法蛮力法是一方面通过两个f。r循环去求出所有子段的值，然后通过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)合并:比较在划分阶段三种情况下的最大子段和，取三者中比较大者为原问题的解。动态规划法划分子问题(1)划分子问题；(2)拟定动态规划函数；(3)填写表格；分为两种情况：(1)、当b[j-1]>0时，b[j]=b[j-l]+a[j]0(2)、当b[j-l]<0W,b(j]=a[j]然后做递归操作求出最大子段和；5.实验结果蛮力法#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;)动态规划法#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<<”数组a的最大连续子段和为："<<MaxSum(6,a)«endl;。cin»k;。return0；)6.讨论和分析在一开始做最大了段问题的实验的时候，对于蛮力法和分治法的理解还是可以的，但是对于动态规划法的理解还不是那么明确透彻，通过网上的一些解释和结合自己书本上