-1 - 昆明理工大学信息工程与自动化学院学生实验报告 （ 2011 — 2012 学年 第 1 学期 ） 课程名称：算法设计与分析 开课实验室：信自楼机房 444 2012 年 12 月 14 日 年级、专业、班 学号 姓名 成绩 实验项目名称 最大子段和问题 指导教师 吴晟 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、上机目的及内容 1.上机内容 给定有 n 个整数（可能有负整数）组成的序列（a1,a2,…,an），求改序列形如jkka1的子段和的最大值，当所有整数均为负整数时，其最大子段和为 0。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线 图 （方框 原理图 或 程序流 程图 ） （1）分别 用蛮 力法、分治 法和动 态 规划 法设计最大子段和问题的算法； 蛮 力法设计原理： 利 用3 个 for 的嵌 套 （实现从 第 1 个数开始 计算子段长 度为 1，2，3…n 的子段和，同理计算出 第 2 个数开始 的长 度为 1，2，3…n-1 的子段和，依 次 类 推 到第 n 个数开始 计算的长 为 1 的子段和）和一个 if（用来 比 较 大小 ）,将 其所有子段的和计算出 来 并将 最大子段和赋 值给summax1。用了 3 个 for 嵌 套 所以 时间复杂性 为○ (n3)； -2- 分治法设计原理： 1）、划分：按照平衡子问题的原则，将序列（1a ，2a ，…，na ）划分成长度相同的两个字序列（1a ，…，2/na）和（ 12/na，…，na ）。 2）、求解子问题：对于划分阶段的情况分别的两段可用递归求解，如果最大子段和在两端之间需要分别计算 s1=)2/1(max2/nianikk，s2=)2/(max12/njnajnkk，则s1+s2为最大子段和。若然只在左边或右边，那就好办了，前者视 s1 为 summax2,后者视 s2 o summax2。 3）、合并：比较在划分...
