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

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房444 2012 年12月 14日年级、专业、班学号姓名成绩实验项目名称最大子段和问题指导教师吴晟教师评语该同学是否了解实验原理：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）分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法； 蛮力法设计原理：利用3个for的嵌套（实现从第1个数开始计算子段长度为1，2，3n的子段和，同理计算出第2个数开始的长度为1，2，3n-1的子段和，依次类推到第n个数开始计算的长为1的子段和）和一个if（用来比较大小）,将其所有子段的和计算出来并将最大子段和赋值给summax1。用了3个for嵌套所以时间复杂性为(n3)； 分治法设计原理：1）、划分：按照平衡子问题的原则，将序列（，）划分成长度相同的两个字序列（，）和（，）。2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算s1=，s2=，则s1+s2为最大子段和。若然只在左边或右边，那就好办了，前者视s1为summax2,后者视s2 o summax2。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（j）=a。可得如下递推式：代码实现过程中只用了一个for, 时间复杂性为：(n) （2） 对所设计的算法采用大O符号进行时间复杂性分析；蛮力法时间复杂性为(n3)；分治法时间复杂性为(nlogn)动态规划法时间复杂性为：(n)（3） 上机实现算法，并用计数法和计时法分别测算算法的运行时间；详情见运行结果。 （4）通过分析对比，得出自己的结论。结论：蛮力法只可以处理小理的数据。当数据量超过10000时，由蛮力法要等很久才输出，所以数据量超过10000时，就比较分治法和动态规划法。由实验结果可知，动态规划法所用的时间要少。实验原理图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件。绘制流程图软件：Diagram Designer.4、 实验方法、步骤（或：程序代码或操作过程）部分重要代码说明：#include /时间的头文件#include /数学头文件int getMaxSum1(int iarray, int n)/*蛮力法函数 */int getMaxSum2(int iarray, int startIndex, int endIndex）/分治法函数int getMaxSum3(int iarray, int n)/*动态规划方法函数 */int OUT_PRINTF()/输出最大字段求解的函数int main()/主函数#include #include /时间的头文件#include /数学头文件using namespace std;/*蛮力法 */int getMaxSum1(int iarray, int n)int maxSum = 0;/初始化maxSumfor (int i = 0; i n; +i)/实现从第1个数开始计算子段长度为1，2，3n的子段和 for (int j = i; j n; +j) int tmp = 0;/初始化tmp(子段和) for (int k = i; k maxSum )/比较子段和，得出最大的子段和maxSum maxSum = tmp; return maxSum;源程序代码：/*分治递归方法 */int getMaxSum2(int iarray, int startIndex, int endIndex) if ( endIndex = startIndex ) /只有一个元素 return iarraystartIndex; if ( endIndex - startIndex = 1 )/两个元素时 int tmp = iarraystartIndex + iarrayendIndex; tmp = tmp iarraystartIndex ? tmp : iarraystartIndex; tmp = tmp iarrayendIndex ? tmp : iarrayendIndex; return tmp; /左边一半序列的最大子段和leftMaxSumint leftMaxSum = getMaxSum2(iarray, startIndex, (startIndex + endIndex)/2); /右边一半序列的最大子段和rightMaxSum int rightMaxSum = getMaxSum2(iarray, (startIndex + endIndex)/2+1, endIndex);int s1 = 0;int s2 = 0;int tmp = 0; for (int i = (startIndex + endIndex)/2; i = startIndex; -i)/左子段和 tmp = tmp + iarrayi; if ( tmp s1 ) s1 = tmp; tmp = 0; for ( i = (startIndex + endIndex)/2+1; i s2 ) s2 = tmp; int middleMaxSum = s1 + s2; int maxSum = leftMaxSum rightMaxSum ? leftMaxSum : rightMaxSum; maxSum = maxSum middleMaxSum ? maxSum : middleMaxSum; return maxSum;/*动态规划方法 */int getMaxSum3(int iarray, int n)int maxSum = 0; int b = 0; for (int i = 0; i 0 ) b = b + iarrayi; else b = iarrayi; if ( b maxSum ) maxSum = b; return maxSum;int OUT_PRINTF()/输出最大字段求解的函数int n,i,cho; clock_t t1,t2,t3,t4,t5,t6;cout*n; cout* 求最大字段和问题 *n; cout*n; coutendl; coutcho; cout请输入序列的长度n; int *iarray=new intn; if(cho=2) srand( (unsigned)time( NULL ) ); / cout随机序列为：endl; for(i=1;i=n;i+)iarrayi=(rand()/13-1129); /cout iarrayi;else cout请输入序列endl; for(i=0;iiarrayi; t1=clock();/使用蛮力法求解的开始时间int maxSum1 = getMaxSum1(iarray, n);t2=clock();/蛮力法求解的结束时间coutendl;cout-n;cout蛮力法最大子段和为: maxSum1 endl;cout时间：float(t2-t1)/CLK_TCKendl;/CLK_TCKt3=clock();/分治法求解的开始时间int maxSum2 = getMaxSum2(iarray, 0, n-1);t4=clock();/分治法求解的结束时间cout-n;cout分治法最大子段和为: maxSum2 endl;cout时间：float(t4-t3)/CLK_TCKendl; t5=clock();/动态规划法求解的开始时间 int maxSum3 = getMaxSum3(iarray, n);t6=clock();/动态规划法求解的结束时间cout-n;cout动态规划法最大子段和为: maxSum3 endl;cout时间：float(t6-t5)/CLK_TCKendl;return 0;int main()/主函数int i;char a,y,Y,b;OUT_PRINTF(); /调用输出函数for(i=1;i10;i+)cout是否继续输入？Y/Na;if(a=y|a=Y) OUT_PRINTF(); if(a=n|a=N) return 0;return 0;5、 实验过程原始记录( 测试数据、图表、计算等)测试程序：输入选择的方式求最大子段和问题。手动输入适合序列长度短的时候：当要测试序列长度很大的时候，经过测试，蛮力法的输出时间太长，所以先省去蛮力法的测试。当序列长度很大是，只调用动态规划法和分治法。结果如下：经过测试可知，动态规划法是最佳的选择。6、 实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）此次实验主要是设计了三种方法来求解最大子段和问题。在此次实验中遇到过很多问题，如设置循环时，条件不合理，导致没有出来理想中得结果。还有，为了得出每种方法求解的时间，添加了一个时间函数的头文件，程序中用到了clock()函数，clock()函数计算出来的是硬件滴答的数目，不是毫秒。在TC2.0中硬件每18.2个滴答是一秒，在VC+6.0中硬件每1000个滴答是一秒。C/C+中的计时函数是clock()，而与其相关的数据类型是clock_t。故计算时间的公式为float(ti-ti-1)/CLK_TCK