最大子段和问题实验报告

实验四实验四 最大子段和问题最大子段和问题 1 1 实验目的实验目的 1 掌握动态规划的设计思想并能熟练运用 2 理解这样一个观点 同样的问题可以用不同的方法解决 一个好的算法是反复努力和 重新修正的结果 2 2 实验要求实验要求 1 分别用蛮力法 分治法和动态规划法设计最大子段和问题的算法 2 比较不同算法的时间性能 3 给出测试数据 写出程序文档 3 3 实验设备和软件环境实验设备和软件环境 操作系统 Windows 7 64x 开发工具 Visual Studio 2013 4 4 实验步骤实验步骤 以下实验数据都是以数组 a 2 11 4 13 5 2 为例子 蛮力法蛮力法 蛮力法是首先通过两个 for 循环去求出所有子段的值 然后通过 if 语句查找出 maxsum 返回子序列的最大子段和 分治法分治法 1 划分 按照平衡子问题的原则 将序列 a1 a2 an 划分成长度相同的两个 子序列 a1 a2 an 2 和 an 2 1 an 2 求解子问题 对与划分阶段的情况 和 可递归求解 情况 需要分别计算 s1 max 1 i n 2 s2 max n 2 1 j0 时 b j b j 1 a j 2 当 b j 1 0 时 b j a j 然后做递归操作求出最大子段和 5 5 实验结果实验结果 蛮力法蛮力法 include include using namespace std int manlifa int a int x int i j sum 0 maxsum 0 for i 0 i x i for j i 1 j sum sum a i if sum maxsum maxsum sum return maxsum int main int y sum int a 20 11 4 13 5 2 int c sizeof a sizeof int sum manlifa a c cout y return 0 分治法分治法 include include using namespace std int MaxSum int a int left int right int sum 0 midSum 0 leftSum 0 rightSum 0 int center s1 s2 lefts rights if left right sum a left else center left right 2 leftSum MaxSum a left center rightSum MaxSum a center 1 right s1 0 lefts 0 for int i center i left i lefts a i if lefts s1 s1 lefts s2 0 rights 0 for int j center 1 j s2 s2 rights midSum s1 s2 if midSum leftSum sum leftSum else sum midSum if sum rightSum sum rightSum return sum int main int sum int a 20 11 4 14 5 2 sum1 MaxSum a 0 5 cout sum1 endl int j n int b 100 cout n cout 请输入序列子段 for j 0 j b j int sum i sum MaxSum b 0 5 cout sum i return 0 动态规划法动态规划法 include using namespace std int MaxSum int n int a int sum 0 b 0 for int i 1 i 0 b a i else b a i if b sum sum b return sum int main int k int a 2 11 4 13 5 2 for int i 0 i 6 i cout a i cout endl cout 数组a的最大连续子段和为 MaxSum 6 a k return 0 6 6 讨论和分析讨论和分析 在一开始做最大子段问题的实验的时候 对于蛮力法和分治法的理解还是可以的 但是对 于动态规划法的理解还不是那么明确透彻 通过网上的一些解释和结合自己书本上的知识 对动态规划法得到了进一步的理解 接下来是三种算法时间性能的比较 蛮力法 时间