《最大子段和问题》由会员分享，可在线阅读，更多相关《最大子段和问题（4页珍藏版）》请在金锄头文库上搜索。
1、实验五：最大子段和问题一、实验环境windows xpMatlab R2010b.二、实验内容给定由n个整数组成的序列(a1, a2,，an)，求该序列形如a的子段和 的最大值，当所有整数均为负整数时，其最大子段和为0。k i k三、实验目的(1) 深刻掌握动态规划法的设计思想并能熟练运用；(2) 理解这样一个观点：冋样的问题可以用不冋的方法解决，一个好的算法是反 复努力和重新修正的结果。(3) 分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；(4) 比较不同算法的时间性能；(5) 给出测试数据，写出程序文档。四、问题分析求最大子段和问题主要有3种方法，1. 蛮力法2. 分治法3.
2、动态规划法五、算法描述：算法一(蛮力法)：从一个数开始，逐个相加比较大小。伪代码：算法MaxSum1输入：一组数列v输出：最大字段和及运行时间1. sum=0;2. 计算数组长度n=length(v);3. 循环i从1n3.1 thissum=0;3.2循环j从in3.2.1 thissum=thissum+v(j);3.2.2 如果thissumsum，贝Vsum=thissum;4. 输出最大字段和sum;算法二(分治法)：分-将问题分解为规模更小的子问题； 治-将这些规模更小的子问题逐个击破； 合一将已解决的子问题合并，最终得出“母”问题的解；。 伪代码：算法MaxSum2(v)输入：一
3、组数列v 输出：最大字段和1. sum=0;2. 计算数组长度n=length(v);3. 设置两部分的初始值left=v(1)， right=v(n);4. 比较left和right4.1 如果 left=right4.2 则判断v(left)O?4.3 如果大于0,贝Vsum=v(left);4.4 否贝9sum=0;算法三(动态规划法)：可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值 的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若 干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 伪代码：算法MaxSum3(v)输入：一组数列v输出：
4、最大字段和1. sum=0;2. 计算数组长度n=length(v);3. 循环i从1n3.1 如果b0 贝 9b=b+v(i);3.2 否则b=v(i);3.3 如果bsum则sum=b;六、实验结果：用Excel表格计算其平均值实验数组蛮力法分治法动态规划v=-20 11 -4 13 -5 -2200.011056200.001512200.009128v=5 11 -4 -1 5 -2160.004243160.001234160.003662v=5 -11 4 -1 5 2100.004712100.001274100.003066v=-8 -14 14 -12 5 2140.0039
5、90140.00124140.003062平均时间0.00600020.0013150.0047295七、实验结果分 析：通过时间复杂度的分析，可以看出动态规划算法是最优的，其次是分治算法， 最差的是蛮力算法，从计数得到的结果与预期的结果一致。但是本次试验出现的问题是在计时器里显示的数据分治算法的用时比蛮力算 法的长，我认为造成这种结果的因素有两个：1、实验数据特殊，数据样本太小。2、因为蛮力算法程序只是一个两层循环，而分治算法的代码过长，导致我们 的计时器得到的结果产生错误。八、实验结论：根据自己程序的算法的分析得到时间复杂性如下 蛮力算法：0( n2)分治算法：0(nlog n )动态规划
6、：0 (n)九、程序源代码算法一(蛮力法)：func tion MaxSuml(v) % 蛮力法 0( n2) sum=0;n=length(v);for i=1:1:nthissum=0;for j=i:1:n;thissum=thissum+v(j);if thissumsumsum=thissum;endendendR1=sum算法二(分治法)：func tion MaxSum2(v) % 分治法 O( nlogn) sum=0;n=length(v);left=v(1);right=v(n);if left=rightif v(lef t)0sum=v(left);elsesum=0;
7、endelsecenter=(left+right)/2;leftsum=MaxSum(v,left,center); rightsum=MaxSum(v,center+1,right); s1=0;lefts=O;for i=center：-1:leftc1=c1+1;lefts=lefts+a(i);if leftss1s1=lefts;endends2 = 0;rights=O;for j=center+1:1:rightc1=c1+1;righ ts=righ ts+aj); if rightss2 s2=rights;endendsum=s1+s2;if sumleftsumsum=leftsum;if sum0b=b+v(i);elseb=v(i);endif bsumsum=b;endendR3=sum调用函数：v=-20 11 -4 13 -5 -2; t ic;MaxSum1(v)t oc;t ic;MaxSum1(v)t oc;ticMaxSum3(v)t oc;十、运行结果R1 =20Elapsed time is 0.011056 seconds.R1 =20Elapsed time is 0.001512 seconds.R3 =20Elapsed time is 0.009128 seconds.
