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

-1-昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼应用、网络机房4442011年12月14日年级、专业、班计科092学号200910405214姓名徐兴繁成绩实验项目名称最大子段和问题指导教师吴晟教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求改序列形如jkka1的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自己的结论。1、穷举法很简单，就是一个两层循环或者是三层循环就能得到结果；分治法是版问题分化，求各个子问题的解，最后合并的到问题的解；动态规划最重要的是求出动态规划函数，然后根据动态规划函数写算法。-2-2、根据自己程序的算法的分析得到时间复杂性如下蛮力算法：O(n2)分治算法：O(nlogn)动态规划：O（n）3、实验的计数和计时在运行结果中体现4、实验的结论是：动态规划算法是最优的，其次是分治算法。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）根据自己的分析写源代码如下：#includestdio.h#includestdlib.h#includetime.hintc1,c2,c3;//用于计数intMaxSum(inta[],intleft,intright){inti,j,sum,center,leftsum,rightsum,s1,s2,lefts,rights;sum=0;if(left==right){if(a[left]0)sum=a[left];elsesum=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(leftss1)s1=lefts;-3-}s2=0;rights=0;for(j=center+1;j=right;j++){c1++;rights+=a[j];if(rightss2)s2=rights;}sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;}returnsum;}//蛮力算法/穷举法intManli(inta[],intn){inti,j,sum=0,max=0;for(j=0;jn;j++){sum=0;for(i=j;in;i++){c2++;sum=sum+a[i];if(maxsum)max=sum;}}returnmax;}intdtgh(intn,inta[]){intsum=0;intb[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];elseb[i]=a[i];if(b[i]sum)sum=b[i];}returnsum;}-4-intmain(){clock_tstart,end;doubleusetime;intn=6;inti;intb[10];inta[6]={-20,11,-4,13,-5,-2};i=Manli(a,6);printf(蛮力算法：%d\n,i);i=MaxSum(a,0,5);printf(分治算法：%d\n,i);i=dtgh(6,a);printf(动规算法：%d\n,i);//时间复杂度printf(\n\n时间复杂度：\n);printf(蛮力算法：O(n^2)\n);printf(分治算法：O(nlog(n))\n);printf(动规算法：O(n)\n);//计数printf(\n\n计数：\n);printf(蛮力算法：%d\n,c1);printf(分治算法：%d\n,c2);printf(动规算法：%d\n,c3);//计算时间printf(\n\n计时：\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--;-5-}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);}五、实验过程原始记录(测试数据、图表、计算等)请给出各个操作步骤的截图和说明；实验结果截图如下：测试数据为教材数据：a[6]={-20,11,-4,13,-5,-2};-6-从截图可以看出三种算法的结果都正确，代码成功。第二组测试数据：：a[6]={20,11,-4,13,-5,-2};把-20改为20实验数据再次说明代码成功：六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）实验结果：通过实验结果得到的结果可以看出实验成功，本次实验最难得算法是分治算法，但分治算法的伪代码在教材上有，我通过教材的伪代码，我试着写了自己的代码。实验分析：通过时间复杂度的分析，可以看出动态规划算法是最优的，其次是分治算法，最差的是蛮力算法，从计数得到的结果与预期的结果一致。但是本次试验出现的问题是在计时器里显示的数据分治算法的用时比蛮力算法的长，我认为造成这种结果的因素有两个：1、实验数据特殊，数据样本太小。2、因为蛮力算法程序只是一个两层循环，而分治算法的代码过长，导致我们的计时器得到的结果产生错误。实验结论：本次实验成功得到结果，实验顺利完成。通过本次实验我进一步加深了算法的设计是多么的重要，一个好的算法意味着很多东西，不仅节约空间，最重要的是我们等待的时间。请结合实验的结果分析算法原理；在实验中遇到了些什么问题，如何解决；有什么收获等；注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。