算法设计与实验题解PDF电子书下载

第1章　算法概述 1

习题1-1　函数的渐近表达式 1

习题1-2 O（1）和O（2）的区别 1

习题1-4 按渐近阶排列表达式 1

习题1-5 算法效率 1

习题1-6 硬件效率 2

习题1-7 函数渐近阶 2

习题1-8 n！的阶 2

算法实现题1-1　统计数字问题 3

习题1-10 平均情况下的计算时间复杂性 3

习题1-9 3n+1问题 3

算法实现题1-2 字典序问题 4

算法实现题1-3 最多约数问题 5

算法实现题1-4 金币阵列问题 7

算法实现题1-5 最大间隙问题 9

第2章　递归与分治策略 12

习题2-1　Hanoi塔问题的非递归算法 12

习题2-2 7个二分搜索算法 13

习题2-3 改写二分搜索算法 16

习题2-5 5次n/3位整数的乘法 17

习题2-4 大整数乘法的O（nmlog(3/2)）算法 17

习题2-6 矩阵乘法 19

习题2-7 多项式乘积 19

习题2-8 不动点问题的O（logn）时间算法 20

习题2-9 主元素问题的线性时间算法 20

习题2-10　无序集主元素问题的线性时间算法 20

习题2-11 O（1）空间子数组换位算法 20

习题2-12 O（1）空间合并算法 22

习题2-14 自然合并排序算法 29

习题2-13 ？段合并排序算法 29

习题2-15 最大值和最小值问题的最优算法 31

习题2-16 最大值和次大值问题的最优算法 32

习题2-17 整数集合排序 32

习题2-18 第k小元素问题的计算时间下界 32

习题2-19 非增序快速排序算法 33

习题2-27 最接近中位数的k个数 34

习题2-26 O（nlogn）时间快速排序算法 34

习题2-25 算法Select中的元素划分 34

习题2-24 用栈模拟递归 34

习题2-23 算法QuickSort中的尾递归 34

习题2-22 随机排列算法 34

习题2-21 随机化快速排序算法 34

习题2-20 随机化算法 34

习题2-28 X和Y的中位数 35

习题2-29 网络开关设计 35

习题2-32 带权中位数问题 35

习题2-34 构造Gray码的分治算法 36

习题2-35 网球循环赛日程表 36

习题2-36 二叉树T的前序、中序和后序序列 40

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

算法实现题2-2 众数问题（习题2-31） 42

算法实现题2-3 邮局选址问题（习题2-32） 43

算法实现题2-4 马的Hamilton周游路线问题（习题2-33） 43

算法实现题2-5 半数集问题 51

算法实现题2-6 半数单集问题 52

算法实现题2-7 士兵站队问题 53

算法实现题2-8 有重复元素的排列问题 54

算法实现题2-9 排列的字典序问题 55

算法实现题2-10 集合划分问题 57

算法实现题2-11 集合划分问题 58

算法实现题2-12 双色Hanoi塔问题 60

算法实现题2-13 标准二维表问题 61

算法实现题2-14 整数因子分解问题 61

第3章　动态规划 63

习题3-1 最长单调递增子序列 63

习题3-2 最长单调递增子序列的O（nlogn）算法 63

习题3-12 二维0-1背包问题 65

习题3-11 整数线性规划问题 65

习题3-7 漂亮打印 65

习题3-14 Ackermann函数 66

习题3-17 最短行驶路线 68

习题3-19 最优旅行路线 69

算法实现题3-1 独立任务最优调度问题（习题3-3） 69

算法实现题3-2 最少硬币问题（习题3-4） 71

算法实现题3-3 序关系计数问题（习题3-5） 71

算法实现题3-4　多重幂计数问题（习题3-6） 72

算法实现题3-5 编辑距离问题（习题3-8） 72

算法实现题3-6 石子合并问题（习题3-9） 73

算法实现题3-7 数字三角形问题（习题3-10） 75

算法实现题3-8 乘法表问题（习题3-13） 76

算法实现题3-9 租用游艇问题（习题3-15） 77

算法实现题3-10 汽车加油行驶问题（习题3-16） 78

算法实现题3-11 最小m段和问题 79

算法实现题3-12 圈乘运算问题（习题3-18） 80

算法实现题3-13 最大长方体问题（习题3-21） 85

