最大子段和问题.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， ij，求出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) 使用分治策略算法实现(3) 使用动态规划算法实现(4) 对各种算法的时间复杂度进行分析和比较。(5) 设计出相应的菜单，通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1) 实现该系统功能的程序代码(2) 撰写符合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料1 吕国英算法设计与分析第2版北京：清华大学出版社，20112 王晓东算法设计与分析 北京，清华大学出版社，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 三种算法的比较205 总结20参考文献20附录20221 常用算法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); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。1.3 动态规划算法1. 动态规划的概念(1) 动态规划（Dynamic programming）是运筹学的一个分支，是求解决策过程最优化的数学方法。 (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，an/2），（an/2+1，an/2+2，an）。整个序列的最大子段和会出现以下三种情形：序列（a1，a2，an）的最大子段和为子序列（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）。当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() 手动输入或自动生成序列的各个值； 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(leftss1) 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 = GetTickCount(); /程序运行的开始时间 for(i=0;i100;i+) /循环100次蛮力算法，来算时间msum=maxsum(left,right); /调用递归函数实现分治策略输出原问题的解；3.3 动态规划算法的实现根据本问题的动态规划算法设计，使用C语言实现该算法：void dongtai() /动态规划函数手动输入或自动生成序列的各个值;b0=a0;msum=0; /用bi数组来存放序列前j项且以第i项为尾项的子段和的最大值for(i=0;in;i+) /动态规划算法 if(bimsum) msum=bi;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 (nlogn)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版北京：清华大学出版社，20112 王晓东算法设计与分析 北京，清华大学出版社，2009附录所有的程序代码：见20121611035李婉秋.cpp课程设计成绩评定表成绩评定项 目比例得 分平时成绩（百分制记分）30%业务考核成绩（百分制记分）70%总评成绩（百分制记分）100%评定等级优 良 中 及格 不及格指导教师（签名）：20 年 月 日1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究2. 基于单片机的嵌入式Web服务器的研究 3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究 4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制 5. 基于MCS-51系列单片机的通用控制模块的研究 6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器7. 单片机控制的二级倒立摆系统的研究8. 基于增强型51系列单片机的TCP/IP协议栈的实现 9. 基于单片机的蓄电池自动监测系统 10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究11. 基于单片机的作物营养诊断专家系统的研究 12. 基于单片机的交流伺服电机运动控制系统研究与开发 13. 基于单片机的泵管内壁硬度测试仪的研制 14. 基于单片机的自动找平控制系统研究 15. 基于C8051F040单片机的嵌入式系统开发 16. 基于单片机的液压动力系统状态监测仪开发 17. 模糊Smith智能控制方法的研究及其单片机实现 18. 一种基于单片机的轴快流CO,2激光器的手持控制面板的研制 19. 基于双单片机冲床数控系统的研究 20. 基于CYGNAL单片机的在线间歇式浊度仪的研制 21. 基于单片机的喷油泵试验台控制器的研制 22. 基于单片机的软起动器的研究和设计 23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究 24. 基于单片机的机电产品控制系统开发 25. 基于PIC单片机的智能手机充电器 26. 基于单片机的实时内核设计及其应用研究 27. 基于单片机的远程抄表系统的设计与研究 28. 基于单片机的烟气二氧化硫浓度检测仪的研制 29. 基于微型光谱仪的单片机系统 30. 单片机系统软件构件开发的技术研究 31. 基于单片机的液体点滴速度自动检测仪的研制32. 基于单片机系统的多功能温度测量仪的研制 33. 基于PIC单片机的电能采集终端的设计和应用 34. 基于单片机的光纤光栅解调仪的研制 35. 气压式线性摩擦焊机单片机控制系统的研制 36. 基于单片机的数字磁通门传感器 37. 基于单片机的旋转变压器-数字转换器的研究 38. 基于单片机的光纤Bragg光栅解调系统的研究 39. 单片机控制的便携式多功能乳腺治疗仪的研制 40. 基于C8051F020单片机的多生理信号检测仪 41. 基于单片机的电机运动控制系统设计 42. Pico专用单片机核的可测性设计研究 43. 基于MCS-51单片机的热量计 44. 基于双单片机的智能遥测微型气象站 45. MCS-51单片机构建机器人的实践研究 46. 基于单片机的轮轨力检测 47. 基于单片机的GPS定位仪的研究与实现 48. 基于单片机的电液伺服控制系统 49. 用于单片机系统的MMC卡文件系统研制 50. 基于单片机的时控和计数系统性能优化的研究 51. 基于单片机和CPLD的粗光栅位移测量系统研究 52. 单片机控制的后备式方波UPS 53. 提升高职学生单片机应用能力的探究 54. 基于单片机控制的自动低频减载装置研究 55. 基于单片机控制的水下焊接电源的研究 56. 基于单片机的多通道数据采集系统 57. 基于uPSD3234单片机的氚表面污染测量仪的研制 58. 基于单片机的红外测油仪的研究 59. 96系列单片机仿真器研究与设计 60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造 61. 基于单片机的温度智能控制系统的设计与实现 62. 基于MSP430单片机的电梯门机控制器的研制 63. 基于单片机的气体测漏仪的研究 64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器 65. 基于单片机和DSP的变压器油色谱在线监测技术研究 66. 基于单片机的膛壁温度报警系统设计 67. 基于AVR单片机的低压无功补偿控制器的设计 68. 基于单片机船舶电力推进电机监测系统 69. 基于单片机网络的振动信号的采集系统 70. 基于单片机的大容量数据存储技术的应用研究 71. 基于单片机的叠图机研究与教学方法实践 72. 基于单片机嵌入式Web服务器技术的研究及实现 73. 基于AT89S52单片机的通用数据采集系统 74. 基于单片机的多道脉冲幅度分析仪研究 75. 机器人旋转电弧传感角焊缝跟踪单片机控制系统 76. 基于单片机的控制系统在PLC虚拟教学实验中的应用研究77. 基于单片机系统的网络通信研究与应用 78. 基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究79. 基于单片机的模糊控制器在工业电阻炉上的应用研究 80. 基于双单片机冲床数控系统的研究与开发 81. 基于Cygnal单片机的C/OS-的研究82. 基于单片机的一体化智能差示扫描量热仪系统研究 83. 基于TCP/IP协议的单片机与Internet互联的研究与实现 84. 变频调速液压电梯单片机控制器的研究 85. 基于单片机-免疫计数器自动换样功能的研究与实现 86. 基于单片机的倒立摆控制系统设计与实现 87. 单片机嵌入式以太网防盗报警系统 88. 基于51单片机的嵌入式Internet系统的设计与实现 89. 单片机监测系统在挤压机上的应用 90. MSP430单片机在智能水表系统上的研究与应用 91. 基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用92. 单片机在高楼恒压供水系统中的应用 93. 基于ATmega16单片机的流量控制器的开发 94. 基于MSP430单片机的远程抄表系统及智能网络水表的设计95. 基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计 96. 基于单片机的氨分解率检测系统的研究与开发 97. 锅炉的单片机控制系统 98. 基于单片机控制的电磁振动式播种控制系统的设计 99. 基于单片机技术的WDR-01型聚氨酯导热系数测试仪的研制 100. 一种RISC结构8位单片机的设计与实现 101. 基于单片机的公寓用电智能管理系统设计 102. 基于单片机的温度测控系统在温室大棚中的设计与实现103. 基于MSP430单片机的数字化超声电源的研制 104. 基于ADC841单片机的防爆软起动综合控制器的研究105. 基于单片机控制的井下低爆综合保护系统的设计 106. 基于单片机的空调器故障诊断系统的设计研究 107. 单片机实现的寻呼机编码器 108. 单片机实现的鲁棒MRACS及其在液压系统中的应用研究 109. 自适应控制的单片机实现方法及基上隅角瓦斯积聚处理中的应用研究110. 基于单片机的锅炉智能控制器的设计与研究 111. 超精密机床床身隔振的单片机主动控制 112. PIC单片机在空调中的应用 113. 单片机控制力矩加载控制系统的研究 项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！项目论证，项目可行性研究报告，可行性研究报告，项目推广，项目研究报告，项目设计，项目建议书，项目可研报告，本文档支持完整下载，支持任意编辑！选择我们，选择成功！单片机论文，毕业设计，毕业论文，单片机设计，硕士论文，研究生论文，单片机研究论文，单片机设计论文，优秀毕业论文，毕业论文设计，毕业过关论文，毕业设计，毕业设计说明，毕业论文，单片机论文，基于单片机论文，毕业论文终稿，毕业论文初稿，本文档支持完整下载，支持任意编辑！本文档全网独一无二，放心使用，下载这篇文档，定会成功！