算法设计与分析 以ACM大学生程序设计竞赛在线题库为例PDF|Epub|txt|kindle电子书版本网盘下载

算法设计与分析 以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章 数据结构和标准模板库STL13

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 Stack25

2.9 ZOJ1094-Matrix Chain Multiplication28

2.10 ZOJ1011-NTA31

2.11 ZOJ1062-Trees Made to Order36

2.12 ZOJ1097-Code the Tree40

2.13 ZOJ1156-Unscrambling Images43

2.14 ZOJ1167-Trees on the Level47

2.15 ZOJ1016-Parencodings50

2.16 ZOJ1944-Tree Recovery53

2.17 ZOJ2104-Let the Balloon Rise55

上机练习题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 String78

上机练习题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 Functions101

4.9 ZOJ1074-To the Max105

4.10 ZOJ1093-Monkey and Banana106

4.11 ZOJ1107-FatMouse and Cheese111

4.12 ZOJ1108-FatMouse's Speed114

4.13 ZOJ1147-Formatting Text118

4.14 ZOJ1149-Dividing123

4.15 ZOJ1163-The Staircases127

4.16 ZOJ1183-Scheduling Lectures130

4.17 ZOJ1196-Fast Food133

4.18 ZOJ1206-Win the Bonus137

4.19 ZOJ1227-Free Candies140

4.20 ZOJ1234-Chopsticks144

上机练习题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-Mainframe174

5.10 ZOJ1025-Wooden Sticks178

5.11 ZOJ1029-Moving Tables181

5.12 ZOJ1076-Gene Assembly183

5.13 ZOJ1161-Gone Fishing185

5.14 ZOJ1171-Sorting the Photos189

5.15 ZOJ2109-FatMouse'Trade190

上机练习题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 Equations215

6.10 ZOJ1157-A Plug for UNIX220

6.11 ZOJ1166-Anagram Checker226

6.12 ZOJ1213-Lumber Cutting230

上机练习题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-Multiple254

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

上机练习题258

第8章 图的搜索算法259

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

8.2 ZOJ1002-Fire Net260

8.3 ZOJ1008-Gnome Tetravex262

8.4 ZOJ1047-Image Perimeters267

8.5 ZOJ1084-Channel Allocation271

8.6 ZOJ1142-Maze274

8.7 ZOJ1190-Optimal Programs278

8.8 ZOJ1191-The Die Is Cast284

8.9 ZOJ1204-Additive Equations287

8.10 ZOJ1245-Triangles290

8.11 ZOJ2100-Seeding293

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

8.13 ZOJ1079-Robotic Jigsaw297

8.14 ZOJ1085-Alien Security301

8.15 ZOJ1103-Hike on a Graph305

8.16 ZOJ1148-The Game308

8.17 ZOJ1217-Eight311

8.18 ZOJ1091-Knight Moves317

上机练习题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 Boys344

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 Looooops363

10.3 欧拉函数365

10.4 ZOJ1906-Relatives366

10.5 PJU2480-Longge's Problem367

10.6 PJU3696-The Luckiest Number369

10.7 中国剩余定理372

10.8 ZOJ1160-Biorhythms372

10.9 一元线性同余方程组374

10.10 PJU2891-Strange Way to Express Integers375

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 Rooms391

11.6 POJ2084-Game of Connections393

11.7 容斥原理与鸽巢原理394

11.7.1 容斥原理394

11.7.2 错排问题395

11.7.3 鸽巢原理396

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

11.9 PJU2356-Find a Multiple398

11.10 ZOJ2836-Number Puzzle400

上机练习题401

参考文献404