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

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼应用、网络机房444 2011 年12月 14日年级、专业、班计科092学号200910405214姓名徐兴繁成绩实验项目名称最大子段和问题指导教师 吴晟教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（a1,a2,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。1、穷举法很简单，就是一个两层循环或者是三层循环就能得到结果； 分治法是版问题分化，求各个子问题的解，最后合并的到问题的解； 动态规划最重要的是求出动态规划函数，然后根据动态规划函数写算法。 2、根据自己程序的算法的分析得到时间复杂性如下蛮力算法：O(n2) 分治算法：O(nlogn) 动态规划：O（n）3、实验的计数和计时在运行结果中体现4、实验的结论是：动态规划算法是最优的，其次是分治算法。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程）根据自己的分析写源代码如下：#includestdio.h#includestdlib.h#includetime.hint 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(aleft0)sum=aleft;else sum=0;elsecenter=(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+=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;/蛮力算法/穷举法int Manli(int a,int n)int i,j,sum=0,max=0;for(j=0;jn;j+) sum=0;for(i=j;in;i+) c2+;sum=sum+ai;if(maxsum)max=sum;return max;int dtgh(int n,int a)int sum=0;int b10,i;b0=a0;for(i=1;i0)bi=bi-1+ai;else bi=ai;if(bisum)sum=bi;return sum;int main()clock_t start,end; double usetime;int n=6;int i;int b10;int a6=-20,11,-4,13,-5,-2;i=Manli(a,6);printf(蛮力算法：%dn,i);i=MaxSum(a,0,5);printf(分治算法：%dn,i);i=dtgh(6,a);printf(动规算法：%dn,i); /时间复杂度printf(nn时间复杂度：n);printf(蛮力算法：O(n2)n);printf(分治算法：O(nlog(n)n);printf(动规算法：O(n)n);/计数printf(nn计数：n);printf(蛮力算法：%dn,c1);printf(分治算法：%dn,c2);printf(动规算法：%dn,c3);/计算时间printf(nn计时：n);start=clock();i=1000000;while(i!=0)Manli(a,6);i-;end=clock();usetime=end-start;printf(蛮力算法用时 %.f*10(-6) 豪秒n, usetime); start=clock();i=1000000;while(i!=0)MaxSum(a,0,5);i-;end=clock();usetime=end-start;printf(分治算法用时 %.f*10(-6) 豪秒n, usetime);start=clock();i=1000000;while(i!=0)dtgh(6,a);i-;end=clock();usetime=end-start;printf(动规算法用时 %.f*10(-6) 豪秒n, usetime);五、实验过程原始记录( 测试数据、图表、计算等)请给出各个操作步骤的截图和说明；实验结果截图如下：测试数据为教材数据：a6=-20,11,-4,13,-5,-2;从截图可以看出三种算法的结果都正确，代码成功。第二组测试数据：a6= 20,11,-4,13,-5,-2;把-20改为20实验数据再次说明代码成功：六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）实验结果：通过实验结果得到的结果可以看出实验成功，本次实验最难得算法是分治算法，但分治算法的伪代码在教材上有，我通过教材的伪代码，我试着写了自己的代码。实验分析：通过时间复杂度的分析，可以看出动态规划算法是最优的，其次是分治算法，最差的是蛮力算法，从计数得到的结果与预期的结果一致。但是本次试验出现的问题是在计时器里显示的数据分治算法的用时比蛮力算法的长，我认为造成这种结果的因素有两个：1、实验数据特殊，数据样本太小。2、因为蛮力算法程序只是一个两层循环，而分治算法的代码过长，导致我们的计时器得到的结果产生错误。实验结论：本次实