《算法设计与分析》课程设计报告-最大子段和问题.doc

《算法设计与分析》 课程设计报告 题 目： 最大子段和问题 院 （系）： 信息科学与工程学院 专业班级： 软件工程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， i≤j，求出ai， ai+1，…aj子段和的最大值。当所有整数均为负值时定义其最大子段还和为0。 例如：当(a1， a2， a3 ，a4 ，a5，a6)=(-2， 11， -4， 13， -5， 2)时，最 大子段和为(a2， a3， a4)=20 即 =20 i=2，j=4 二、设计主要内容 具体要求如下： 使用蛮力算法实现 使用分治策略算法实现 使用动态规划算法实现 对各种算法的时间复杂度进行分析和比较。 设计出相应的菜单，通过菜单的选择实现各个功能 三、原始资料 无 四、要求的设计成果 (1) 实现该系统功能的程序代码 (2) 撰写符合规范要求的课程设计报告 五、进程安排 序号 课程设计内容 学时分配 1 选题与搜集资料 1天 2 分析与设计 1天 3 模块实现 4天 4 系统调试与测试 2天 5 撰写课程设计报告 2天 合计 10天 六、主要参考资料 [1] 吕国英．第2版2011．[2] 王晓东．． 2009．．第2版．．1 常用算法 6 1.1蛮力算法 6 1.2分治算法 7 1.3 动态规划算法 8 2 问题分析与算法设计 9 2.1蛮力算法的设计 9 2.2 分治算法的设计 9 2.3 动态规划算法的设计 10 3 算法实现 10 3.2蛮力算法的实现 10 3.2 分治算法的实现 11 3.3 动态规划算法的实现 13 4 测试和分析 13 4.1蛮力算法测试 13 4.2蛮力算法时间复杂度的分析 15 4.3 分治算法测试 15 4.4分治算法时间复杂度的分析 17 4.5 动态规划算法测试 17 4.6 动态规划算法时间复杂度的分析 19 4.7 三种算法的比较 20 5 总结 20 参考文献 20 附录 20 1 常用算法 1.1蛮力算法 1. 枚举的概念 (1)枚举法（Enumerate）也称为列举法、穷举法，是蛮力策略的体现，又称为蛮力法。 (2)枚举是一种简单而直接地解决问题的方法，其基本思想是逐一列举问题所涉及的所有情形 。 (3)应用枚举时应注意对问题所涉及的有限种情形进行一一列举，既不能重复，又不能遗漏。 (4)枚举法常用于解决“是否存在”或“有多少种可能”等问题。 2. 枚举的框架描述 n=0; for(k=区间下限;k=区间上限;k++) // 控制枚举范围 if(约束条件) // 根据约束条件实施筛选 { printf(满足要求的解); // 输出解 n++; // 统计解的个数 } 枚举的实施步骤 （1）根据问题的具体情况确定枚举量（简单变量或数组）； （2）根据问题的具体实际确定枚举范围，设置枚举循环； （3）根据问题的具体要求确定筛选（约束）条件； （4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。 1.2分治算法 1. 分治算法的基本思想：对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。即将将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 2. 分治算法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3. 分治算法的基本步骤： divide-and-conquer(P) { if ( | P | = n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk；//分解问题