算法设计与分析习题解答(第2版)_第1页
算法设计与分析习题解答(第2版)_第2页
算法设计与分析习题解答(第2版)_第3页
算法设计与分析习题解答(第2版)_第4页
算法设计与分析习题解答(第2版)_第5页
已阅读5页,还剩6页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第 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 子集和问题的近似算法

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论