蛮力法、分治法和动态规划法设计最大子段和问题的算法.doc

算法设计与分析实验报告 实验题目 给定由n个整数组成的序列(a1, a2, …, an)，求该序列形如 的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。 实验目的 （1）深刻掌握动态规划法的设计思想并能熟练运用； （2）理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果。 实验要求 （1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； （2）比较不同算法的时间性能； （3）给出测试数据，写出程序文档。 实验内容（包括代码和对应的执行结果截图） #includeiostream.h int x,y,z; int ml(int d[])//蛮力法 { int a=0,i,j,f; for(j=0;j5;j++) { f=0; for(i=j;i5;i++) { f=f+d[i]; if(af) a=f; x++; } } return a; } int MaxSum(int a[ ], int left, int right) { int lefts,rights,s1,s2,i,j; int sum=0,center,leftsum,rightsum; if (left==right) { //如果序列长度为1，直接求解 if (a[left]0) sum=a[left]; else sum=0; y++; } else { center=(left+right)/2; //划分 leftsum=MaxSum(a, left, center); //对应情况①，递归求解 rightsum=MaxSum(a, center+1, right); //对应情况②，递归求解 s1=0; lefts=0; //以下对应情况③，先求解s1 for (i=center; i=left; i--) { lefts+=a[i]; if (leftss1) s1=lefts; y++; } s2=0; rights=0; //再求解s2 for (j=center+1; j=right; j++) { rights+=a[j]; if (rightss2) s2=rights; y++; } sum=s1+s2; //计算情况③的最大子段和 if (sumleftsum) sum=leftsum; //合并，在sum、leftsum和rightsum中取较大者 if (sumrightsum) sum=rightsum; y++; } return sum; } int max(int a[],int n) { int sum=0,b=0; for(int i=0;i=n;i++) { if(b0) b+=a[i]; else b=a[i]; if(bsum) sum=b; z++; } return sum; } void main() { int c; int s[5]={1,9,-5,7,-1}; c=ml(s); cout蛮力法计算最大子段和为：cendl; cout蛮力法时间性为：xendl; c=MaxSum(s, 0, 4); cout分治法计算最大子段和为：cendl; cout分治法时间性为：yendl; c=max(s, 4); cout动态规划法计算最大子段和为：cendl; cout动态规划法时间性为：zendl; } 程序运行结果： 实验结果分析 程序测试序列为1 ,9 , -5 , 7, -1 最大子段和为12。 由上述程序结果分析动态