最大子段和问题.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] :清华大学出版社,2011.
[2] . 北京,清华大学出版社,2009.
[3] ,清华大学出版社出版,2010.
指导教师(签名):
20 年月日
目录
1 常用算法 6
6
7
动态规划算法 8
2 问题分析与算法设计 9
9
分治算法的设计 9
动态规划算法的设计 10
3 算法实现 10
10
分治算法的实现 11
动态规划算法的实现 13
4 测试和分析 13
13
15
分治算法测试 15
17
动态规划算法测试 17
动态规划算法时间复杂度的分析 19
三种算法的比较 20
5 总结 20
参考文献 20
附录 20
1 常用算法

1. 枚举的概念
(1)枚举法(Enumerate)也称为列举法、穷举法,是蛮力策略的体现,又称为蛮力法。
(2)枚举是一种简单而直接地解决问题的方法,其基本思想是逐一列举问题所涉及的所有情形。
(3)应用枚举时应注意对问题所涉及的有限种情形进行一一列举,既不能重复,又不能遗漏。
(4)枚举法常用于解决“是否存在”或“有多少种可能”等问题。
2. 枚举的框架描述
n=0;
for(k=<区间下限>;k<=<区间上限>;k++) // 控制枚举范围
if(<约束条件>) // 根据约束条件实施筛选
{ printf(<满足要求的解>); // 输出解
n++; // 统计解的个数
}
枚举的实施步骤
(1)根据问题的具体情况确定枚举量(简单变量或数组);
(2)根据问题的具体实际确定枚举范围,设置枚举循环;
(3)根据问题的具体要求确定筛选(约束)条件;
(4)设计枚举程序并运行、调试,对运行结果进行分析与讨论。

1. 分治算法的基本思想:对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。即将将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
2. 分治算法所能解决的问题一般具有以下几个特征:
该问题的规模缩小到一定的程度就可以容易地解决;
该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解;
该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
3. 分治算法的基本步骤:
divide-and-conquer(P)
{
if ( | P | <= n0) adhoc(P); //解决小规模的问题
divide P into smaller subinstances