最大子段和问题课程设计

《最大子段和问题课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、011．[2]王晓东．算法设计与分析．北京，清华大学出版社，2009．[3]徐士良．计算机常用算法．第2版．北京，清华大学出版社出版，2010．指导教师（签名）：20年月日21目录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分治算法时间复杂度

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

5、<=<区间上限>;k++)//控制枚举范围if(<约束条件>)//根据约束条件实施筛选{printf(<满足要求的解>);//输出解n++;//统计解的个数}3.枚举的实施步骤（1）根据问题的具体情况确定枚举量（简单变量或数组）；（2）根据问题的具体实际确定枚举范围，设置枚举循环；（3）根据问题的具体要求确定筛选（约束）条件；（4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。211.2分治算法1.分治算法的基本思想：对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容

6、易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。即将将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。2.分治算法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。3.分治算法的基本步骤：divide-and-conquer(P){if(

7、

8、P

9、<=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题for(i=1,i<=k,i++)yi=divide-and-conquer(Pi);//递归的解各子问题returnmerge(y1,...,yk);//将各子问题的解合并为原问题的解}人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思

10、想，它几乎总是比子问题规模不等的做法要好。211.3动态规划算法1.动态规划的概念(1)动态规划（Dynamicprogramming）是运筹学的一个分支，是求解决策过程最优化的