最大子段和问题实验报告.pdf
版权申诉
59 浏览量
2023-02-22
21:44:34
上传
评论
收藏 236KB PDF 举报
实验四 最大子段和问题
〔1〕掌握动态规划的设计思想并能熟练运用；
〔2〕理解这样一个观点：同样的问题可以用不同的方法解决，一个好的算法是反复努力和
重新修正的结果；
〔1〕分别用蛮力法、分治法和动态规划法设计最大子段和问题的算法；
〔2〕比较不同算法的时间性能；
〔3〕给出测试数据，写出程序文档；
3.实验设备和软件环境
操作系统：Windows 7〔64x〕
开发工具：Visual Studio 2013
4. 实验步骤
以下实验数据都是以数组 a[]={-2, 11, -4, 13, -5, -2}为例子；
蛮力法
蛮力法是首先通过两个 for 循环去求出所有子段的值，然后通过if 语句查找出 maxsum，返
回子序列的最大子段和；
分治法
（1） 划分：按照平衡子问题的原则，将序列〔 a1，a2，…，an〕划分成长度相同的两个
子序列〔a1，a2，...，an/2〕和〔an/2+1,…,an〕;
（2） 求解子问题：对与划分阶段的情况①和②可递归求解，情况③需要分别计算
资源评论
