算法设计与分析 以ACM大学生程序设计竞赛在线题库为例PDF电子书下载

第1章 算法概述 1

1.1 引言 1

1.1.1 算法的描述 1

1.1.2 算法的设计 3

1.2 算法的复杂性 6

1.2.1 时间复杂性 6

1.2.2 空间复杂性 9

1.3 大学生程序设计竞赛概述 10

1.4 程序设计在线测试题库 11

第2章 数据结构和标准模板库STL 13

2.1 栈 13

2.2 向量 14

2.3 映射 17

2.4 列表 19

2.5 集合 21

2.6 队列 22

2.7 优先队列 23

2.8 ZOJ1004-Anagrams by Stack 25

2.9 ZOJ1094-Matrix Chain Multiplication 28

2.10 ZOJ1011-NTA 31

2.11 ZOJ1062-Trees Made to Order 36

2.12 ZOJ1097-Code the Tree 40

2.13 ZOJ1156-Unscrambling Images 43

2.14 ZOJ1167-Trees on the Level 47

2.15 ZOJ1016-Parencodings 50

2.16 ZOJ1944-Tree Recovery 53

2.17 ZOJ2104-Let the Balloon Rise 55

上机练习题 56

第3章 递归与分治策略 59

3.1 递归算法 59

3.1.1 Fibonacci数列 60

3.1.2 集合的全排列问题 61

3.1.3 整数划分问题 62

3.2 分治策略 63

3.2.1 分治法的基本步骤 63

3.2.2 分治法的适用条件 64

3.2.3 二分搜索技术 64

3.2.4 循环赛日程表 65

3.2.5 棋盘覆盖问题 67

3.2.6 选择问题 70

3.7.7 输油管道问题 72

3.2.8 半数集问题 73

3.2.9 整数因子分解 75

3.2.10 取余运算 76

3.3 ZOJ1633-Big String 78

上机练习题 79

第4章 动态规划 81

4.1 矩阵连乘积问题 82

4.1.1 分析最优解的结构 84

4.1.2 建立递归关系 85

4.1.3 计算最优值 85

4.1.4 构造最优解 87

4.2 动态规划算法的基本要素 88

4.2.1 最优子结构 88

4.2.2 重叠子问题 89

4.2.3 备忘录方法 89

4.3 最长公共子序列 91

4.3.1 最长公共子序列的结构 91

4.3.2 子问题的递归结构 92

4.3.3 计算最优值 92

4.3.4 构造最长公共子序列 94

4.4 最大子段和 94

4.5 0-1背包问题 96

4.5.1 递归关系分析 97

4.5.2 算法实现 97

4.6 最长单调递增子序列 99

4.7 数字三角形问题 100

4.8 ZOJ1027-Human Gene Functions 101

4.9 ZOJ1074-To the Max 105

4.10 ZOJ1093-Monkey and Banana 106

4.11 ZOJ1107-FatMouse and Cheese 111

4.12 ZOJ1108-FatMouse's Speed 114

4.13 ZOJ1147-Formatting Text 118

4.14 ZOJ1149-Dividing 123

4.15 ZOJ1163-The Staircases 127

4.16 ZOJ1183-Scheduling Lectures 130

4.17 ZOJ1196-Fast Food 133

4.18 ZOJ1206-Win the Bonus 137

4.19 ZOJ1227-Free Candies 140

4.20 ZOJ1234-Chopsticks 144

上机练习题 147

第5章 贪心算法 151

5.1 活动安排问题 151

5.2 贪心算法的理论基础 153

5.2.1 贪心选择性质 154

5.2.2 最优子结构性质 154

5.2.3 贪心算法的求解过程 154

5.3 背包问题 155

5.4 最优装载问题 158

5.5 单源最短路径 159

5.6 最小生成树 163

5.6.1 最小生成树的性质 163

5.6.2 Prim算法 164

5.6.3 Kruskal算法 166

5.7 删数问题 169

5.7.1 问题的贪心选择性质 170

5.7.2 问题的最优子结构性质 171

5.8 多处最优服务次序问题 171

5.8.1 问题的贪心选择性质 173

5.8.2 问题的最优子结构性质 173

5.9 ZOJ1012-Mainframe 174

5.10 ZOJ1025-Wooden Sticks 178

5.11 ZOJ1029-Moving Tables 181

5.12 ZOJ1076-Gene Assembly 183

5.13 ZOJ1161-Gone Fishing 185

5.14 ZOJ1171-Sorting the Photos 189

5.15 ZOJ2109-FatMouse'Trade 190

上机练习题 192

第6章 回溯算法 194

6.1 回溯算法的理论基础 194

6.1.1 问题的解空间 194

6.1.2 回溯法的基本思想 195

6.1.3 子集树与排列树 197

