最大子段和问题.docx
《最大子段和问题.docx》由会员分享，可在线阅读，更多相关《最大子段和问题.docx（19页珍藏版）》请在冰点文库上搜索。
最大子段和问题
《算法设计与分析》
课程设计报告
题目：
最大子段和问题
院（系）：
信息科学与工程学院
专业班级：
软件工程1201班
2014年12月29日至2015年1月9日
算法设计与分析课程设计任务书
一、设计题目
最大子段和问题
问题描述：
给定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）=20即=20i=2，j=4
二、设计主要内容
具体要求如下：
（1）使用蛮力算法实现
（2）使用分治策略算法实现
（3）使用动态规划算法实现
（4）对各种算法的时间复杂度进行分析和比较。
（5）设计出相应的菜单，通过菜单的选择实现各个功能
三、原始资料
无
四、要求的设计成果
（1）实现该系统功能的程序代码
（2）撰写符合规范要求的课程设计报告
五、进程安排
序号
课程设计内容
学时分配
备注
1
选题与搜集资料
1天
2
分析与设计
1天
3
模块实现
4天
4
系统调试与测试
2天
5
撰写课程设计报告
2天
合计
10天
六、主要参考资料
[1]吕国英．算法设计与分析．第2版．北京：
清华大学出版社，2011．
[2]王晓东．算法设计与分析．北京，清华大学出版社，2009．
[3]徐士良．计算机常用算法．第2版．北京，清华大学出版社出版，2010．
指导教师（签名）：
20年月日
目录
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++;//统计解的个数
}
3.枚举的实施步骤
（1）根据问题的具体情况确定枚举量（简单变量或数组）；
（2）根据问题的具体实际确定枚举范围，设置枚举循环；
（3）根据问题的具体要求确定筛选（约束）条件；
（4）设计枚举程序并运行、调试，对运行结果进行分析与讨论。
1.2分治算法
1.分治算法的基本思想：
对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
即将将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
2.分治算法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
3.分治算法的基本步骤：
divide-and-conquer（P）
{
if（|P|<=n0）adhoc（P）;//解决小规模的问题
dividePintosmallersubinstancesP1,P2,...,Pk；//分解问题
for（i=1,i<=k,i++）
yi=divide-and-conquer（Pi）;//递归的解各子问题
returnmerge（y1,...,yk）;//将各子问题的解合并为原问题的解
}
人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。
即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
这种使子问题规模大致相等的做法是出自一种平衡（balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。
1.3动态规划算法
1.动态规划的概念
（1）动态规划（Dynamicprogramming）是运筹学的一个分支，是求解决策过程最优化的数学方法。
（2）动态规划处理的对象是多阶段决策问题。
（3）多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。
对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。
多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。
2.动态规划实施步骤
（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。
（2）将问题各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推关系，并确定初始条件。
分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。
（3）应用递推求解最优值。
递推计算最优值是动态规划算法的实施过程。
（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，…，a[n/2]），（a[n/2]+1，a[n/2]+2，…，an）。
整个序列的最大子段和会出现以下三种情形：
①序列（a1，a2，…，an）的最大子段和为子序列（a1，a2，…，a[n/2]）的最大子段和；
②序列（a1，a2，…，an）的最大子段和为子序列（a[n/2]+1，a[n/2]+2，…，an）的最大子段和；
③序列（a1，a2，…，an）的最大子段和为
1≤i≤[n/2],[n/2]+1≤j≤n。
求解子问题：
对于以上的情形①和②，可递归求解。
对于情形③，需分别计算
s1=max
，1≤i≤[n/2]
s2=max
[n/2]+1≤j≤n
则msum=s1+s2为情形③的最大子段和。
比较3个子问题的求解结果，最大值为原问题的解。
定义数组a[n]存放序列（a1，a2，…，an），变量left、right分别存放序列首尾元素下标，变量msum存放最大子段和。
定义递归函数maxsum（left，right）。
当left=right时，即序列中只有一个元素，则msum=a[left],返回（递归出口）。
当left2.3动态规划算法的设计
设置b数组，设b[i]为序列前i项且以第i项为尾项的子段和的最大值，b[0]=a[0],即
b[j]=max{
}，1≤i≤n,
1≤j≤i
有b[i]的定义，可得b[i+1]的递推公式：
b[i+1]=｛a[i+1]，b[i]≤0,
0≤i={b[i]+a[i+1]，b[i]>0,0≤i用递推完成最大子段和的求解：
每得到一个b[i]，与msum比较得最大和msum；同时用变量k记录最大子段的尾标号i,最后用求和求出最大子段的首项标号。
3算法实现
3.2蛮力算法的实现
根据本问题的蛮力算法设计，使用C语言实现该算法：
voidmain（）
{
手动输入或自动生成序列的各个值；
msum=0;
for（i=0;i{
sum=0;
for（j=i;j{sum=sum+a[j];if（sum>msum）{msum=sum;c=i;r=j;}
}
输出原问题的解；
}
3.2分治算法的实现
根据本问题的分治算法设计，使用C语言实现该算法：
intmaxsum（intleft,intright）//递归函数
{
inti,msum;
intcenter,leftsum,rightsum;
ints1,s2,lefts,rights;
if（left==right）//递归出口
{
if（a[left]<0）msum=0;
elsemsum=a[left];
returnmsum;
}
center=（left+right）/2;//分解原问题
leftsum=maxsum（left,center）;//子问题1和子问题2递归调用
rightsum=maxsum（center+1,right）;
s1=0;lefts=0;//求解子问题3
for（i=center;i>=left;i--）
{
lefts=lefts+a[i];
if（lefts>s1）{s1=lefts;c=i;}
}
s2=0;rights=0;
for（i=center+1;i<=right;i++）
{
rights=rights+a[i];
if（rights>s2）{s2=rights;r=i;}
}
msum=s1+s2;f=0;//最大子段和问题的解就是子问题3的解
if（msumif（msumreturnmsum;
}
voidfenzhi（）//分治策略函数
{
手动输入或自动生成序列的各个值；
left=0;right=n-1;
unsigneduStartTime=GetTickCount（）;//程序运行的开始时间
for（i=0;i<100;i++）//循环100次蛮力算法，来算时间
msum=maxsum（left,right）;//调用递归函数实现分治策略
输出原问题的解；
}
3.3动态规划算法的实现
根据本问题的动态规划算法设计，使用C语言实现该算法：
voiddongtai（）//动态规划函数
{
手动输入或自动生成序列的各个值;
b[0]=a[0];msum=0;//用b[i]数组来存放序列前j项且以第i项为尾项的子段和的最大值
for（i=0;i{
if（b[i]<=0）b[i+1]=a[i+1];
elseb[i+1]=b[i]+a[i+1];
if（b[i]>msum）
{msum=b[i];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=1000,自动生成序列
截图：
⑦n=10000,自动生成序列
截图：
4.4分治算法时间复杂度的分析
分治算法用到了递归，从理论和算法实际运行情况分析该算法的时间复杂度为O（nlog
n）
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三种算法的比较
从程序实际运行的时间各种算法进行比较，可知动态规划算法的效率最高，其次是分治算法，最后是蛮力算法。
5总结
在这次课程设计中，我的收获还是蛮多的，通过这个最大子段和问题的求解，让我对分支策略和动态规划的算法思想更加理解，并且能通过比较程序的运行时间来比较各种算法的复杂度，因为这是以前我没有做过的事。
通过这次课程设计，我认识到了算法设计在编程中的重要性，一个可靠性好的、高质量的程序是需要好的算法来支撑的，所以算法的选择在编程应用中真的非常重要，当然自己在算法设计这一领域，还不是很精通熟练，我想自己在课下还是会多多上机练习的。
参考文献
[1]吕国英．算法设计与分析．第2版．北京：
清华大学出版社，2011．
[2]王晓东．算法设计与分析．北京，清华大学出版社，2009．
附录
所有的程序代码：
见20121611035李婉秋.cpp
课程设计成绩评定表
成
绩
评
定
项目
比例
得分
平时成绩（百分制记分）
30%
业务考核成绩（百分制记分）
70%
总评成绩（百分制记分）
100%
评定等级
优良中及格不及格
指导教师（签名）：
20年月日
升级会员 