最大子段和问题.doc
《最大子段和问题.doc》由会员分享,可在线阅读,更多相关《最大子段和问题.doc(22页珍藏版)》请在咨信网上搜索。
1、算法设计与分析课程设计报告题 目: 最大子段和问题 院 (系): 信息科学与工程学院 专业班级: 软件工程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, ij,求出ai, ai+1,aj子段和的最大值。当所有整数均为负值时定义其最大子段还和为0。例如:当(a1, a2, a3 ,a4 ,a5,a6)=(-2, 11, -4, 13, -5, 2)时,最大子段和为(a2, a3, a
2、4)=20 即 =20 i=2,j=4二、设计主要内容具体要求如下:(1) 使用蛮力算法实现(2) 使用分治策略算法实现(3) 使用动态规划算法实现(4) 对各种算法的时间复杂度进行分析和比较。(5) 设计出相应的菜单,通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1) 实现该系统功能的程序代码(2) 撰写符合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料1 吕国英算法设计与分析第2版北京:清华大学出版社,20112 王晓东算法设计与分析 北京,清
3、华大学出版社,20093 徐士良计算机常用算法第2版北京,清华大学出版社出版,2010指导教师(签名): 20 年 月 日目 录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分治算法时间复杂度的分析174.5 动态规划算法测试174.6 动态规划算法时间复杂度的分析194.7
4、三种算法的比较205 总结20参考文献20附录20221 常用算法1.1蛮力算法1. 枚举的概念(1)枚举法(Enumerate)也称为列举法、穷举法,是蛮力策略的体现,又称为蛮力法。 (2)枚举是一种简单而直接地解决问题的方法,其基本思想是逐一列举问题所涉及的所有情形 。(3)应用枚举时应注意对问题所涉及的有限种情形进行一一列举,既不能重复,又不能遗漏。(4)枚举法常用于解决“是否存在”或“有多少种可能”等问题。 2. 枚举的框架描述n=0;for(k=;k=;k+) / 控制枚举范围 if() / 根据约束条件实施筛选 printf(); / 输出解 n+; / 统计解的个数 3. 枚举的
5、实施步骤(1)根据问题的具体情况确定枚举量(简单变量或数组);(2)根据问题的具体实际确定枚举范围,设置枚举循环;(3)根据问题的具体要求确定筛选(约束)条件;(4)设计枚举程序并运行、调试,对运行结果进行分析与讨论。 1.2分治算法1. 分治算法的基本思想:对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。即将将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。2. 分治算法所能解决的问题一般具有
6、以下几个特征:该问题的规模缩小到一定的程度就可以容易地解决;该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解;该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。3. 分治算法的基本步骤: divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk;/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各
7、子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。1.3 动态规划算法1. 动态规划的概念(1) 动态规划(Dynamic programming)是运筹学的一个分支,是求解决策过程最优化的数学方法。 (2) 动态规划处理的对象是多阶段决策问题。(3) 多阶段决策问题,是指这样的一类特殊的活动过程,问题可以分解
8、成若干相互联系的阶段,在每一个阶段都要做出决策,形成一个决策序列,该决策序列也称为一个策略。对于每一个决策序列,可以在满足问题的约束条件下用一个数值函数(即目标函数)衡量该策略的优劣。多阶段决策问题的最优化目标是获取导致问题最优值的最优决策序列(最优策略),即得到最优解。2. 动态规划实施步骤 (1)把所求最优化问题分成若干个阶段,找出最优解的性质,并刻划其结构特性。(2)将问题各个阶段时所处不同的状态表示出来,确定各个阶段状态之间的递推关系,并确定初始条件。分析归纳出各个阶段状态之间的转移关系是应用动态规划的关键。(3)应用递推求解最优值。递推计算最优值是动态规划算法的实施过程。(4)根据计
9、算最优值时所得到的信息,构造最优解。 构造最优解就是具体求出最优决策序列。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,an/2),(an/2+1,an/2+2,an)。整个序列的最大子段和会出现以下三种情形:序列(a1,a2,a
10、n)的最大子段和为子序列(a1,a2,an/2)的最大子段和;序列(a1,a2,an)的最大子段和为子序列(an/2+1,an/2+2,an)的最大子段和;序列(a1,a2,an)的最大子段和为,1in/2,n/2+1jn。求解子问题:对于以上的情形和,可递归求解。对于情形,需分别计算s1=max,1in/2s2= max,n/2+1jn则msum=s1+s2为情形的最大子段和。比较3个子问题的求解结果,最大值为原问题的解。定义数组an存放序列(a1,a2,an),变量left、right分别存放序列首尾元素下标,变量msum存放最大子段和。定义递归函数maxsum(left,right)。当
11、left=right时,即序列中只有一个元素,则msum=aleft,返回(递归出口)。当leftright时,用分治策略求解。2.3 动态规划算法的设计设置b数组,设bi为序列前i项且以第i项为尾项的子段和的最大值,b0=a0,即bj= max ,1in, 1ji有bi的定义,可得bi+1的递推公式:bi+1=ai+1, bi0, 0i0,0in用递推完成最大子段和的求解:每得到一个bi,与msum比较得最大和msum;同时用变量k记录最大子段的尾标号i,最后用求和求出最大子段的首项标号。3 算法实现3.2蛮力算法的实现根据本问题的蛮力算法设计,使用C语言实现该算法:void main()
12、手动输入或自动生成序列的各个值; msum=0; for(i=0;in;i+) /蛮力算法求出最大子段和,各序列的首项为i sum=0; for(j=i;jmsum) msum=sum;c=i;r=j; 输出原问题的解;3.2 分治算法的实现根据本问题的分治算法设计,使用C语言实现该算法:int maxsum(int left,int right) /递归函数int i,msum;int center,leftsum,rightsum;int s1,s2,lefts,rights;if(left=right) /递归出口if(aleft=left;i-)lefts=lefts+ai;if(le
13、ftss1) s1=lefts;c=i;s2=0;rights=0;for(i=center+1;is2) s2=rights;r=i;msum=s1+s2;f=0; /最大子段和问题的解就是子问题3的解if(msumleftsum)msum=leftsum;f=1; /最大子段和问题的解就是子问题1的解 if(msumrightsum) msum=rightsum;f=2; /最大子段和问题的解就是子问题2的解return msum;void fenzhi() /分治策略函数手动输入或自动生成序列的各个值; left=0;right=n-1; unsigned uStartTime = Ge
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最大 问题
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。