算法实现题3-14 正则表达式匹配问题（习题3-22） 86

算法实现题3-15 双调旅行售货员问题（习题3-23） 90

算法实现题3-16 最大k乘积问题（习题5-28） 92

算法实现题3-17 最少费用购物问题（习题3-20） 94

算法实现题3-18 收集样本问题 96

算法实现题3-19 最优时间表问题 98

算法实现题3-20 字符串比较问题 98

算法实现题3-21 有向树k中值问题 100

算法实现题3-22 有向树独立k中值问题 104

算法实现题3-23 有向直线m中值问题 108

算法实现题3-24 有向直线2中值问题 111

算法实现题3-25 树的最大连通分支问题 114

算法实现题3-26 直线k中值问题 116

算法实现题3-27 直线k覆盖问题 121

算法实现题3-28 m处理器问题 125

算法实现题3-29 红黑树的红色内结点问题 127

习题4-10 程序最优存储问题 136

习题4-4 特殊的0-1背包问题 136

习题4-3 背包问题的贪心选择性质 136

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

第4章　贪心算法 136

习题4-13 最优装载问题的贪心算法 137

习题4-18 Fibonacci序列的哈夫曼编码 137

习题4-19 最优前缀码的编码序列 137

习题4-21 任务集独立性问题 137

习题4-22 矩阵拟阵 137

习题4-30　整数边权Dijkstra算法 138

习题4-29 最短路径的负边权 138

算法实现题4-1　会场安排问题（习题4-1） 138

习题4-28 最大权最小生成树 138

习题4-27 整数边权Prim算法 138

习题4-23 最小权最大独立子集拟阵 138

算法实现题4-2 最优合并问题（习题4-5） 139

算法实现题4-3 磁带最优存储问题（习题4-6） 140

算法实现题4-4 磁盘文件最优存储问题（习题4-7） 141

算法实现题4-5 程序存储问题（习题4-8） 142

算法实现题4-6 最优服务次序问题（习题4-11） 143

算法实现题4-7 多处最优服务次序问题（习题4-12） 143

算法实现题4-8　d森林问题（习题4-14） 144

算法实现题4-9 汽车加油问题（习题4-16） 146

算法实现题4-10 区间覆盖问题（习题4-17） 147

算法实现题4-11 硬币找钱问题（习题4-24） 148

算法实现题4-12 删数问题（习题4-25） 148

算法实现题4-13 数列极差问题（习题4-26） 149

算法实现题4-14 嵌套箱问题（习题4-31） 149

算法实现题4-15 套汇问题（习题4-32） 150

算法实现题4-16 信号增强装置问题（习题5-20） 152

算法实现题4-17 磁带最大利用率问题（习题4-9） 153

算法实现题4-18 非单位时间任务安排问题（习题4-15） 154

算法实现题4-19 多元Huffman编码问题（习题4-20） 156

算法实现题4-20 多元Huffman编码变形 157

算法实现题4-21 区间相交问题 159

算法实现题4-22 任务时间表问题 159

算法实现题4-23 最优分解问题 160

算法实现题4-24 可重复最优分解问题 161

算法实现题4-25 可重复最优组合分解问题 161

算法实现题4-26 旅行规划问题 163

算法实现题4-27 登山机器人问题 163

习题5-1 装载问题改进回溯法1 165

第5章　回溯法 165

习题5-2 装载问题改进回溯法2 166

习题5-4 0-1背包问题的最优解 166

习题5-5 最大团问题的迭代回溯法 168

习题5-7 旅行售货员问题的费用上界 169

习题5-8 旅行售货员问题的上界函数 171

算法实现题5-1 子集和问题（习题5-3） 171

算法实现题5-2 最小长度电路板排列问题（习题5-9） 173

算法实现题5-3 最小重量机器设计问题（习题5-10） 175

算法实现题5-4 运动员最佳配对问题（习题5-14） 176

算法实现题5-5 无分隔符字典问题（习题5-15） 178

算法实现题5-6　无和集问题（习题5-16） 180

算法实现题5-7 n色方柱问题（习题5-17） 181

算法实现题5-8 整数变换问题（习题5-18） 186

算法实现题5-9 拉丁矩阵问题 187

算法实现题5-10　排列宝石问题（习题5-19） 188

