最大字段和问题动态规划法

1、淮海工学院计算机工程学院实验报告书课程名：算法分析与设计题 目： 实验2 动态规戈U算法最大子段和问题班级：软件081班学号：110831116姓 名：陈点点评语:成绩： 指导教师： 批阅时间:算法分析与设计实验报告-5 -实验2动态规划算法实验目的和要求(1) 深刻掌握动态规划法的设计思想并能熟练运用；(2) 理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。(3) 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；(4) 比较不同算法的时间性能；(5) 给出测试数据，写出程序文档实验内容j给定由n个整数组成的序列(al, a2,an),求该序

2、列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。实验环境Turbo C 或 VC+实验学时2学时，必做实验数据结构与算法数据结构：程序中所用的数据都是储存在数组当中算法：蛮力法函数 MaxSum(int a,int n,int &besti,int &bestj)分治法函数 MaxSum(int a,int left,int right)动态规划法函数 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<<"请输入整数序列的元素个数n:"<<e ndl;cin»n;cout<<"请输入各元素的值(一共"<<*<&quo

4、t;个):"<<endl;for(m=1;m <=n; m+)cin> >am;maxsum=MaxSum(a, n,i,j);cout<<"整数序列的最大子段和是："<<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) / 如果序列长度为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<<"请输入整数序列的元素个数n:"<<e ndl;cin»n;cout<<"请输入各元素的值(一共"<<*<"个):"<<endl;for(m=1;m

7、<=n; m+)cin> >am;maxsum=MaxSum(a,1, n);cout<<"整数序列的最大子段和是："<<maxsum<<e ndl;3, 动态规划法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<<"整数序列的最大子段和是：&qu

8、ot;<<sum<<endl;void mai n()int n ,a100,m,maxsum;cout<<"请输入整数序列的元素个数n:"<<e ndl;cin»n;cout<<"请输入各元素的值(一共"<<*<"个):"<<endl;for(m=1;m <=n; m+)cin> >am;MaxSum( n,a);实验结果1,蛮力法:2,分治法:3,动态规划法:实验体会同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。