算法分析与设计 以大学生程序设计竞赛为例2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

算法分析与设计 以大学生程序设计竞赛为例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章 数据结构和标准模板库13

2.1栈13

2.2向量14

2.3映射15

2.4列表17

2.5集合19

2.6队列20

2.7优先队列21

2.8 ZOJ1004-Anagrams by Stack23

2.9 ZOJ1094-Matrix Chain Multiplication25

2.10 ZOJ1011-NTA28

2.11 ZOJ1062-Trees Made to Order33

2.12 ZOJ1097-Code the Tree37

2.13 ZOJ1156-Unscrambling Images40

2.14 ZOJ1167-Trees on the Level45

2.15 ZOJ1016-Parencodings47

2.16 ZOJ1944-Tree Recovery50

2.17 ZOJ2104- Let the Balloon Rise52

上机练习题54

第3章 递归与分治策略56

3.1递归算法56

3.1.1 Fibonacci数列57

3.1.2集合的全排列问题58

3.1.3整数划分问题59

3.2分治策略60

3.2.1分治法的基本步骤60

3.2.2分治法的适用条件61

3.2.3二分搜索技术61

3.2.4循环赛日程表62

3.2.5棋盘覆盖问题64

3.2.6选择问题67

3.2.7输油管道问题69

3.2.8半数集问题70

3.2.9整数因子分解72

3.2.10取余运算73

3.3 Big String74

上机练习题76

第4章 动态规划77

4.1矩阵连乘积问题78

4.1.1分析最优解的结构80

4.1.2建立递归关系81

4.1.3计算最优值81

4.1.4构造最优解84

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

4.2.1最优子结构85

4.2.2重叠子问题85

4.2.3备忘录方法86

4.3最长公共子序列87

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

4.3.2子问题的递归结构88

4.3.3计算最优值89

4.3.4构造最长公共子序列90

4.4最大子段和91

4.5 0-1背包问题93

4.5.1递归关系分析93

4.5.2算法实现94

4.6最长单调递增子序列95

4.7数字三角形问题96

4.8 ZOJ1013-Great Equipment98

4.9 ZOJ1027-Human Gene Functions104

4.10 ZOJ1074-To the Max107

4.11 ZOJ1093-Monkey and Banana109

4.12 ZOJ1100-Mondriaan’s Dream114

4.13 ZOJ1102-Phylogenetic Trees Inherited118

4.14 ZOJ1107-FatMouse and Cheese122

4.15 ZOJ1108-FatMouse’s Speed125

4.16 ZOJ1132-Railroad129

4.17 ZOJ1147-Formatting Text134

4.18 ZOJ1149-Dividing139

4.19 ZOJ1163-The Staircases143

4.20 ZOJ1183-Scheduling Lectures145

4.21 ZOJ1196-Fast Food148

4.22 ZOJ1206-Win the Bonus152

4.23 ZOJ1227-Free Candies155

4.24 ZOJ1234-Chopsticks159

上机练习题162

第5章 贪心算法165

5.1活动安排问题165

5.2贪心算法的理论基础167

5.2.1贪心选择性质168

5.2.2最优子结构性质168

5.2.3贪心算法的求解过程168

5.3背包问题169

5.4最优装载问题172

5.5单源最短路径173

5.6最小生成树177

5.6.1最小生成树的性质177

5.6.2 Prim算法178

5.6.3 Kruskal算法180

5.7删数问题183

5.7.1问题的贪心选择性质184

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

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

5.8.1问题的贪心选择性质187

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

5.9 ZOJ1012-Mainframe187

5.10 ZOJ1025-Wooden Sticks192

5.11 ZOJ1029-Moving Tables194

5.12 ZOJ1076-Gene Assembly197

5.13 ZOJ1161-Gone Fishing199

5.14 ZOJ1171-Sorting the Photos202

5.15 ZOJ2109-FatMouse’Trade204

上机练习题206

第6章 回溯算法207

6.1回溯算法的理论基础207

6.1.1问题的解空间207

6.1.2回溯法的基本思想207

6.1.3子集树与排列树210

6.2装载问题211

6.3 0-1背包问题214

6.4图的m着色问题216

6.5 n皇后问题219

6.6旅行商问题221

6.7流水作业调度问题223

6.8子集和问题226

6.9 ZOJ1145-Dreisam Equations228

6.10 ZOJ1157-A Plug for UNIX233

6.11 ZOJ1166-Anagram Checker238

6.12 ZOJ1213-Lumber Cutting242

上机练习题246

第7章 分支限界算法248

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

7.1.1分支限界算法策略248

7.1.2分支结点的选择249

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

7.1.4限界函数250

7.2单源最短路径问题250

7.3装载问题254

7.4 0-1背包问题258

7.5旅行商问题264

7.6 ZOJ1136-Multiple267

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

上机练习题271

第8章 图的搜索算法272

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

8.2 ZOJ1002-Fire Net273

8.3 ZOJ1008-Gnome Tetravex276

8.4 ZOJ1047-Image Perimeters280

8.5 ZOJ1084-Channel Allocation284

8.6 ZOJ1142-Maze287

8.7 ZOJ1190-Optimal Programs291

8.8 ZOJ1191-The Die Is Cast297

8.9 ZOJ1204-Additive Equations301

8.10 ZOJ1245-Triangles304

8.11 ZOJ2100-Seeding307

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

8.13 ZOJ1055- Oh，Those Achin’Feet310

8.14 ZOJ1079- Robotic Jigsaw317

8.15 ZOJ1085-Alien Security322

8.16 ZOJ1103- Hike on a Graph325

8.17 ZOJ1148- The Game329

8.18 ZOJ1217-Eight332

8.19 ZOJ 1091-Knight Moves337

上机练习题342

参考文献344