算法实现题5-11 重复拉丁矩阵问题（习题5-19） 190

算法实现题5-12 罗密欧与朱丽叶的迷宫问题（习题5-21） 192

算法实现题5-13 工作分配问题（习题5-22） 195

算法实现题5-14 独立钻石跳棋问题（习题5-23） 196

算法实现题5-15 智力拼图问题（习题5-24） 202

算法实现题5-16 布线问题（习题5-25） 208

算法实现题5-17 最佳调度问题（习题5-26） 209

算法实现题5-18 无优先级运算问题（习题5-27） 210

算法实现题5-19 世界名画陈列馆问题（习题5-29） 212

算法实现题5-20 世界名画陈列馆问题（不重复监视）（习题5-30） 216

算法实现题5-21 2×2×2魔方问题 218

算法实现题5-22 魔方（Rubik's Cube）问题（习题5-31） 234

算法实现题5-23 算24点问题 250

算法实现题5-24 算m点问题 252

算法实现题5-25 双轨车皮编序问题 255

算法实现题5-26 多轨车皮编序问题 259

算法实现题5-27 部落卫队问题（习题5-6） 262

算法实现题5-28 虫蚀算式问题 263

算法实现题5-29 完备环序列问题 267

算法实现题5-30 离散0-1串问题 269

算法实现题5-31 喷漆机器人问题 270

算法实现题5-32 子集树问题（习题5-11） 273

算法实现题5-33 0-1背包问题（习题5-11） 274

算法实现题5-34 排列树问题（习题5-12） 276

算法实现题5-35 一般解空间搜索问题（习题5-13） 278

算法实现题5-36 最短加法链问题 280

算法实现题5-37　n2-1谜问题 286

第6章　分支限界法 292

习题6-1　0-1背包问题的栈式分支限界法 292

习题6-2 释放结点空间的队列式分支限界法 294

习题6-3 及时删除不用的结点 295

习题6-4 用最大堆存储活结点的优先队列式分支限界法 297

习题6-5 释放结点空间的优先队列式分支限界法 300

习题6-8　修改解旅行售货员问题的分支限界法 303

习题6-6 团顶点数的上界 303

习题6-7 团顶点数改进的上界 303

习题6-9 解旅行售货员问题的分支限界法中保存已产生的排列树 306

习题6-10 电路板排列问题的队列式分支限界法 308

算法实现题6-1 最小长度电路板排列问题（习题6-11） 310

算法实现题6-2 最小长度电路板排列问题（习题6-12） 313

算法实现题6-3 最小权顶点覆盖问题（习题6-13） 316

算法实现题6-4 无向图的最大割问题（习题6-14） 319

算法实现题6-5 最小重量机器设计问题（习题6-15） 322

算法实现题6-6 运动员最佳配对问题（习题6-16） 325

算法实现题6-7 n皇后问题（习题6-18） 327

算法实现题6-8 圆排列问题（习题6-19） 330

算法实现题6-9 布线问题（习题6-20） 333

算法实现题6-10　最佳调度问题（习题6-21） 335

算法实现题6-11 无优先级运算问题（习题6-22） 338

算法实现题6-12 世界名画陈列馆问题（习题6-24） 341

算法实现题6-13 子集空间树问题（习题6-25） 344

算法实现题6-14 排列空间树问题（习题6-26） 347

算法实现题6-15 一般解空间的队列式分支限界法（习题6-27） 352

算法实现题6-16 子集空间树问题（习题6-28） 357

算法实现题6-17 排列空间树问题（习题6-29） 362

算法实现题6-18 一般解空间的优先队列式分支限界法（习题6-30） 368

算法实现题6-19 骑士征途问题 373

算法实现题6-20 推箱子问题 374

算法实现题6-21 图形变换问题 379

算法实现题6-22 行列变换问题 381

算法实现题6-23 重排n2宫问题 386

算法实现题6-24 最长距离问题 394

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

第7章　概率算法 399

习题7-2 随机抽样算法 400

习题7-3 随机产生m个整数 400

习题7-4 集合大小的概率算法 401

习题7-5 生日问题 402

习题7-6 易验证问题的拉斯维加斯算法 402

习题7-7 用数组模拟有序链表 403

习题7-8 O（n3/2）舍伍德型排序算法 403

