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

图书标准信息

• 作者 王晓东
• 出版社 清华大学出版社
• 出版时间 2018-11
• 版次 4
• ISBN 9787302511069
• 定价 59.00元
• 装帧 平装
• 开本 16开
• 页数 387页
• 字数 616千字

【内容简介】

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

【作者简介】

王晓东，福州大学计算机系教授，福建省计算机学会理事长。研究领域是算法设计与算法评价、基于计算机网络和信息安全的大规模问题求解算法与数据结构、信息可视化技术、几何计算、并行和分布式算法设计、计算复杂理论。主持自然科学项目、很好留学回国人员项目、福建省杰出人才项目和福建省自然科学项目等7个研究课题；获得科技进步奖1项，福建省科技进步奖3项。主持精品课程“算法与数据结构”和“算法设计与分析”的课程建设，获得2005年福建省成果。在靠前外重要学术刊物上发表有创见的50余篇，出版学术著作7部。在算法复杂研究方面取得了一系列理论研究成果和应用成果。

【目录】

章算法引论1
题1-1实际参数交换1
题1-2方法头1
题1-3数组排序判定1
题1-4函数的渐近表达式2
题1-5o(1)和o(2)的区别2
题1-6按渐近阶排列表达式2
题1-7算法效率2
题1-8硬件效率3
题1-9函数渐近阶3
题1-10n!的阶3
题1-11均情况下的计算时间复杂4
算法实现题1-1统字问题4
算法实现题1-2字典序问题5
算法实现题1-3多约数问题6
算法实现题1-4金币阵列问题7
算法实现题1-5优选间隙问题10
第2章递归与分治策略12
题2-1hanoi-塔问题的非递归算法12
题2-27个二分搜索算法13
题2-3改写二分搜索算法16
题2-4大整数乘法的o(nmlog(3/2))算法16
题2-55次n/3位整数的乘法17
题2-6矩阵乘法19
题2-7多项式乘积19
题2-8不动点问题的o(logn)时间算法19
题2-9主元素问题的线时间算法19
题2-10无序集主元素问题的线时间算法20
题2-11o(1)空间子数组换位算法20
题2-12o(1)空间合并算法22
题2-13n段合并排序算法28
题2-14自然合并排序算法29
题2-15优选值和小值问题的很优算法31
题2-16优选值和次大值问题的很优算法31
题2-17整数集合排序32
题2-18第k小元素问题的计算时间下界32
题2-19非增序快速排序算法33
题2-20化算法34
题2-21化快速排序算法34
题2-22排列算法34
题2-23算法qsort中的尾递归34
题2-24用栈模拟递归34
题2-25算法select中的元素划分35
题2-26o(nlogn)时间快速排序算法35
题2-27接近中位数的k个数36
题2-28x和y的中位数36
题2-29网络开关设计36
题2-30带权中位数问题37
题2-31构造gray码的分治算法39
题2-32网球循环赛程表40
算法实现题2-1输油管道问题44
算法实现题2-2众数问题44
算法实现题2-3邮局选址问题45
算法实现题2-4马的hamilton周游路线问题46
算法实现题2-5半数集问题54
算法实现题2-6半数单集问题55
算法实现题2-7士兵站队问题56
算法实现题2-8有重复元素的排列问题57
算法实现题2-9排列的字典序问题58
算法实现题2-10集合划分问题（一）60
算法实现题2-11集合划分问题（二）61
算法实现题2-12双hanoi塔问题62
算法实现题2-13标准二维表问题64
算法实现题2-14整数因子分解问题64
算法实现题2-15有向直线2中值问题65
第3章动态规划68
题3-1长单调递增子序列68
题3-2长单调递增子序列的o(nlogn)算法69
题3-3漂亮打印70
题3-4整数线规划问题71
题3-5二维背包问题71
题3-6ackermann函数72
算法实现题3-1独立任务很优调度问题74
算法实现题3-2少硬币问题76
算法实现题3-3序关系问题77
算法实现题3-4多重幂问题77
算法实现题3-5小m段和问题78
算法实现题3-6石子合并问题79
算法实现题3-7数字三角形问题81
算法实现题3-8乘法表问题82
算法实现题3-9租用游艇问题83
算法实现题3-10汽车加油行驶问题84
算法实现题3-11圈乘运算问题85
算法实现题3-12少费用购物91
算法实现题3-13优选长方体问题93
算法实现题3-14正则表达式匹配问题94
算法实现题3-15双调旅行售货员问题98
算法实现题3-16优选k乘积问题100
第4章贪心算法102
题4-1活动安排问题的贪心选择102
题4-2背包问题的贪心选择质102
题4-3特殊的0-1背包问题103
题4-4程序很优存储问题103
题4-5很优装载问题的贪心算法103
题4-6fibonacci序列的huffman编码104
题4-7很优前缀码的编码序列104
题4-8任务集独立问题104
题4-9矩阵拟阵104
题4-10小权优选独立子集拟阵105
题4-11整数边权prim算法105
题4-12优选权小生成树105
题4-13短路径的负边权105
题4-14整数边权dijkstra算法106
算法实现题4-1会场安排问题106
算法实现题4-2很优合并问题108
算法实现题4-3磁带很优存储问题108
算法实现题4-4磁盘文件很优存储问题109
算法实现题4-5程序存储问题110
算法实现题4-6很优服务次序问题111
算法实现题4-7多处很优服务次序问题112
算法实现题4-8d森林问题113
算法实现题4-9汽车加油问题114
算法实现题4-10区间覆盖问题115
算法实现题4-11硬币找钱问题116
算法实现题4-12删数问题116
算法实现题4-13数列极差问题117
算法实现题4-14嵌套箱问题118
算法实现题4-15套汇问题119
算法实现题4-16信号增强装置问题120
算法实现题4-17磁带优选利用率问题121
算法实现题4-18非单位时间任务安排问题122
算法实现题4-19多元huffman编码问题124
算法实现题4-20多元huffman编码变形125
算法实现题4-21区间相交问题127
算法实现题4-22任务时间表问题128
第5章回溯法129
题5-1装载问题改进回溯法（一）129
题5-2装载问题改进回溯法（二）130
题5-30-1背包问题的很优解130
题5-4优选团问题的迭代回溯法131
题5-5旅行售货员问题的费用上界132
题5-6旅行售货员问题的上界函数134
算法实现题5-1子集和问题134
算法实现题5-2小长度电路板排列问题135
算法实现题5-3小重量机器设计问题138
算法实现题5-4运动员很好匹配问题139
算法实现题5-5无分隔符字典问题140
算法实现题5-6无和集问题142
算法实现题5-7n方柱问题143
算法实现题5-8整数变换问题147
算法实现题5-9拉丁矩阵问题148
算法实现题5-10排列宝石问题150
算法实现题5-11重复拉丁矩阵问题152
算法实现题5-12罗密欧与朱丽叶的迷宫问题154
算法实现题5-13工作分配问题156
算法实现题5-14独立钻石跳棋问题157
算法实现题5-15智力拼图问题163
算法实现题5-16布线问题170
算法实现题5-17很好调度问题171
算法实现题5-18无优先级运算问题172
算法实现题5-1界名画陈列馆问题174
算法实现题5-20世界名画陈列馆问题（不重复监视）177
算法实现题5-21部落卫队问题179
算法实现题5-22虫蚀算式问题181
算法实现题5-23完备环序列问题184
算法实现题5-24离散01串问题186
算法实现题5-25喷漆机器人问题188
算法实现题5-26n2-1谜问题190
第6章分支限界法197
题6-10-1背包问题的栈式分支限界法197
题6-2用优选堆存储活结点的优先队列式分支限界法199
题6-3团顶点数的上界202
题6-4团顶点数改进的上界202
题6-5修改解旅行售货员问题的分支限界法202
题6-6解旅行售货员问题的分支限界法中保存已产生的排列树204
题6-7电路板排列问题的队列式分支限界法206
算法实现题6-1小长度电路板排列问题(一)207
算法实现题6-2小长度电路板排列问题(二)210
算法实现题6-3小权顶点覆盖问题213
算法实现题6-4无向图的优选割问题216
算法实现题6-5小重量机器设计问题219
算法实现题6-6运动员很好匹配问题221
算法实现题6-7n后问题223
算法实现题6-8圆排列问题225
算法实现题6-9布线问题227
算法实现题6-10很好调度问题229
算法实现题6-11无优先级运算问题232
算法实现题6-12世界名画陈列馆问题234
算法实现题6-13骑士征途问题237
算法实现题6-14推箱子问题238
算法实现题6-15图形变换问题243
算法实现题6-16行列变换问题246
算法实现题6-17重排n2宫问题247
算法实现题6-18长距离问题251
第7章概率算法257
题7-1模拟正态分布变量257
题7-2抽样算法258
题7-3产生m个整数258
题7-4集合大小的概率算法259
题7-5生问题259
题7-6易验证问题的拉斯维加斯算法260
题7-7用数组模拟有序链表261
题7-8o(n3/2)舍伍德型排序算法261
题7-9n后问题解的存在261
题7-10整数因子分解算法262
题7-11非蒙特卡罗算法的例子263
题7-12重复3次的蒙特卡罗算法264
题7-13集合元素算法264
题7-14由蒙特卡罗算法构造拉斯维加斯算法265
题7-15产生素数算法266
题7-16矩阵方程问题266
算法实现题7-1模方根问题267
算法实现题7-2集合相等问题268
算法实现题7-3逆矩阵问题269
算法实现题7-4多项式乘积问题270
算法实现题7-5皇后控制问题270
算法实现题7-63-sat问题273
算法实现题7-7战车问题274
算法实现题7-8圆排列问题276
算法实现题7-9骑士控制问题277
算法实现题7-10骑士对攻问题278
第8章np接近理论与近似算法280
题8-1析取范式的可满足280
题8-22-sat问题的线时间算法280
题8-3整数规划问题281
题8-4划分问题282
题8-5长简单回路问题283
题8-6面图着问题的近似算法283
题8-7很优程序存储问题284
题8-8树的很优顶点覆盖285
题8-9顶点覆盖算法的能比286
题8-10团的常数能比近似算法286
题8-11售货员问题的常数能比近似算法287
题8-12瓶颈旅行售货员问题287
题8-13很优旅行售货员回路不自相交288
题8-14集合覆盖问题的实例289
题8-15多机调度问题的近似算法290
题8-16lpt算法的坏情况实例291
题8-17多机调度问题的多项式时间近似算法292
算法实现题8-1旅行售货员问题的近似算法292
算法实现题8-2可满足问题的近似算法294
算法实现题8-3优选可满足问题的近似算法295
算法实现题8-4子集和问题的近似算法297
算法实现题8-5子集和问题的接近多项式时间近似算法297
算法实现题8-6实现算法greedysetcover298
算法实现题8-7装箱问题的近似算法first fit301
算法实现题8-8装箱问题的近似算法best fit303
算法实现题8-9装箱问题的近似算法first fit decreasing305
算法实现题8-10装箱问题的近似算法best fit decreasing305
算法实现题8-11装箱问题的近似算法next fit306
第9章串与序列的算法309
题9-1简单子串搜索算法坏情况复杂309
题9-2后缀重叠问题309
题9-3改进前缀函数310
题9-4确定所有匹配位置的kmp算法311
题9-5特殊情况下简单子串搜索算法的改进311
题9-6简单子串搜索算法的均能312
题9-7带间隙字符的模式串搜索312
题9-8串接的前缀函数313
题9-9串的循环旋转314
题9-10失败函数质314
题9-11输出函数质315
题9-12后缀数组类315
题9-13长公共扩展查询316
题9-14长公共扩展质320
题9-15后缀数组质320
题9-16后缀数组搜索321
题9-17后缀数组快速搜索322
算法实现题9-1安全基因序列问题326
算法实现题9-2长重复子串问题328
算法实现题9-3长回文子串问题329
算法实现题9-4相似基因序列问题331
算法实现题9-5计算机病毒问题332
算法实现题9-6带有子串包含约束的长公共子序列问题335
算法实现题9-7多子串排斥约束的长公共子序列问题336
0章算法优化策略338
题10-1算法obst的正确338
题10-2矩阵连乘问题的o(n2)时间算法338
题10-3货物储运问题的费用343
题10-4garsia算法343
算法实现题10-1货物储运问题346
算法实现题10-2石子合并问题346
算法实现题10-3优选运输费用货物储运问题347
算法实现题10-4五边形问题349
算法实现题10-5区间图短路问题352
算法实现题10-6圆弧区间短路问题353
算法实现题10-7双机调度问题353
算法实现题10-8离线小值问题361
算法实现题10-9近公共祖先问题363
算法实现题10-10达尔文芯片问题365
算法实现题10-11多柱hanoi塔问题367
算法实现题10-12线时间huffman算法370
算法实现题10-13单机调度问题371
算法实现题10-14优选费用单机调度问题374
算法实现题10-15飞机加油问题377
1章在线算法设计378
题11-1在线算法lfu的竞争378
题11-2多读写头磁盘问题的在线算法378
题11-3带权页调度问题378
算法实现题11-1很优页调度问题378
算法实现题11-2在线lru页调度382
算法实现题11-3k服务问题383
参文献388