6.2 装载问题 198

6.3 0-1背包问题 201

6.4 图的m着色问题 203

6.5 n皇后问题 206

6.6 旅行商问题 208

6.7 流水作业调度问题 210

6.8 子集和问题 213

6.9 ZOJ1145-Dreisam Equations 215

6.10 ZOJ1157-A Plug for UNIX 220

6.11 ZOJ1166-Anagram Checker 226

6.12 ZOJ1213-Lumber Cutting 230

上机练习题 234

第7章 分支限界算法 235

7.1 分支限界算法的基本理论 235

7.1.1 分支限界算法策略 235

7.1.2 分支结点的选择 236

7.1.3 提高分支限界算法的效率 236

7.1.4 限界函数 237

7.2 单源最短路径问题 237

7.3 装载问题 242

7.4 0-1背包问题 245

7.5 旅行商问题 251

7.6 ZOJ1136-Multiple 254

7.7 回溯算法与分支限界算法的比较 258

上机练习题 258

第8章 图的搜索算法 259

8.1 图的深度优先搜索遍历 259

8.2 ZOJ1002-Fire Net 260

8.3 ZOJ1008-Gnome Tetravex 262

8.4 ZOJ1047-Image Perimeters 267

8.5 ZOJ1084-Channel Allocation 271

8.6 ZOJ1142-Maze 274

8.7 ZOJ1190-Optimal Programs 278

8.8 ZOJ1191-The Die Is Cast 284

8.9 ZOJ1204-Additive Equations 287

8.10 ZOJ1245-Triangles 290

8.11 ZOJ2100-Seeding 293

8.12 图的广度优先搜索遍历 296

8.13 ZOJ1079-Robotic Jigsaw 297

8.14 ZOJ1085-Alien Security 301

8.15 ZOJ1103-Hike on a Graph 305

8.16 ZOJ1148-The Game 308

8.17 ZOJ1217-Eight 311

8.18 ZOJ1091-Knight Moves 317

上机练习题 321

第9章 图论 323

9.1 网络流问题 323

9.1.1 流和割的概念 323

9.1.2 剩余网络和增广路 324

9.1.3 Ford-Fulkerson算法 325

9.1.4 Edmonds-Karp算法 326

9.1.5 ZOJ1734-Power Network——Edmonds-Karp算法 327

9.1.6 ISAP算法 330

9.1.7 ZOJ1734-Power Network——ISAP算法 332

9.1.8 Dinic算法 334

9.1.9 ZOJ1734-Power Network——Dinic算法 335

9.1.10 最小费用流——SPFA算法 337

9.1.11 ZOJ2404-Going Home——SPFA算法 338

9.2 二分图匹配问题 341

9.2.1 匹配问题 341

9.2.2 二分图最大匹配——匈牙利算法 343

9.2.3 ZOJ1137-Girls and Boys 344

9.2.4 ZOJ1140-Courses——匈牙利算法 346

9.2.5 PJU1247-The Perfect Stall——匈牙利算法 349

9.2.6 Hopcroft-Karp算法 352

9.2.7 ZOJ1140-Courses——Hopcroft-Karp算法 353

9.2.8 PJU1247-The Perfect Stall——Hopcroft-Karp算法 355

9.2.9 二分图最佳匹配——Kuhn Munkres算法 357

9.2.10 ZOJ2404-Going Home——Kuhn Munkres算法 358

上机练习题 360

第10章 数论 362

10.1 扩展欧几里得算法 362

10.2 PJU2115-C Looooops 363

10.3 欧拉函数 365

10.4 ZOJ1906-Relatives 366

10.5 PJU2480-Longge's Problem 367

10.6 PJU3696-The Luckiest Number 369

10.7 中国剩余定理 372

10.8 ZOJ1160-Biorhythms 372

10.9 一元线性同余方程组 374

10.10 PJU2891-Strange Way to Express Integers 375

10.11 HDU1572-X问题 377

上机练习题 378

第11章 组合数学 381

11.1 母函数 381

11.1.1 普通型母函数 381

11.1.2 指数型母函数 383

11.1.3 Stirling数 384

11.1.4 Catalan数 386

11.2 HDU2082-找单词 387

11.3 HDU1521-排列组合 388

11.4 HDU2065-“红色病毒”问题 389

11.5 HDU3625-Examining the Rooms 391

11.6 POJ2084-Game of Connections 393

11.7 容斥原理与鸽巢原理 394

11.7.1 容斥原理 394

11.7.2 错排问题 395

11.7.3 鸽巢原理 396

11.8 HDU2048-神、上帝以及老天爷 397

11.9 PJU2356-Find a Multiple 398

11.10 ZOJ2836-Number Puzzle 400

上机练习题 401

参考文献 404