文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 算法分析习题参考答案第五章
侵权投诉

算法分析习题参考答案第五章

算法分析习题参考答案第五章

1.最大子段和问题:给定整数序列 a1,a2, ,an,求该序列形如 ak的子段和

k i

j 的最大值: max 0,max ak 1 i j nk i j

1) 已知一个简单算法如下:

int Maxsum(int n,int a,int& best i,int& bestj){

int sum = 0;

for(int i=1;i<=n;i++){

int suma = 0;

for(int j=i;j<=n;j++){

suma + = a[j];

if(suma > sum){

sum = suma;

besti = i;

bestj = j;

}

}

}

return sum;

}试分析该算法的时间复杂性。

2) 试用分治算法解最大子段和问题,并分析算法的时间复杂性。

3) 试说明最大子段和问题具有最优子结构性质,并设计一个动态规划算法解最大子段和问题。分析算法的时间复杂度。

(提示:令b(j) max1 i j n a,j 1,2, ,n) k

k ij

解:1)分析按照第一章,列出步数统计表,计算可得O(n) 2

2)分治算法:将所给的序列a[1:n]分为两段a [1:n/2]、a[n/2+1:n],分别求出这两段的最大子段和,则a[1:n]的最大子段和有三种可能:

①a[1:n]的最大子段和与a[1:n/2]的最大子段和相同;

②a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同;

③a[1:n]的最大子段和为两部分的字段和组成,即

j a

l ij ai a n a n aj;

2 2 1

第1页

你可能喜欢

热门文档

相关文档

  • 算法分析习题参考答案第一章

    算法分析习题参考答案第...1/2 相关文档推荐 算法分析与设计 第1章习... 3...5 , x2 = 2 2 则可设 n F (n) = c1 x1n + c 2 x 2 5 由 F...

  • 第五章练习题参考答案及解析

    第五章练习题参考答案及解析一.单项选择题 1. 【答案】B 【解析】向不特定...对要约条件进行分析,对股东是否接受要约提出建 议,并聘请独立财务顾问提出专业...

  • 算法分析习题参考答案第八章

    算法分析习题参考答案第八章算法分析习题参考答案第八章隐藏>> 1.二元可满足性...5. 独立集问题: 例:对于给定的无向图 G = (V , E ) 和正整数 k (≤...

  • 数据结构与算法分析课后题答案

    数据结构与算法分析第五章课后题答案? ? ? ? 课后答案网,用心为你服务! ? ...最全最多的课后习题参考答案,尽在课后答案网(www.khdaw.com)! Khdaw团队一直...

  • 第5章课后习题参考答案

    第五章 习题参考答案 1.试编写一个绘制 Bezier .../*具体算法详见如下代码*/ for( i = 0; i < ...教育学第五章课后习题参... 2页 免费 电路分析课后...

  • 数值最优化算法与理论第五章习题答案

    数值最优化算法与理论第五章习题答案_工学_高等教育...2014年12月大学英语四级经典参考范文四季养生 中医养生...2014教师资格材料分析辅... 2014小学教师资格考试《...

  • 数据结构与算法第5章课后答案

    数据结构与算法第5章课后答案_工学_高等教育_教育专区。数据结构与算法 课后答案...【解答】2h -1,2h-1 【分析】最小结点个数的情况是第1层有1个结点,其他...

  • 第5章 数据结构与算法 习题与答案

    数据结构与算法分析习题及... 44页 2财富值 数据结构与算法习题二参考... 4...计算机科学概论(刘艺著)第5章 数据结构与算法 习题与答案计算机科学概论(刘艺著...

  • 第五章习题参考答案

    第五章习题参考答案_理学_高等教育_教育专区。自动原理第五章课后习题第...证券从业资格考试投资分析考点识记89份文档 爆笑大撞脸 超爆笑笑话 有趣及爆笑...

  • 第五章成本分析综合练习题参考答案

    第五章成本分析综合练习题参考答案 一、名词解释 1.机会成本:又称替换成本,是指生产者为了生产一定数量的产品所放弃的使用相同的生 产要素在其他生产用途中所能...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email