最大子段和问题实验报告.docx

《最大子段和问题实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四最大子段和问题1.实验目的（1）掌握动态规划的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果；2.实验要求（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（2）比较不同算法的时间性能；（3）给出测试数据，写出程序文档；3.实验设备和软件环境操作系统：Windows7（64x）开发工具：VisualStudio20134.实验步骤以下实验数据都是以数组a[]={-2,11,-4,13,-5,-2}为例子；蛮力法蛮力法是首先通过两个for循环去求出所有子段

2、的值，然后通过if语句查找出maxsum，返回子序列的最大子段和；分治法（1）划分：按照平衡子问题的原则，将序列（a1，a2，…，an）划分成长度相同的两个子序列（a1，a2，...，an/2）和（an/2+1,…,an）;（2）求解子问题：对与划分阶段的情况①和②可递归求解，情况③需要分别计算s1=max{k=in/2ak}(1<=i<=n/2),s2=max｛k=n2+1jak｝(n/2+1<=j<=n),则s1+s2为情况③的最大子段和。（1）合并：比较在划分阶段三种情况下的最大子段和，取三者中比较大者为原问题的解。动态规划法划分子问题

3、(1)划分子问题；(2)确定动态规划函数；(3)填写表格；分为两种情况：（1）、当b[j-1]>0时，b[j]=b[j-1]+a[j]。（2）、当b[j-1]<0时，b[j]=a[j]然后做递归操作求出最大子段和；5.实验结果蛮力法#include#includeusingnamespacestd;/*------------------------------------------------------------------------------*/intmanlifa(inta[],intx){

4、inti,j,sum=0,maxsum=0;for(i=0;isum){sum=a[i];}if(sum>maxsum){maxsum=sum;}}}returnmaxsum;}intmain(){inty,sum;inta[]={-20,11,-4,13,-5,-2};intc=sizeof(a)/sizeof(int);sum=manlifa(a,c);cout<>y;return0;}分治法#include

5、ostream>#includeusingnamespacestd;intMaxSum(inta[],intleft,intright){intsum=0,midSum=0,leftSum=0,rightSum=0;intcenter,s1,s2,lefts,rights;if(left==right)sum=a[left];else{center=(left+right)/2;leftSum=MaxSum(a,left,center);rightSum=MaxSum(a,center+1,right);s1=0;lefts=

6、0;for(inti=center;i>=left;i--){lefts+=a[i];if(lefts>s1)s1=lefts;}s2=0;rights=0;for(intj=center+1;j<=right;j++){rights+=a[j];if(rights>s2)s2=rights;}midSum=s1+s2;if(midSum

7、={-20,11,-4,14,-5,-2};//sum1=MaxSum(a,0,5);cout<>n;cout<<"请输入序列子段:";for(j=0;j>b[j];}intsum,i;sum=MaxSum(b,0,5);cout<>i;return0;}动态规划法#includeusingnamespacestd;intMaxSum(intn,int*a){ints

8、um=0,b=0;for(inti=1;i<=n;i++){if(b>0){b+=a[i];}else{b=a[i];}if(b>sum){sum=b;}}retu