算法分析与设计-实验三-最大子段和问题

-1-昆明理工大学信息工程与自动化学院学生实验报告（201—201学年第1学期）课程名称：算法分析与设计开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称最大子段和问题指导教师教师评语该同学是否了解实验原理：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）通过分析对比，得出自己的结论。穷举法是用一个二维数组将从i到j的和都记录下来，再比较各元素的大小，时间复杂性为O（n2），分治法的设计思想是不断将问题为子问题，然后求解子问题，最后对解进行合并，时间复杂性为O(nlogn)，动态规划法的设计思想是将问题划分为若干个子问题，时间复杂度为O(n)。-2-分治法流程图：开始结束输入整数个数输出最大子段和输入整数left==rightlefts+=a[i]if(leftss1)s1=leftsrights+=a[j]if(rightss2)s2=rightssum=s1+s2比较sum,leftsum比较sum，rightsum-3-穷举法流程图：动态规划法流程图：三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件开始结束输入整数个数输出最大子段和输入整数max=num[0]maxnum[i]max=num[i]开始结束输入整数个数输出最大子段和输入整数sum=0,b=0b0b+=a[i]b=a[i]bsumsum=b-4-四、实验方法、步骤（或：程序代码或操作过程）程序代码：//穷举法#includestdio.hvoidmain(){inti,j,n;intnum[100],a[100],max;printf(\t\t\t最大子段和问题（穷举法）\n\n);printf(请输入所要求最大字段和整数的个数:\n);scanf(%d,&n);printf(请分别输入这%d个整数的值:\n,n);for(i=0;in;i++)scanf(%d,&num[i]);max=num[0];for(i=1;i=n;i++){if(maxnum[i])max=num[i];}a[1]=num[1];for(i=1;i=n;i++){for(j=i+1;j=n;j++){a[i]+=num[j];if(maxa[i])max=a[i];}}if(max0)max=0;printf(这%d个整数组成的序列的最大子段和是：%d\n,n,max);}//分治法#includestdio.hintMaxSum(inta[],intleft,intright){intsum=0;if(left==right){-5-if(a[left]0)sum=a[left];elsesum=0;}else{intcenter=(left+right)/2;intleftsum=MaxSum(a,left,center);intrightsum=MaxSum(a,center+1,right);ints1=0;intlefts=0;for(inti=center;i=left;i--){lefts+=a[i];if(leftss1)s1=lefts;}ints2=0;intrights=0;for(intj=center+1;j=right;j++){rights+=a[j];if(rightss2)s2=rights;}sum=s1+s2;if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;}returnsum;}voidmain(){intn,a[100],m,maxsum;printf(\t\t\t最大子段和问题（分治法）\n\n);printf(请输入所要求最大字段和整数的个数:\n);scanf(%d,&n);printf(请分别输入这%d个整数的值:\n,n);for(m=1;m=n;m++)scanf(%d,&a[m]);maxsum=MaxSum(a,1,n);printf(这%d个整数组成的序列的最大子段和是：%d\n,n,maxsum);}-6-//动态规划法#includestdio.hvoidMaxSum(intn,inta[]){intsum=0;intb=0;for(inti=1;i=n;i++){if(b0)b+=a[i];elseb=a[i];if(bsum)sum=b;}printf(这%d个整数组成的序列的最大子段和是：%d\n,n,sum);}voidmain(){intn,a[100],m,maxsum;printf(\t\t\t最大子段和问题（动态规划法）\n\n);printf(请输入所要求最大字段和整数的个数:\n);scanf(%d,&n);printf(请分别输入这%d个整数的值:\n,n);for(m=1;m=n;m++)scanf(%d,&a[m]);MaxSum(n,a);}五、实验过程原始记录(测试数据、图表、计算等)程序运行截图：-7-六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）这次实验我们是用穷举法、分治法和动态规划法三种方法来求解最大子段和问题。我们都知道，分治法就是将一个复杂的问题分解成两个或者更多的相同或相似的子问题，直到最后的子问题能够简单的求解，原问题的解就是子问题的解的合并，而且该问题所分解的各个子问题是相互独立的。