最大子段和问题.docx

1、最大子段和问题算法设计与分析课程设计报告题 目： 最大子段和问题 院 （系）： 信息科学与工程学院 专业班级： 软件工程1201班 20 14 年 12 月 29 日至20 15 年 1 月 9 日 算法设计与分析 课程设计任务书一、设计题目最大子段和问题问题描述：给定n个整数（可能有负整数）a1， a2， ，an 。求形如ai， ai+1，aj i=1，2，n，j=1，2，n， ij，求出ai， ai+1，aj子段和的最大值。当所有整数均为负值时定义其最大子段还和为0。例如：当(a1， a2， a3 ，a4 ，a5，a6)=(-2， 11， -4， 13， -5， 2)时，最大子段和为(a2

2、， a3， a4)=20 即 =20 i=2，j=4二、设计主要内容具体要求如下：(1) 使用蛮力算法实现(2) 使用分治策略算法实现(3) 使用动态规划算法实现(4) 对各种算法的时间复杂度进行分析和比较。(5) 设计出相应的菜单，通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1) 实现该系统功能的程序代码(2) 撰写符合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料1 吕国英算法设计与分析第2版北京：清华大学出版社，20112 王晓东算法设计与

3、分析 北京，清华大学出版社，20093 徐士良计算机常用算法第2版北京，清华大学出版社出版，2010指导教师（签名）： 20 年 月 日目 录1 常用算法 61.1蛮力算法 61.2分治算法 71.3 动态规划算法 82 问题分析与算法设计 92.1蛮力算法的设计 92.2 分治算法的设计 92.3 动态规划算法的设计 103 算法实现 103.2蛮力算法的实现 103.2 分治算法的实现 113.3 动态规划算法的实现 134 测试和分析 134.1蛮力算法测试 134.2蛮力算法时间复杂度的分析 154.3 分治算法测试 154.4分治算法时间复杂度的分析 174.5 动态规划算法测试 1

4、74.6 动态规划算法时间复杂度的分析 194.7 三种算法的比较 205 总结 20参考文献 20附录 201 常用算法1.1蛮力算法1. 枚举的概念(1)枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。 (2)枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形 。(3)应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。(4)枚举法常用于解决“是否存在”或“有多少种可能”等问题。 2. 枚举的框架描述n=0;for(k=;k=;k+) / 控制枚举范围 if() / 根据约束条件实施筛选 printf(

5、); / 输出解 n+; / 统计解的个数 3. 枚举的实施步骤（1）根据问题的具体情况确定枚举量（简单变量或数组）；（2）根据问题的具体实际确定枚举范围，设置枚举循环；（3）根据问题的具体要求确定筛选（约束）条件；（4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。 1.2分治算法1. 分治算法的基本思想：对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。即将将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便

6、各个击破，分而治之。2. 分治算法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3. 分治算法的基本步骤： divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=di

7、vide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。1.3 动态规划算法1. 动态规划的概念(1) 动态规划（Dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。 (2) 动态规划处理的对象是多阶段决策问题。(3) 多

8、阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。2. 动态规划实施步骤 （1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。（2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。（3）应用递推求解最优

9、值。递推计算最优值是动态规划算法的实施过程。（4）根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。2 问题分析与算法设计2.1蛮力算法的设计 设序列子段的手段的首项为i（i=0，2，n-1）,尾项为j(j=i，n-1)，该子段和为sum。设置i，j二重循环枚举，可确保所有子段既不重复也不遗漏。每一子段和sum与最大变量值msum比较，可得最大子段和，同时用变量c,r分别记录最大子段的首尾标号。最后输出最大子段的各个数和最大子段和msum。2.2 分治算法的设计按照平衡原则，把序列分解为两个子序列（a1，a2，an/2），（an/2+1，an/2+2，an）。整个

10、序列的最大子段和会出现以下三种情形：序列（a1，a2，an）的最大子段和为子序列（a1，a2，an/2）的最大子段和；序列（a1，a2，an）的最大子段和为子序列（an/2+1，an/2+2，an）的最大子段和；序列（a1，a2，an）的最大子段和为,1in/2,n/2+1jn。求解子问题：对于以上的情形和，可递归求解。对于情形，需分别计算s1=max，1in/2s2= max,n/2+1jn则msum=s1+s2为情形的最大子段和。比较3个子问题的求解结果，最大值为原问题的解。定义数组an存放序列（a1，a2，an），变量left、right分别存放序列首尾元素下标，变量msum存放最大子段

