2023年最大子段和问题实验报告.docx

《2023年最大子段和问题实验报告.docx》由会员分享，可在线阅读，更多相关《2023年最大子段和问题实验报告.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验四最大子段和问题L实验目的(1)掌握动态规划的设计思想并能纯熟运用;(2 )理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和重新修正的结果;2 .实验规定(D分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法;(2)比较不同算法的时间性能；(3)给出测试数据，写出程序文档；3 .实验设备和软件环境操作系统:Windows 7( 6 4x)开发工具：Visual Stud i o 2 023.实验环节以下实验数据都是以数组a = -2, 11, -4, 13, -5, - 2为例子；蛮力法蛮力法是一方面通过两个f。r循环去求出所有子段的值，然后通过if语句查找

2、出maxsum, 返回子序列的最大子段和;分治法(1)划分:按照平衡子问题的原则，将序列(al, a2，,an)划提成长度相同的两个子序列(al, a 2,.,an/2ri(an/2+ 1 ,.,an);(2)求解子问题：对与划分阶段的情况和可递归求解,情况需要分别计算s 1 =max V1/2 akX! ak乙k = i (i= i 0时，b j =bj -l+aj0(2)、当 bj-l0 W, b(j =aj 然后做递归操作求出最大子段和；5.实验结果蛮力法# i nc 1 u de #include usin g names p a ce st d ；i n t manlifa(int

3、a , i n t x)int i, j, sum=O, maxsum=O;* f or (i = 0 ; i x ； i+)( for (j = i + 1 ; j s u m)o 0(。sum = a i ;o o oo if ( s um maxsum)。 (3ma x s u m = s um ：。)0)。re t urn max sum;)int m a in()o ini y, sum;i n t a = -20, 1 1 , -4, 13, -5, 2 );int c = s izeo f ( a ) / s izeof ( i n t );sum = manl if a (a,

4、 c);cout s um;c i n y ：。r eturn 0；分治法# i nclu d e #inclu d e usi n g namespace s t d ;i n t MaxSum(int a, in t left, i n t r i ght)(。int s u m = 0 , m i d Sum = 0, 1 e ft Sum = 0, r igh t Sum = 0 ;。int c e nt e r, s 1 , s 2, left s ,r ights;。i f (left = right)， sum = a lef t ;else(。cente r = (left +

5、 ri g hl) / 2;lef t Sum = Ma x Sum (a, left, c e nter)；。 rights u m = M a x Sum (a, ccn ter + 1 , right);1 ef t s = 0 ;3 fo r (int i = cen t e r; i = 1 e ft; i) 0(。 le f t s += ai：， if (lef t s si) si = 1 e fts：。s 2 =0;s rights = 0 ：，for (int j =cente r + 1; j s 2 ) s2 = rig h t s ;。 m i dSum = si +

6、 s2;。 if (midSum leftSum) s u m = leftSum;s else。s um = m i dSum; if ( s um rights u m) sum = rightSum：。)retu r n sum;)int mai n ()(。/ * int s um ;。/int a口 = -20,1 1 , -4, 1 4, -5,-2 ;。/s u ml = Ma x Sum ( a , 0 , 5);cou t sum 1 endl ;*/int j , n;i nt b 1 00；。cout 请输入序列长度：；c i n n ：。cou t 请输入序列子段：；f

7、o r (j = 0: j b j：i nt sum, i ;。s um = MaxSum (b, 0, 5)：cout sum i;return 0;)动态规划法#in c lude using n amespa c e st d ;in t MaxSum (int n, i n t *a)i nt sum = 0, b = 0;o for (i n to for (i n t1： i 0)。(。b += a i;，。 else。(b = ai:。)。 i f (bsum)00。o sum = b：。return sum;int mainO(。in t k：int a = - 2, 11,

8、4, 13, -5, -2 );for (i n t i = 0; i 6; i+)cout a i cout end 1 ；c out ”数组a的最大连续子段和为： MaxSum( 6 , a) endl;。c in k;。retu r n 0；)6.讨论和分析在一开始做最大了段问题的实验的时候，对于蛮力法和分治法的理解还是可以的，但是对于 动态规划法的理解还不是那么明确透彻，通过网上的一些解释和结合自己书本上的知识，对 动态规划法得到了进一步的理解，接下来是三种算法时间性能的比较：蛮力法：时间复杂度为0(n2)分治法：时间复杂度为:T(n)=0(n 1 og (n)动态规划：时间复杂度为:T(n) = O (n)对于最大子段和问题在上述三种不同的算法中，动态规划算法的时间性能相对于其他两 个比较好。