求最大字段的三种方法 - 动态规划 蛮力 分治算法

昆明理工大学信息工程与自动化学院学生实验报告

（ 2011 —2012 学年 第 1 学期 ）

课程名称：算法设计与分析 开课实验室：信自楼应用、网络机房444 2011 年12月 14日 年级、专业、计科092 班 实验项目名称 教师评最大子段和问题 A.了解□ A.强 □ A.达到□ A.规范□ A.详细□ 学号 200910405214 姓名 徐兴繁 成绩 指导教师 吴晟 B.基本了解□ B.中等 □ B.基本达到□ B.基本规范□ B.一般 □ C.不了解□ C.差 □ C.未达到□ C.不规范□ C.没有 □ 该同学是否了解实验原理： 该同学的实验能力： 该同学的实验是否达到要求： 实验报告是否规范： 实验过程是否详细记录： 语 教师签名： 年 月 日 一、上机目的及内容

1.上机内容

给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求改序列形如

?ak?1jk的子段和的

最大值，当所有整数均为负整数时，其最大子段和为0。 2.上机目的

（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；

（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法； （2）对所设计的算法采用大O符号进行时间复杂性分析；

（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。

1、穷举法很简单，就是一个两层循环或者是三层循环就能得到结果； 分治法是版问题分化，求各个子问题的解，最后合并的到问题的解； 动态规划最重要的是求出动态规划函数，然后根据动态规划函数写算法。

-1-

2、根据自己程序的算法的分析得到时间复杂性如下 蛮力算法：O(n2) 分治算法：O(nlog

n

)

动态规划：O（n）

3、实验的计数和计时在运行结果中体现

4、实验的结论是：动态规划算法是最优的，其次是分治算法。

三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件

四、实验方法、步骤（或：程序代码或操作过程）

根据自己的分析写源代码如下： #include\#include\#include\

int c1,c2,c3;//用于计数

int MaxSum(int a[],int left ,int right) { int i,j,sum,center,leftsum,rightsum,s1,s2,lefts,rights; sum=0; if(left==right) { if(a[left]>0)sum=a[left]; else sum=0; } else { center=(left+right)/2; leftsum=MaxSum(a,left,center); rightsum=MaxSum(a,center+1,right); s1=0; lefts=0; for(i=center;i>=left;i--) { c1++; lefts+=a[i]; if(lefts>s1)s1=lefts;

-2-

} s2=0; rights=0; for(j=center+1;j<=right;j++) { c1++; rights+=a[j]; if(rights>s2)s2=rights; } sum=s1+s2; if(sum

//蛮力算法/穷举法 int Manli(int a[],int n) { int i,j,sum=0,max=0; for(j=0;j

return max; }

int dtgh(int n,int a[]) { int sum=0; int b[10],i; b[0]=a[0]; for(i=1;i<=n;i++) { c3++; if(b[i-1]>0)b[i]=b[i-1]+a[i]; else b[i]=a[i]; if(b[i]>sum)sum=b[i]; } return sum; }

-3-

int main() { clock_t start,end; double usetime; int n=6; int i; int b[10]; int a[6]={-20,11,-4,13,-5,-2}; i=Manli(a,6); printf(\蛮力算法：%d\\n\ i=MaxSum(a,0,5); printf(\分治算法：%d\\n\ i=dtgh(6,a); printf(\动规算法：%d\\n\

//时间复杂度 printf(\时间复杂度：\\n\ printf(\蛮力算法：O(n^2)\\n\ printf(\分治算法：O(nlog(n))\\n\ printf(\动规算法：O(n)\\n\ //计数 printf(\计数：\\n\ printf(\蛮力算法：%d\\n\ printf(\分治算法：%d\\n\ printf(\动规算法：%d\\n\ //计算时间 printf(\计时：\\n\ start=clock(); i=1000000; while(i!=0) { Manli(a,6); i--; } end=clock(); usetime=end-start; printf(\蛮力算法用时 %.f*10^(-6) start=clock(); i=1000000; while(i!=0) { MaxSum(a,0,5); i--;

豪秒\\n\-4-

usetime);