习题7-9 n后问题解的存在性 403

习题7-12 非蒙特卡罗算法的例子 405

习题7-11 整数因子分解算法 405

习题7-13 重复3次的蒙特卡罗算法 406

习题7-14 集合随机元素算法 407

习题7-15 由蒙特卡罗算法构造拉斯维加斯算法 408

习题7-16 产生素数算法 408

习题7-19 矩阵方程问题 409

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

算法实现题7-3 集合相等问题（习题7-18） 412

算法实现题7-2 素数测试问题（习题7-17） 412

算法实现题7-4 逆矩阵问题（习题7-20） 413

算法实现题7-5 多项式乘积问题（习题7-21） 414

算法实现题7-6 皇后控制问题 414

算法实现题7-7 3-SAT问题 418

算法实现题7-8 战车问题 419

算法实现题7-9 圆排列问题 421

算法实现题7-10 骑士控制问题 422

算法实现题7-11 骑士对攻问题 423

习题8-1 线性规划可行区域无界的例子 425

习题8-2 单源最短路与线性规划 425

第8章　线性规划与网络流 425

习题8-3 网络最大流与线性规划 426

习题8-4 最小费用流与线性规划 426

习题8-5 运输计划问题 427

习题8-6 单纯形算法 427

习题8-7 边连通度问题 428

习题8-8 有向无环网络的最大流 428

习题8-12 最大流更新算法 429

习题8-16 混合图欧拉回路问题 429

习题8-9 无向网络的最大流 429

习题8-22 单源最短路与最小费用流 430

习题8-23 中国邮路问题 430

算法实现题8-1 飞行员配对方案问题（习题8-10） 430

算法实现题8-2 太空飞行计划问题（习题8-11） 432

算法实现题8-3 最小路径覆盖问题（习题8-13） 433

算法实现题8-4 魔术球问题（习题8-14） 434

算法实现题8-5 圆桌问题（习题8-15） 435

算法实现题8-6 最长递增子序列问题（习题8-17） 436

算法实现题8-7 试题库问题（习题8-18） 438

算法实现题8-8 机器人路径规划问题（习题8-19） 440

算法实现题8-9 方格取数问题（习题8-20） 443

算法实现题8-10 餐巾计划问题（习题8-21） 447

算法实现题8-11 航空路线问题（习题8-24） 448

算法实现题8-12 软件补丁问题（习题8-25） 449

算法实现题8-13 星际转移问题（习题8-26） 451

算法实现题8-14 孤岛营救问题（习题8-27） 452

算法实现题8-15 汽车加油行驶问题（习题8-28） 453

算法实现题8-16 数字梯形问题 457

算法实现题8-17 运输问题 462

算法实现题8-18 分配工作问题 464

算法实现题8-19 负载平衡问题 466

算法实现题8-20 深海机器人问题 467

算法实现题8-21 最长k可重区间集问题 471

算法实现题8-22 最长k可重线段集问题 474

算法实现题8-23 火星探险问题 478

算法实现题8-24 骑士共存问题 479

习题9-3 计算nn的RAM程序 485

习题9-2 RAM和RASP程序的复杂性 485

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

习题9-1 RAM和RASP程序 485

第9章　NP完全性理论与近似算法 485

习题9-5 最优程序存储问题 486

习题9-6 树的最优顶点覆盖 487

习题9-7 顶点覆盖算法的性能比 488

习题9-8 团的常数性能比近似算法 488

习题9-10 旅行售货员问题的常数性能比近似算法 489

习题9-11 瓶颈旅行售货员问题 489

习题9-12 最优旅行售货员回路不自相交 490

习题9-14 集合覆盖问题的实例 490

习题9-16　多机调度问题的近似算法 491

习题9-17　LPT算法的最坏情况实例 493

习题9-18 多机调度问题的多项式时间近似算法 493

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

算法实现题9-2 可满足问题的近似算法（习题9-19） 496

算法实现题9-3 最大可满足问题的近似算法（习题9-20） 497

算法实现题9-4 子集和问题的近似算法（习题9-15） 499

算法实现题9-5 子集和问题的完全多项式时间近似算法 500

算法实现题9-6 2-SAT问题的线性时间算法 501

算法实现题9-7 实现算法greedySetCover（习题9-13） 504

参考文献 508