11、和。定义递归函数maxsum（left，right）。当left=right时，即序列中只有一个元素，则msum=aleft,返回（递归出口）。当leftright时，用分治策略求解。2.3 动态规划算法的设计 设置b数组，设bi为序列前i项且以第i项为尾项的子段和的最大值，b0=a0,即bj= max ，1in, 1ji有bi的定义，可得bi+1的递推公式：bi+1=ai+1， bi0, 0i0,0in用递推完成最大子段和的求解：每得到一个bi，与msum比较得最大和msum；同时用变量k记录最大子段的尾标号i,最后用求和求出最大子段的首项标号。3 算法实现3.2蛮力算法的实现根据本问题的蛮

12、力算法设计，使用C语言实现该算法：void main() 手动输入或自动生成序列的各个值； msum=0; for(i=0;in;i+) /蛮力算法求出最大子段和，各序列的首项为i sum=0; for(j=i;jmsum) msum=sum;c=i;r=j; 输出原问题的解；3.2 分治算法的实现根据本问题的分治算法设计，使用C语言实现该算法：int maxsum(int left,int right) /递归函数 int i,msum; int center,leftsum,rightsum; int s1,s2,lefts,rights; if(left=right) /递归出口 if(

13、aleft=left;i-) lefts=lefts+ai; if(leftss1) s1=lefts;c=i; s2=0;rights=0; for(i=center+1;is2) s2=rights;r=i; msum=s1+s2;f=0; /最大子段和问题的解就是子问题3的解 if(msumleftsum)msum=leftsum;f=1; /最大子段和问题的解就是子问题1的解 if(msumrightsum) msum=rightsum;f=2; /最大子段和问题的解就是子问题2的解 return msum;void fenzhi() /分治策略函数 手动输入或自动生成序列的各个值；

14、left=0;right=n-1; unsigned uStartTime = GetTickCount(); /程序运行的开始时间 for(i=0;i100;i+) /循环100次蛮力算法，来算时间 msum=maxsum(left,right); /调用递归函数实现分治策略输出原问题的解；3.3 动态规划算法的实现根据本问题的动态规划算法设计，使用C语言实现该算法：void dongtai() /动态规划函数 手动输入或自动生成序列的各个值; b0=a0;msum=0; /用bi数组来存放序列前j项且以第i项为尾项的子段和的最大值 for(i=0;in;i+) /动态规划算法 if(bim

15、sum) msum=bi;k=i; 输出原问题的解;4 测试和分析4.1蛮力算法测试手动输入：1，2，3，4，5；截图：-1，-2.，-3，-4，-5截图：-1截图：-1，9，-2，3，-4截图：n=100,自动生成序列n=1000, 自动生成序列n=10000, 自动生成序列4.2蛮力算法时间复杂度的分析在蛮力算法中，设计了二重循环枚举序列的所有子段。显然枚举实现最大子段和的时间复杂度为O（n）。4.3 分治算法测试手动输入：1，2，3，4，5；截图：手动输入：-1，-2.，-3，-4，-5截图：手动输入：-1截图：手动输入：-1，9，-2，3，-4截图：n=100,自动生成序列截图：n=1

16、000, 自动生成序列截图：n=10000, 自动生成序列截图：4.4分治算法时间复杂度的分析分治算法用到了递归，从理论和算法实际运行情况分析该算法的时间复杂度为O (nlogn)4.5 动态规划算法测试给手动输入：1，2，3，4，5；截图：手动输入：-1，-2.，-3，-4，-5截图：手动输入：-1截图：手动输入：-1，9，-2，3，-4截图：n=100,自动生成序列。截图：n=1000, 自动生成序列截图：n=10000, 自动生成序列截图：4.6 动态规划算法时间复杂度的分析动态规划设计在一重循环中实现，可知动态规划求解的时间复杂度为O(n)。4.7 三种算法的比较从程序实际运行的时间各

17、种算法进行比较，可知动态规划算法的效率最高，其次是分治算法，最后是蛮力算法。5 总结 在这次课程设计中，我的收获还是蛮多的，通过这个最大子段和问题的求解，让我对分支策略和动态规划的算法思想更加理解，并且能通过比较程序的运行时间来比较各种算法的复杂度，因为这是以前我没有做过的事。通过这次课程设计，我认识到了算法设计在编程中的重要性，一个可靠性好的、高质量的程序是需要好的算法来支撑的，所以算法的选择在编程应用中真的非常重要，当然自己在算法设计这一领域，还不是很精通熟练，我想自己在课下还是会多多上机练习的。参考文献1 吕国英算法设计与分析第2版北京：清华大学出版社，20112 王晓东算法设计与分析 北京，清华大学出版社，2009附录所有的程序代码：见20121611035李婉秋.cpp课程设计成绩评定表成绩评定项 目比例得 分平时成绩（百分制记分）30%业务考核成绩（百分制记分）70%总评成绩（百分制记分）100%评定等级优 良 中 及格 不及格指导教师（签名）：20 年 月 日