算法分析课后习题答案资源-CSDN文库

需积分: 14 22 浏览量 2009-06-22 23:16:59 上传评论收藏 69KB DOC 举报

资源详情

资源评论

资源推荐

期末实验

姓名林惠彬学号

200603032

5

系别数计院班级 06 计教

课程名称

计算机算法分析

组员：赖丽云庄俏芸袁舒婷林其鹏肖富鹏童军乐

学号： 16 48 41 29 38 34

一、实验名称：最大子段和问题

二、实验目的：

最大子段和问题：通过对枚举法，改进的枚举法，二分策略法，动态规划法和递推算法这五种算法

的学习分析讨论，从中理解到，在面对问题的时候，用高级算法或者复杂的算法策略不一定必然设计出高

效率的算法，而是该由问题的特点分析决定使用的算法策略，从而达到灵活运用的效果，提高效率。

三、实验内容：

问题描述：给定 n 个整数（可能为负整数）a

1

，a

2

，…，a

n

，求形如：

a

i

,a

i+1

,...,a

j

i ,j =1,...,n, i<=j

的子段和的最大值。当所有整数均为负整数时定义其最大子段和为 0 。

例如（a

1

,a

2

,a

3

,a

4

,a

5

,a

6

）＝（－２，１１，－４，１３，－５，－２）时，最大子段和为： ∑a

k

　

＝２０

　　　

ｉ＝２，ｊ＝４（下标从１开始）

四、问题分析：　

算法设计１：

首先用简单的枚举算法来解决这个问题。枚举所有可能的起始下标（ｉ＝１，２，３，．．．，ｎ）

和终止下标（j=i，i+1，...,n）　累加 i 到 j 所有元素的和，并从中选取最大的子段和。

算法设计 2：

如果我们注意到：∑a

k

=

a

j

+∑a

j

即第 k 次计算的和可由前 k-1 次计算结果推算，算法 1 每次都从头

开始累加，显然没有必要。将算法 1 中的最内层的 for(k=i;k<=j;k=k+1) 循环省去，就可以避免重复

计算，从而使枚举法的实现得以改进。

算法设计 3：

前面两个改进只是减少了 i 一定时的重复计算操作。当 i 变化时 this_sum 被置 0 后，又重新开始累

加计算，其中必然仍会有很多重复计算。例如，当 i=1 时，已计算过下标为 1～5 元素的和；当 i=2 时，

还要再计算下标为 2～5 元素的和，不能利用以前累加的结果。

从结构上看，适合于用分治二分策略法进行求解。虽然并不独立，可对重叠的子问题进行专门处理，

并对它进行合并。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余9页未读，立即下载

评论0

内容反馈

llylyun

粉丝: 0
资源: 4

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip