算法设计与分析习题解答-(第4版)

1星价 ¥42.5 (7.2折)

2星价￥42.5 定价￥59.0

作者：王晓东

出版社：清华大学出版社

本类榜单：教材

分类：教材 > 研究生/本科/专科教材 > 工学

暂无评论

图文详情

ISBN：9787302511069
装帧：一般胶版纸
册数：暂无
重量：暂无
开本：16开
页数：387
出版时间：2018-11-01
条形码：9787302511069 ; 978-7-302-51106-9

本书特色

本书是《算法设计与分析(第4版)》配套的辅助教材，对主教材中的全部习题做了详尽的解答，并提供了应用实验型习题的全部测试数据。本书的内容是对主教材深入的扩展，许多主教材中无法讲述的较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，本书将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能上机实现。教学实践反映这类算法实现题的教学效果非常好。作者还结合国家级精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。本书结合原教材的内容，进一步讨论和讲解原教材中的重点和难点，问题分析，求解思路和方法，为读者深刻体会问题求解的核心思想提供帮助。由于原教材的内容有一定的深度和难度，读者在学习和解答习题过程中会遇到一定的困难，因此本书选择了原教材的一些典型的习题和难题，给出详细的解答和分析。本书内容丰富，观点新颖，理论联系实际。不仅可用作高等院校计算机科学与工程专业本科生和研究生学习计算机算法设计的辅教教材，而且也适合广大工程技术人员和自学读者学习参考。本书是学习算法设计与分析的经典教材学习辅导用书，清华大学出版社配套开发了丰富的在线教学资源，可以在清华大学出版社的在线教学平台上进行练习与测试，实现教学互动、智能学习。王晓东教授力作，算法经典畅销书新作，国家级精品课程配套教材，凝练精品课程建设成果本书结合主教材的内容，进一步讨论和讲解主教材中的重点和难点，问题分析，求解思路和方法，为读者深刻体会问题求解的核心思想提供帮助。由于原教材的内容有一定的深度和难度，读者在学习和解答习题过程中会遇到一定的困难，因此本书选择了原教材的一些典型的习题和难题，给出详细的解答和分析。

内容简介

本书是《算法设计与分析（第4版）》配套辅助教材。本书将结合原教材的内容，进一步讨论和讲解原教材中的重点和难点，问题分析，求解思路和方法，为读者深刻体会问题求解的核心思想提供帮助。由于原教材的内容有一定的深度和难度，读者在学习和解答习题过程中会遇到一定的困难，因此本书选择了原教材的一些典型的习题和难题，给出详细的解答和分析。本书内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。

节选

可用归纳设计策略解此问题。归纳假设是：已知计算序列a［0:i-1］(i 用归纳设计策略解题时，归纳假设对应于算法循环中的循环不变式。本题的循环不变式P是： P: k是序列a［0:i］的*长递增子序列的长度，0≤i 容易看出在由i-1到i的循环中，a［i］的值起关键作用。如果a［i］能扩展序列a［0:i-1］的*长递增子序列的长度，则k=k+1，否则k不变。设a［0:i-1］的长度为k的*长递增子序列的结尾元素是a［j］(0≤j≤i-1)，则当a［i］≥a［j］时可以扩展，否则不能扩展。如果序列a［0:i-1］中有多个长度为k的*长递增子序列，那么需要存储哪些信息？容易看出，只要存储序列a［0:i-1］中所有长度为k的递增子序列中结尾元素的*小值b［k］即可。因此，需要将循环不变式P增强为： P: 0≤i b［k］是序列a［0:i］中所有长度为k的递增子序列中的*小结尾元素值。动态规划第 3 章算法设计与分析习题解答（第4版）相应的归纳假设也增强为：已知计算序列a［0:i-1］(i 增强归纳假设后，在由i-1到i的循环中，当a［i］≥b［k］时，k=k+1，b［k］=a［i］,否则k值不变。注意到当a［i］≥b［k］时,k值增加，b［k］的值为a［i］。那么当a［i］按上述思想设计的算法可实现如下：public static int LIS() { int i=1,k; b［1］=a［0］; for (i=1,k=1;i { if (a［i］＞=b［k］) b［++k］=a［i］; else b［binary(i,k)］=a［i］; } return k; }static int binary(int i, int k) { int h,j; if (a［i］ for(h=1, j=k; h!=j-1;) { if (b［k=(h+j)/2］＜=a［i］) h=k; else j=k; } return j; }binary(i,k)用二分搜索算法在b［1:k］中找到下标j，使得b［j-1］≤a［i］给定由n个英文单词组成的一段文章，每个单词的长度(字符个数)依序为l1，l2，…,ln。要在一台打印机上将这段文章“漂亮”地打印出来。打印机每行*多可打印M个字符。这里所说的“漂亮”的定义如下：在打印机所打印的每一行中，行首和行尾可不留空格；行中每两个单词之间留一个空格；如果在一行中打印从单词i到单词j的字符，则按打印规则，应在一行中恰好打印∑jk=ilk+j－i个字符(包括字间空格字符)，且不允许将单词打破。多余的空格数为M－j+i－∑jk=ilk；除文章的*后一行外，希望每行多余的空格数尽可能少。因此，以各行(*后一行除外)的多余空格数的立方和达到*小作为“漂亮”的标准。试用动态规划算法设计一个“漂亮打印”方案，并分析算法的计算复杂性。