算法实验3-最大子段和问题实验报告

《算法实验3-最大子段和问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼机房4442012年12月14日年级、专业、班学号姓名成绩实验项目名称最大子段和问题指导教师吴晟教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年

2、月日一、上机目的及内容1.上机内容给定有n个整数（可能有负整数）组成的序列（a1,a2,…,an），求改序列形如的子段和的最大值，当所有整数均为负整数时，其最大子段和为0。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算

3、法；蛮力法设计原理：利用3个for的嵌套（实现从第1个数开始计算子段长度为1，2，3…n的子段和，同理计算出第2个数开始的长度为1，2，3…n-1的子段和，依次类推到第n个数开始计算的长为1的子段和）和一个if（用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。用了3个for嵌套所以时间复杂性为○(n3)；-10-分治法设计原理：1）、划分：按照平衡子问题的原则，将序列（，，…，）划分成长度相同的两个字序列（，…，）和（，…，）。2）、求解子问题：对于划分阶段的情况分别的两段可

4、用递归求解，如果最大子段和在两端之间需要分别计算s1=，s2=，则s1+s2为最大子段和。若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2osummax2。3）、合并：比较在划分阶段的3种情况下的最大子段和，取三者之中的较大者为原问题的解。4）、时间复杂性分析:f(n)=2*f(n/2)+○(n/2),最后为○(nlogn)。动态规划法设计原理：动态规划法求解最大字段和问题的关键是要确定动态规划函数。记则由b（j）的定义，当b（j-1）>0是，b（j）=b（j-1）+a，否则，b（

5、j）=a。可得如下递推式：代码实现过程中只用了一个for,时间复杂性为：○(n)（2）对所设计的算法采用大O符号进行时间复杂性分析；蛮力法时间复杂性为○(n3)；分治法时间复杂性为○(nlogn)动态规划法时间复杂性为：○(n)（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；详情见运行结果。（4）通过分析对比，得出自己的结论。结论：蛮力法只可以处理小理的数据。当数据量超过10000时，由蛮力法要等很久才输出，所以数据量超过10000时，就比较分治法和动态规划法。由实验结果可知，动态规划法所

6、用的时间要少。-10-实验原理图：-10-三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件。绘制流程图软件：DiagramDesigner.四、实验方法、步骤（或：程序代码或操作过程）部分重要代码说明：#include//时间的头文件#include//数学头文件intgetMaxSum1(intiarray[],intn)/*蛮力法函数*/intgetMaxSum2(intiarray[],intstartIndex,inte

7、ndIndex）//分治法函数intgetMaxSum3(intiarray[],intn)/*动态规划方法函数*/intOUT_PRINTF()//输出最大字段求解的函数intmain()//主函数#include#include//时间的头文件#include//数学头文件usingnamespacestd;/*蛮力法*/intgetMaxSum1(intiarray[],intn){intmaxSum=0;//初始化maxSumfor(inti=

8、0;imaxSum)//比较子段和，得出最大的子段和maxSum{maxSum=tmp;}}}returnmaxSum;}源程序代码：-10-/*分治递归方法*/intgetMaxSum2(inti