内容简介
本书内括经典的算法设计技术，主要介绍数据结构和标准模板库、递归与分治策略、动态规划、贪心算法、回溯算法、分支限界算法、图的搜索算法、图论、数论和组合数学问题。本括大量的问题实例，并在北京大学、浙江大学和杭州电子科技大学在线题库中原题，详细地分析解题的方法，深入浅出地讲解用到的算法，章后的上机练选自在线题库中的典型题目，供读者练巩固所学算法。本书内容基本上涵盖了目前大学生程序设计竞赛所要掌握的算法。 本书结构清晰、内容丰富，适合作为计算机科学与技术、软件工程以及相关学科算法课程的教材或参考书，适合有志于参加信息学竞赛和ACM大学生程序设计竞赛的读者学练。
目录
第1章 算法概述 1.1 引言 1.1.1 算法的描述 1.1.2 算法的设计 1.2 算法的复杂度 1.2.1 时间复杂度 1.2.2 空间复杂度 1.3 大学生程序设计竞赛概述 1.4 程序设计在线测试题库第2章 数据结构和标准模板库 2.1 栈 2.2 向量 2.3 映射 2.4 列表 2.5 集合 2.6 队列 2.7 优先队列 2.8 ZOJ1004-Anagramy Stack 2.9 ZOJ1094-Matrix Chain Multiplication 2.10 ZOJ1011-NTA 2.11 ZOJ1062-Trees Made to Order 2.12 ZOJ1097-Code the Tree 2.13 ZOJ1156-Unscrambling Imager/> 2.14 ZOJ1167-Trees on the Level 2.15 ZOJ1016-Parencodingr/> 2.16 ZOJ1944-Tree Recovery 2.17 ZOJ2104-Let the Balloon Rir/> 上机练br/>第3章 递归与分治策略 3.1 递归算法 3.1.1 Fibonacci数列 3.1.2 集合的全排列问题 3.1.3 整数划分问题 3.2 分治策略 3.2.1 分治策略的基本步骤 3.2.2 分治策略的适用条件 3.2.3 二分搜索算法 3.2.4 循环赛日程表 3.2.5 棋盘覆盖问题 3.2.6 选择问题 3.2.7 输油管道问题 3.2.8 半数集问题 3.2.9 整数因子分解 3.2.10 取余运算 3.3 ZOJ1633-Big String 上机练br/>第4章 动态规划 4.1 矩阵连乘积问题 4.1.1 分析优解的结构 4.1.2 建立递归关系 4.1.3 计算优值 4.1.4 构造优解 4.2 动态规划算法的基本要素 4.2.1 优子结构 4.2.2 重叠子问题 4.2.3 备忘录方法 4.3 长公共子序列 4.3.1 长公共子序列的结构 4.3.2 子问题的递归结构 4.3.3 计算优值 4.3.4 构造长公共子序列 4.4 大子段和 4.5 0-1问题 4.5.1 递归关系分析 4.5.2 算法实现 4.6 长单调递增子序列 4.7 数字三角形问题 4.8 ZOJ1027-Human Gene Functionr/> 4.9 ZOJ1074-To the Max 4.10 ZOJ1093-Monkey and Banana 4.11 ZOJ1107-FatMouse and Cheer/> 4.12 ZOJ1108-FatMouse's Speed 4.13 ZOJ1147-Formatting Text 4.14 ZOJ1149-Dividing 4.15 ZOJ1163-The Staircaser/> 4.16 ZOJ1183-Scheduling Lecturer/> 4.17 ZOJ1196-Fast Food 4.18 ZOJ1206-Win the Bonur/> 4.19 ZOJ1227-Free Candier/> 4.20 ZOJ1234-Chopstickr/> 上机练br/>第5章 贪心算法 5.1 活动安排问题 5.2 贪心算法的理论基础 5.2.1 贪心选择质 5.2.2 优子结构质 5.2.3 贪心算法的求解过程 5.3 问题 5.4 优装载问题 5.5 单源短路径 5.6 小生成树 5.6.1 小生成树的质 5.6.2 Prim算法 5.6.3 Kruskal算法 5.7 删数问题 5.7.1 问题的贪心选择质 5.7.2 问题的优子结构质 5.8 多处优服务次序问题 5.8.1 问题的贪心选择质 5.8.2 问题的优子结构质 5.9 ZOl1012-Mainframe 5.10 ZOJ1025-Wooden Stickr/> 5.11 ZOJ1029-Moving Tabler/> 5.12 ZOJ1076-Gene Asly 5.13 ZOJ1161-Gone Fishing 5.14 Z0J1171-Sorting the Photor/> 5.15 ZOJ2109-FatMouse' Trade 上机练br/>第6章 回溯算法 6.1 回溯算法的理论基础 6.1.1 问题的解空间 6.1.2 回溯算法的基本思想 6.1.3 子集树与排列树 6.2 装载问题 6.3 0-1问题 6.4 图的m着色问题 6.5 n皇后问题 6.6 旅行商问题 6.7 流水作业调度问题 6.8 子集和问题 6.9 ZOJ1145-Dreisam Equationr/> 6.10 ZOJ1157-A Plug for UNIX 6.11 ZOJ1166-Anagram Checker 6.12 ZOJ1213-Lumber Cutting 上机练br/>第7章 分支限界算法 7.1 分支限界算法的基本理论 7.1.1 分支限界算法策略 7.1.2 分支结点的选择 7.1.3 提高分支限界算法的效率 7.1.4 限界函数 7.2 单源短路径问题 7.3 装载问题 7.4 0-1问题 7.5 旅行商问题 7.6 ZOJ1136-Multiple 7.7 回溯算法与分支限界算法的比较 上机练br/>第8章 图的搜索算法 8.1 图的深度优先搜索遍历 8.2 ZOJ1002-Fire Net 8.3 ZOJ1008-Gnome Tetravex 8.4 ZOJ1047-Image Perimeterr/> 8.5 ZOJ1084-Channel Allocation 8.6 ZOJ1142-Maze 8.7 ZOJ1190-Optimal Programr/> 8.8 ZOJ1191-The Die Is Car/> 8.9 ZOJ1204-itive equationr/> 8.10 ZOJ1245-Triangler/> 8.11 ZOJ2100-Seeding 8.12 图的广度优先搜索遍历 8.13 ZOJ1079-Robotic Jigsaw 8.14 ZOJ1085-Alien Security 8.15 ZOJ1103-Hike on a Graph 8.16 ZOJ1148-The Game 8.17 ZOJ1217-Eight 8.18 ZOJ1091-Knight Mover/> 上机练br/>第9章 图论 9.1 网络流问题 9.1.1 流和割的概念 9.1.2 剩余网络和增广路径 9.1.3 Ford-Fulkerson算法 9.1.4 Edmonds-Karp算法 9.1.5 ZOJ1734-Power Network-—-Edmonds-Karp算法 9.1.6 ISAP算法 9.1.7 ZOJ1734-Power Network——ISAP算法 9.1.8 Dinic算法 9.1.9 ZOI1734-Power Network——-Dinic 算法 9.1.10 小费用流——SPFA算法 9.1.11 ZOJ2404-Going Home——SPFA算法 9.2 二分图匹配问题 9.2.1 匹配问题 9.2.2 二分图大匹配——匈牙利算法 9.2.3 ZOJ1137-Girls and Boyr/> 9.2.4 ZOJ1140-Courses——匈牙利算法 9.2.5 PJU1247-The Perfect Stall-——句牙利算法 9.2.6 Hoperoft-Karp 算法 9.2.7 ZOJ1140-Courses--Hopcroft-Karp算法 9.2.8 PJU1274-The Perfect Stall---Hopcroft-Karp 算法 9.2.9 二分图佳匹配——Kuhn Munkres算法 9.2.10 ZOJ2404-Going Home——Kuhn Munkres 算法 上机练br/>第10章 数论 10.1 扩展欧几里得算法 10.2 PJU2115-C Looooopr/> 10.3 欧拉函数 10.4 ZOJ1906-Relativer/> 10.5 PJU2480-Longge's problem 10.6 PJU3696-The Luckiest number 10.7 中国剩余定理 10.8 ZOJ1160-Biorhythmr/> 10.9 一元线同余方程组 10.10 PJU2891-Strange Way to Express Integerr/> 10.11 HDU1573-X问颞 上机练br/>第11章 组合数学 11.1 母函数 11.1.1 普通型母函数 11.1.2 指数型母函数 11.1.3 Stirling 数 11.1.4 Catalan 数 11.2 HDU2082-找单词 11.3 HDU1521-排列组合 11.4 HDU2065-“红色病毒”问题 11.5 HDU3625-Examining the Roomr/> 11.6 POJ2084-Game of Connection 11.7 容斥原理与鸽巢原理 11.7.1 容斥原理 11.7.2 错排问题 11.7.3 鸽巢原理 11.8 HDU2048-“恭喜你，中奖了！” 11.9 POJ2356-Find a multiple 11.10 ZOJ2836-Number Puzzle 上机练br/>参考文献