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

淮海工学院计算机工程学院实验报告书课程名： 算法分析与设计 题 目： 实验2 动态规划算法 最大子段和问题 班 级： 软件081班 学 号： 110831116 姓 名： 陈点点 评语：成绩： 指导教师： 批阅时间： 年 月 日 算法分析与设计实验报告 - 4 -实验2 动态规划算法实验目的和要求（1）深刻掌握动态规划法的设计思想并能熟练运用；（2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 （3）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；（4）比较不同算法的时间性能；（5）给出测试数据，写出程序文档实验内容给定由n个整数组成的序列(a1, a2, , an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验环境 Turbo C 或VC+实验学时 2学时，必做实验数据结构与算法数据结构: 程序中所用的数据都是储存在数组当中算法: 蛮力法函数MaxSum(int a,int n,int &besti,int &bestj)分治法函数MaxSum(int a,int left,int right) 动态规划法函数 MaxSum(int n,int a)核心源代码1， 蛮力法 T(n)=O(n2)。#includeint MaxSum(int a,int n,int &besti,int &bestj) int sum=0; int i,j,k; for(i=1;i=n;i+) int asum=0; for(j=i;jsum) sum=asum; besti=i; bestj=j; return sum;void main() int n,a100,m,i,j,maxsum; cout请输入整数序列的元素个数n:n; cout请输入各元素的值(一共n个):endl; for(m=1;mam; maxsum=MaxSum(a,n,i,j); cout整数序列的最大子段和是：maxsumendl;2，分治法T(n)=O(nlog(n)。#includeint MaxSum(int a,int left,int right) int sum=0; if (left=right) /如果序列长度为1，直接求解 if (aleft0) sum=aleft; else sum=0; else int center=(left+right)/2; int leftsum=MaxSum(a,left,center); int rightsum=MaxSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i=left;i-) lefts+=ai; if(leftss1) s1=lefts; int s2=0; int rights=0; for(int j=center+1;js2) s2=rights; sum=s1+s2; if(sumleftsum)sum=leftsum; /合并，在sum、leftsum和rightsum中取较大者 if(sumrightsum)sum=rightsum; return sum;void main() int n,a100,m,maxsum; cout请输入整数序列的元素个数n:n; cout请输入各元素的值(一共n个):endl; for(m=1;mam; maxsum=MaxSum(a,1,n); cout整数序列的最大子段和是：maxsumendl;3，动态规划法T(n)=O(n)。#includevoid MaxSum(int n,int a) int sum=0; int b=0; for(int i=1;i0)b+=ai; else b=ai; if(bsum)sum=b; cout整数序列的最大子段和是：sumendl; void main() int n,a100,m,maxsum; cout请输入整数序列的元素个数n:n; cout请输入各元素的值(一共n个):endl; for(m=1;mam;MaxSum(n,a);实验结果1，蛮力法：2，分治法：3，动态规划法：实验体会同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。虽然蛮力法，分治法，动态规划法都可以解决最大子段和这个问题