算法设计与分析习题解答（第2版）

定　价：¥43.90

作　者：	王晓东
出版社：	清华大学出版社
丛编项：	普通高等教育"十一五"国家级规划教材
标　签：	计算机理论

购买这本书可以去

ISBN：	9787302167198	出版时间：	2008-02-01	包装：	平装
开本：	16	页数：	420 pages	字数：

内容简介

　　《21世纪大学本科计算机专业系列教材：算法设计与分析习题解答（第2版）》是清华大学出版社出版的普通高等教育“十一五”国家级规划教材《算法设计与分析（第2版）》（主教材）配套的辅助教材，对《算法设计与分析（第2版）》一书中的全部习题做了详尽的解答。《21世纪大学本科计算机专业系列教材：算法设计与分析习题解答（第2版）》的内容是对《算法设计与分析（第2版）》的较深入的扩展，许多在主教材中无法讲述的、较深入的主题通过习题的形式展现出来。为了加强学生灵活运用算法设计策略解决实际问题的能力，《21世纪大学本科计算机专业系列教材：算法设计与分析习题解答（第2版）》将主教材中的许多习题改造成算法实现题，要求学生不仅设计出解决具体问题的算法，而且能够上机实现。作者的教学实践反映出这类算法实现题的教学效果非常好。作者还结合国家精品课程建设，进行了教材的立体化开发，包括主教材、辅助教材、实验与设计、电子课件和教学网站建设。本书内容丰富，观点新颖，理论联系实际。不仅可以用作高等学校计算机科学与技术学科各专业本科生和研究生学习计算机算法设计的辅助教材，而且也适合广大工程技术人员和自学读者学习参考。

作者简介

　　王晓东，男，1957年3月出生，福州大学计算机系教授，福建省计算机学会理事长。研究领域是算法设计与算法评价，基于计算机网络和信息安全的大规模问题求解算法与数据结构，信息可视化技术，几何计算，并行和分布式算法设计，计算复杂性理论。先后主持了与算法设计与分析有关的国家自然科学基金项目、国家优秀留学回国人员基金项目、福建省杰出人才基金项目和省自然科学基金项日等7个研究课题；获德国家科技进步二等奖1项，省科技进步二等奖3项。主持国家精品课程算法与数据结构和算法设计与分析的课程建设，获福建省教学成果·等奖。在国内外重要学术刊物上发表有创见性的论文50余篇；出版《算法设计与分析》等学术著作7部，在算法复杂性研究方面取得r一系列理论研究和应用成果。例如，在对著名的凸壳问题的计算复杂性研究成果巾推广了关于判定树模型下问题的计算复杂性ji界著名的Ben-Or定理，并应用于分析凸壳问题的计算复杂性，在较一般的情况下改进和完善了网际算法界知名学者Aggarwal，Steele和Yao等提出的关于凸壳问题计算复杂性下界的结果。研究成果得到国内外同行专家的好评并被国内权威刊物所引用。

图书目录

习题1-1 实参交换1
习题1-2 方法头签名1
习题1-3 数组排序判定1
习题1-4 函数的渐近表达式2
习题1-5 O(1)和O(2)的区别2
习题1-7 按渐近阶排列表达式2
习题1-8 算法效率2
习题1-9 硬件效率3
习题1-10 函数渐近阶3
习题1-11 n!的阶4
习题1-12 平均情况下的计算时间复杂性4
算法实现题1-1 统计数字问题4
算法实现题1-2 字典序问题5
算法实现题1-3 最多约数问题6
算法实现题1-4 金币阵列问题8
算法实现题1-5 最大间隙问题11第2章递归与分治策略14
习题2-1 Hanoi 塔问题的非递归算法14

算法实现题2-1 输油管道问题（习题2-30) 49

习题3-1 最长单调递增子序列76
习题3-2 最长单调递增子序列的O(nlogn)算法77
习题3-7 漂亮打印78
习题3-11 整数线性规划问题79
习题3-12 二维背包问题80
习题3-14 Ackermann函数81
习题3-17 最短行驶路线83
习题3-19 最优旅行路线83
算法实现题3-1 独立任务最优调度问题（习题3-3) 83
算法实现题3-2 最少硬币问题（习题3-4) 85
算法实现题3-3 序关系计数问题（习题3-5) 86
算法实现题3-4 多重幂计数问题（习题3-6) 87

习题4-2 活动安排问题的贪心选择123

算法实现题4-1 会场安排问题（习题4-1) 128

习题5\|1 装载问题改进回溯法（一）153
习题5\|2 装载问题改进回溯法（二）154
习题5\|4 0-1背包问题的最优解155
习题5\|5 最大团问题的迭代回溯法156
习题5\|7 旅行售货员问题的费用上界157
习题5\|8 旅行售货员问题的上界函数158
算法实现题5-1 子集和问题（习题5-3) 159

习题6-1 0-1背包问题的栈式分支限界法229
习题6-2 用最大堆存储活结点的优先队列式分支限界法231
习题6-3 团顶点数的上界234
习题6-4 团顶点数改进的上界235
习题6-5 修改解旅行售货员问题的分支限界法235
习题6-6 解旅行售货员问题的分支限界法中保存已产生的排列树237
习题6-7 电路板排列问题的队列式分支限界法239
算法实现题6-1 最小长度电路板排列问题一（习题6-8) 241

习题7-1 模拟正态分布随机变量296

算法实现题7-1 模平方根问题（习题7-10) 307

习题8-1 RAM和RASP程序322

习题9-1 平面图着色问题的绝对近似算法336

算法实现题9-1 旅行售货员问题的近似算法（习题9-9) 346

习题10-1 算法obst的正确性365
习题10-2 矩阵连乘问题的O(n2)时间算法365
习题10-6 货物储运问题的费用371
习题10-7 Garsia算法371

第11章在线算法设计410
习题11-1 在线算法LFU的竞争性410
习题11-4 多读写头磁盘问题的在线算法410
习题11-6 带权页调度问题410
算法实现题11-1 最优页调度问题（习题11-2) 411
算法实现题11-2 在线LRU页调度（习题11-3) 414
算法实现题11-3 k服务问题（习题11-5) 416
参考文献422