《算法分析与设计》实验2 最大子段和问题

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

2、数时，其最大子段和为0。实验环境 Turbo C 或VC+实验学时 2学时，必做实验核心源代码蛮力法#includeusing namespace std;void main()int i,j,n;double num100,a100,max;coutn;coutendl;cout请输入要求的最大子段和中的数据元素: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该数据段的最大字段和为：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请依次输入要求最大子段和的数据：endl;for(i=1;inumi;coutendl;cout求得的最大子段和为：MaxSum(num,1,n)endlendl;动态规划法#includeusing namespace std;#define Max 50void main()int n,i;float aMax,bMax,sum=0; coutn;coutendl;cout请依次输入要求最大子段和的数据：endl;for(i=1;iai;coutendl;b0=a0;cout求得的最大子段和为：;for(i=1;i