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

第 1 章 算法引论 11 1 算法与程序 1 1 2 表达算法的抽象机制 1 1 3 描述算法 3 1 4 算法复杂性分析 13 小结 16 习题 17 第 2 章 递归与分治策略 19 2 1 递归的概念 19 2 2 分治法的基本思想 26 2 3 二分搜索技术 27 2 4 大整数的乘法 28 2 5 Strassen 矩阵乘法 30 2 6 棋盘覆盖 32 2 7 合并排序 34 2 8 快速排序 37 2 9 线性时间选择 39 2 10 最接近点对问题 43 2 11 循环赛日程表 53 小结 54 习题 54 第 3 章 动态规划 61 3 1 矩阵连乘问题 62 目 录算法设计与分析 第 2 版 3 2 动态规划算法的基本要素 67 3 3 最长公共子序列 71 3 4 凸多边形最优三角剖分 75 3 5 多边形游戏 79 3 6 图像压缩 82 3 7 电路布线 85 3 8 流水作业调度 88 3 9 0 1 背包问题 92 3 10 最优二叉搜索树 98 小结 101 习题 102 第 4 章 贪心算法 107 4 1 活动安排问题 107 4 2 贪心算法的基本要素 110 4 2 1 贪心选择性质 111 4 2 2 最优子结构性质 111 4 2 3 贪心算法与动态规划算法的差异 111 4 3 最优装载 114 4 4 哈夫曼编码 116 4 4 1 前缀码 117 4 4 2 构造哈夫曼编码 117 4 4 3 哈夫曼算法的正确性 119 4 5 单源最短路径 121 4 5 1 算法基本思想 121 4 5 2 算法的正确性和计算复杂性 123 4 6 最小生成树 125 4 6 1 最小生成树性质 125 4 6 2 Prim 算法 126 4 6 3 Kruskal 算法 128 4 7 多机调度问题 130 4 8 贪心算法的理论基础 133 4 8 1 拟阵 133 4 8 2 带权拟阵的贪心算法 134 4 8 3 任务时间表问题 137 小结 141 习题 141 第 5 章 回溯法 146 5 1 回溯法的算法框架 146 5 1 1 问题的解空间 146 5 1 2 回溯法的基本思想 147 5 1 3 递归回溯 149 5 1 4 迭代回溯 150 5 1 5 子集树与排列树 151 5 2 装载问题 152 5 3 批处理作业调度 160 5 4 符号三角形问题 162 5 5 n 后问题 165 5 6 0 1 背包问题 168 5 7 最大团问题 171 5 8 图的 m 着色问题 174 5 9 旅行售货员问题 177 5 10 圆排列问题 179 5 11 电路板排列问题 181 5 12 连续邮资问题 185 5 13 回溯法的效率分析 187 小结 190 习题 191 第 6 章 分支限界法 195 6 1 分支限界法的基本思想 195 6 2 单源最短路径问题 198 6 3 装载问题 202 6 4 布线问题 211 6 5 0 1 背包问题 216 6 6 最大团问题 222 6 7 旅行售货员问题 225 6 8 电路板排列问题 229 6 9 批处理作业调度 232 小结 237 习题 238 第 7 章 概率算法 240 7 1 随机数 241 7 2 数值概率算法 244 7 2 1 用随机投点法计算 值 244 7 2 2 计算定积分 245 7 2 3 解非线性方程组 247 7 3 舍伍德算法 250 7 3 1 线性时间选择算法 250 7 3 2 跳跃表 252 7 4 拉斯维加斯算法 259 7 4 1 n 后问题 260 7 4 2 整数因子分解 264 7 5 蒙特卡罗算法 266 7 5 1 蒙特卡罗算法的基本思想 266 7 5 2 主元素问题 268 7 5 3 素数测试 270 小结 273 习题 273 第 8 章 NP 完全性理论 278 8 1 计算模型 279 8 1 1 随机存取机 RAM279 8 1 2 随机存取存储程序机 RASP287 8 1 3 RAM 模型的变形与简化 291 8 1 4 图灵机 295 8 1 5 图灵机模型与 RAM 模型的关系 297 8 1 6 问题变换与计算复杂性归约 299 8 2 P 类与 NP 类问题 301 8 2 1 非确定性图灵机 301 8 2 2 P 类与 NP 类语言 302 8 2 3 多项式时间验证 304 8 3 NP 完全问题 305 8 3 1 多项式时间变换 305 8 3 2 Cook 定理 307 8 4 一些典型的 NP 完全问题 310 8 4 1 合取范式的可满足性问题 311 8 4 2 3 元合取范式的可满足性问题 312 8 4 3 团问题 313 8 4 4 顶点覆盖问题 314 8 4 5 子集和问题 315 8 4 6 哈密顿回路问题 317 8 4 7 旅行售货员问题 322 小结 323 习题 323 第 9 章 近似算法 326 9 1 近似算法的性能 327 9 2 顶点覆盖问题的近似算法 328 9 3 旅行售货员问题近似算法 329 9 3 1 具有三角不等式性质的旅行售货员问题 330 9 3 2 一般的旅行售货员问题 331 9 4 集合覆盖问题的近似算法 333 9 5 子集和问题的近似算法 336 9 5 1 子集和问题的指数时间算法 336 9 5 2 子集和问题的完全多项式时间近似格式 337 小结 340 习题 340 第 10 章 算法优化策略 345 10 1 算法设计策略的比较与选择 345 10 1 1 最大子段和问题的简单算法 345 10 1 2 最大子段和问题的分治算法 346 10 1 3 最大子段和问题的动态规划算法 348 10 1 4 最大子段和问题与动态规划算法的推广 349 10 2 动态规划加速原理 352 10 2 1 货物储运问题 352 10 2 2 算法及其优化 353 10 3 问题的算法特征 357 10 3 1 贪心策略 357 10 3 2 对贪心策略的改进 357 10 3 3 算法三部曲 359 10 3 4 算法实现 360 10 3 5 算法复杂性 366 10 4 优化数据结构 366 10 4 1 带权区间最短路问题 366 10 4 2 算法设计思想 367 10 4 3 算法实现方案 369 10 4 4 并查集 373 10 4 5 可并优先队列 376 10 5 优化搜索策略 380 小结 388 习题 388 第 11 章 在线算法设计 391 11 1 在线算法设计的基本概念 391 11 2 页调度问题 393 11 3 势函数分析 395 11 4 k 服务问题 397 11 4 1 竞争比的下界 397 11 4 2 平衡算法 399 11 4 3 对称移动算法 399 11 5 Steiner 树问题 403 11 6 在线任务调度 405 11 7 负载平衡 406 小结 407 习题 407 词汇索引 409 参考文献 415 习题 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 2 7 个二分搜索算法 15 习题 2 3 改写二分搜索算法 18 习题 2 4 大整数乘法的 O nm log 3 2 算法 19 习题 2 5 5 次 n 3 位整数的乘法 19 习题 2 6 矩阵乘法 21 习题 2 7 多项式乘积 21 习题 2 8 不动点问题的 O log n 时间算法 22 习题 2 9 主元素问题的线性时间算法 22 习题 2 10 无序集主元素问题的线性时间算法 22 习题 2 11 O 1 空间子数组换位算法 23 习题 2 12 O 1 空间合并算法 25 习题 2 13 n 段合并排序算法 32 习题 2 14 自然合并排序算法 32 习题 2 15 最大值和最小值问题的最优算法 35 习题 2 16 最大值和次大值问题的最优算法 35 习题 2 17 整数集合排序 35 习题 2 18 第 k 小元素问题的计算时间下界 36 习题 2 19 非增序快速排序算法 37 习题 2 20 随机化算法 37 习题 2 21 随机化快速排序算法 38 习题 2 22 随机排列算法 38 习题 2 23 算法 qSort 中的尾递归 38 习题 2 24 用栈模拟递归 38 习题 2 25 算法 select 中的元素划分 39 习题 2 26 O n log n 时间快速排序算法 40 习题 2 27 最接近中位数的 k 个数 40 习题 2 28 X 和 Y 的中位数 40 习题 2 29 网络开关设计 41 习题 2 32 带权中位数问题 42 习题 2 34 构造 Gray 码的分治算法 43 习题 2 35 网球循环赛日程表 44 目 录算法设计与分析习题解答 第 2 版 算法实现题 2 1 输油管道问题 习题 2 30 49 算法实现题 2 2 众数问题 习题 2 31 50 算法实现题 2 3 邮局选址问题 习题 2 32 51 算法实现题 2 4 马的 Hamilton 周游路线问题 习题 2 33 51 算法实现题 2 5 半数集问题 60 算法实现题 2 6 半数单集问题 62 算法实现题 2 7 士兵站队问题 63 算法实现题 2 8 有重复元素的排列问题 63 算法实现题 2 9 排列的字典序问题 65 算法实现题 2 10 集合划分问题 一 67 算法实现题 2 11 集合划分问题 二 68 算法实现题 2 12 双色 Hanoi 塔问题 69 算法实现题 2 13 标准二维表问题 71 算法实现题 2 14 整数因子分解问题 72 算法实现题 2 15 有向直线 2 中值问题 72 第 3 章 动态规划 76 习题 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 算法实现题 3 5 编辑距离问题 习题 3 8 87 算法实现题 3 6 石子合并问题 习题 3 9 89 算法实现题 3 7 数字三角形问题 习题 3 10 91 算法实现题 3 8 乘法表问题 习题 3 13 92 算法实现题 3 9 租用游艇问题 习题 3 15 93 算法实现题 3 10 汽车加油行驶问题 习题 3 16 95 算法实现题 3 11 圈乘运算问题 习题 3 18 96 算法实现题 3 12 最少费用购物 习题 3 20 102 算法实现题 3 13 最大长方体问题 习题 3 21 104 算法实现题 3 14 正则表达式匹配问题 习题 3 22 105 算法实现题 3 15 双调旅行售货员问题 习题 3 23 110 算法实现题 3 16 最大 k 乘积问题 习题 5 24 111 算法实现题 3 17 最小 m 段和问题 113 算法实现题 3 18 红黑树的红色内结点问题 115 第 4 章 贪心算法 123 习题 4 2 活动安排问题的贪心选择 123 习题 4 3 背包问题的贪心选择性质 123 习题 4 4 特殊的 0 1 背包问题 124 习题 4 10 程序最优存储问题 124 习题 4 13 最优装载问题的贪心算法 125 习题 4 18 Fibonacci 序列的 Huffman 编码 125 习题 4 19 最优前缀码的编码序列 125 习题 4 21 任务集独立性问题 126 习题 4 22 矩阵拟阵 126 习题 4 23 最小权最大独立子集拟阵 126 习题 4 27 整数边权 Prim 算法 126 习题 4 28 最大权最小生成树 127 习题 4 29 最短路径的负边权 127 习题 4 30 整数边权 Dijkstra 算法 127 算法实现题 4 1 会场安排问题 习题 4 1 128 算法实现题 4 2 最优合并问题 习题 4 5 129 算法实现题 4 3 磁带最优存储问题 习题 4 6 130 算法实现题 4 4 磁盘文件最优存储问题 习题 4 7 131 算法实现题 4 5 程序存储问题 习题 4 8 132 算法实现题 4 6 最优服务次序问题 习题 4 11 133 算法实现题 4 7 多处最优服务次序问题 习题 4 12 134 算法实现题 4 8 d 森林问题 习题 4 14 135 算法实现题 4 9 汽车加油问题 习题 4 16 137 算法实现题 4 10 区间覆盖问题 习题 4 17 138 算法实现题 4 11 硬币找钱问题 习题 4 24 138 算法实现题 4 12 删数问题 习题 4 25 139 算法实现题 4 13 数列极差问题 习题 4 26 140 算法实现题 4 14 嵌套箱问题 习题 4 31 140 算法实现题 4 15 套汇问题 习题 4 32 142 算法实现题 4 16 信号增强装置问题 习题 5 17 143 算法实现题 4 17 磁带最大利用率问题 习题 4 9 144 算法实现题 4 18 非单位时间任务安排问题 习题 4 15 145 算法实现题 4 19 多元 Huffman 编码问题 习题 4 20 147 算法实现题 4 20 多元 Huffman 编码变形 149 算法实现题 4 21 区间相交问题 151 算法实现题 4 22 任务时间表问题 151 第 5 章 回溯法 153 习题 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 算法实现题 5 2 最小长度电路板排列问题 习题 5 9 160 算法实现题 5 3 最小重量机器设计问题 习题 5 10 163 算法实现题 5 4 运动员最佳匹配问题 习题 5 11 164 算法实现题 5 5 无分隔符字典问题 习题 5 12 165 算法实现题 5 6 无和集问题 习题 5 13 167 算法实现题 5 7 n 色方柱问题 习题 5 14 168 算法实现题 5 8 整数变换问题 习题 5 15 173 算法实现题 5 9 拉丁矩阵问题 习题 5 16 175 算法实现题 5 10 排列宝石问题 习题 5 16 176 算法实现题 5 11 重复拉丁矩阵问题 习题 5 16 179 算法实现题 5 12 罗密欧与朱丽叶的迷宫问题 181 算法实现题 5 13 工作分配问题 习题 5 18 183 算法实现题 5 14 独立钻石跳棋问题 习题 5 19 184 算法实现题 5 15 智力拼图问题 习题 5 20 191 算法实现题 5 16 布线问题 习题 5 21 198 算法实现题 5 17 最佳调度问题 习题 5 22 200 算法实现题 5 18 无优先级运算问题 习题 5 23 201 算法实现题 5 19 世界名画陈列馆问题 习题 5 25 203 算法实现题 5 20 世界名画陈列馆问题 不重复监视 习题 5 26 207 算法实现题 5 21 部落卫队问题 习题 5 6 209 算法实现题 5 22 虫蚀算式问题 211 算法实现题 5 23 完备环序列问题 214 算法实现题 5 24 离散 01 串问题 217 算法实现题 5 25 喷漆机器人问题 218 算法实现题 5 26 n 2 1 谜问题 221 第 6 章 分支限界法 229 习题 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 算法实现题 6 2 最小长度电路板排列问题二 习题 6 9 244 算法实现题 6 3 最小权顶点覆盖问题 习题 6 10 247 算法实现题 6 4 无向图的最大割问题 习题 6 11 250 算法实现题 6 5 最小重量机器设计问题 习题 6 12 253 算法实现题 6 6 运动员最佳匹配问题 习题 6 13 256 算法实现题 6 7 n 后问题 习题 6 15 259 算法实现题 6 8 圆排列问题 习题 6 16 260 算法实现题 6 9 布线问题 习题 6 17 263 算法实现题 6 10 最佳调度问题 习题 6 18 265 算法实现题 6 11 无优先级运算问题 习题 6 19 268 算法实现题 6 12 世界名画陈列馆问题 习题 6 21 271 算法实现题 6 13 骑士征途问题 274 算法实现题 6 14 推箱子问题 275 算法实现题 6 15 图形变换问题 281 算法实现题 6 16 行列变换问题 284 算法实现题 6 17 重排 n 2 宫问题 285 算法实现题 6 18 最长距离问题 290 第 7 章 概率算法 296 习题 7 1 模拟正态分布随机变量 296 习题 7 2 随机抽样算法 297 习题 7 3 随机产生 m 个整数 297 习题 7 4 集合大小的概率算法 298 习题 7 5 生日问题 299 习题 7 6 易验证问题的拉斯维加斯算法 300 习题 7 7 用数组模拟有序链表 300 习题 7 8 O n 3 2 舍伍德型排序算法 300 习题 7 9 n 后问题解的存在性 301 习题 7 11 整数因子分解算法 302 习题 7 12 非蒙特卡罗算法的例子 302 习题 7 13 重复 3 次的蒙特卡罗算法 303 习题 7 14 集合随机元素算法 304 习题 7 15 由蒙特卡罗算法构造拉斯维加斯算法 305 习题 7 16 产生素数算法 306 习题 7 18 矩阵方程问题 306 算法实现题 7 1 模平方根问题 习题 7 10 307 算法实现题 7 2 集合相等问题 习题 7 17 309 算法实现题 7 3 逆矩阵问题 习题 7 19 309 算法实现题 7 4 多项式乘积问题 习题 7 20 310 算法实现题 7 5 皇后控制问题 311 算法实现题 7 6 3 SAT 问题 314 算法实现题 7 7 战车问题 315 算法实现题 7 8 圆排列问题 317 算法实现题 7 9 骑士控制问题 319 算法实现题 7 10 骑士对攻问题 320 第 8 章 NP 完全性理论 322 习题 8 1 RAM 和 RASP 程序 322 习题 8 2 RAM 和 RASP 程序的复杂性 322 习题 8 3 计算 n n 的 RAM 程序 322 习题 8 4 没有 MULT 和 DIV 指令的 RAM 程序 324 习题 8 5 MULT 和 DIV 指令的计算能力 324 习题 8 6 RAM 和 RASP 的空间复杂性 325 习题 8 7 行列式的直线式程序 325 习题 8 8 求和的 3 带图灵机 325 习题 8 9 模拟 RAM 指令 325 习题 8 10 计算 2 2 n 的 RAM 程序 325 习题 8 11 计算 g m n 的程序 326 习题 8 12 图灵机模拟 RAM 的时间上界 326 习题 8 13 图的同构问题 326 习题 8 14 哈密顿回路 327 习题 8 15 P 类语言的封闭性 327 习题 8 16 NP 类语言的封闭性 328 习题 8 17 语言的 2 O n k 时间判定算法 328 习题 8 18 P CO NP329 习题 8 19 NP CO NP329 习题 8 20 重言布尔表达式 329 习题 8 21 关系 p 的传递性 329 习题 8 22 L p 330 习题 8 23 语言的完全性 330 习题 8 24 的 CO NP 完全性 330 习题 8 25 判定重言式的 CO NP 完全性 331 习题 8 26 析取范式的可满足性 331 习题 8 27 2 SAT 问题的线性时间算法 331 习题 8 28 整数规划问题 332 习题 8 29 划分问题 333 习题 8 30 最长简单回路问题 334 第 9 章 近似算法 336 习题 9 1 平面图着色问题的绝对近似算法 336 习题 9 2 最优程序存储问题 336 习题 9 4 树的最优顶点覆盖 337 习题 9 5 顶点覆盖算法的性能比 339 习题 9 6 团的常数性能比近似算法 339 习题 9 9 售货员问题的常数性能比近似算法 340 习题 9 10 瓶颈旅行售货员问题 340 习题 9 11 最优旅行售货员回路不自相交 342 习题 9 14 集合覆盖问题的实例 342 习题 9 16 多机调度问题的近似算法 343 习题 9 17 LPT 算法的最坏情况实例 345 习题 9 18 多机调度问题的多项式时间近似算法 345 算法实现题 9 1 旅行售货员问题的近似算法 习题 9 9 346 算法实现题 9 2 可满足问题的近似算法 习题 9 20 348 算法实现题 9 3 最大可满足问题的近似算法 习题 9 21 349 算法实现题 9 4 子集和问题的近似算法