最大子段和问题.doc

《算法设计与分析》 课程设计报告 题 目： 最大子段和问题 院 （系）： 信息科学与工程学院 专业班级： 0 学生姓名： 0 学 号： 0 指导教师： 0 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 二、设计主要内容 具体要求如下： 使用蛮力算法实现 使用分治策略算法实现 使用动态规划算法实现 对各种算法的时间复杂度进行分析和比较。 设计出相应的菜单，通过菜单的选择实现各个功能 三、原始资料 杨克昌《计算机常用算法与程序设计案例教程》清华大学出版社2011.7 四、要求的设计成果 (1) 实现该系统功能的程序代码 (2) 撰写符合规范要求的课程设计报告 五、进程安排 序号 课程设计内容 学时分配 备注 1 选题与搜集资料 1天 2 分析与设计 1天 3 模块实现 4天 4 系统调试与测试 2天 5 撰写课程设计报告 2天 合计 10天 六、主要参考资料 [1] 吕国英．算法设计与分析．第2版．北京：清华大学出版社，2011． [2] 王晓东．算法设计与分析． 北京，清华大学出版社，2009． [3] 徐士良．计算机常用算法．第2版．北京，清华大学出版社出版，2010． 指导教师（签名）： 20 年 月 日 目 录 1. 常用算法…………………………………………………………………………………页码 1.1蛮力算法………………………………………………………………………………页码 1.2××××××××………………………………………………………………………页码 1.3××××××××………………………………………………………………………页码 问题分析与算法设计……………………………………………………………………页码 2.1××××××××………………………………………………………………………页码 2.2××××××××………………………………………………………………………页码 2.3××××××××………………………………………………………………………页码 算法实现…………………………………………………………………………………页码 3.1××××××××………………………………………………………………………页码 3.2××××××××………………………………………………………………………页码 3.3××××××××………………………………………………………………………页码 测试与分析………………………………………………………………………………页码 4.1××××××××………………………………………………………………………页码 4.2××××××××………………………………………………………………………页码 4.3××××××××………………………………………………………………………页码 4.4××××××××………………………………………………………………………页码 4.5××××××××………………………………………………………………………页码 4.6××××××××………………………………………………………………………页码 4.7××××××××………………………………………………………………………页码 总结………………………………………………………………………………………页码 ……………………………………… 参考文献………………………………………………………………………………………页码 附录（源代码）………………………………………………………………………………页码 PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT 1 1 常用算法 1.1蛮力算法 1.1.1蛮力算法的基本思想: 蛮力法是一种