算法分析与设计 以大学生程序设计竞赛为例

第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睞nagramsbyStack2.9 ZOJ1094睲atrixChainMultiplication2.1 0ZOJ1011睳TA2.1 1ZOJ1062睺reesMadetoOrder2.1 2ZOJ1097睠odetheTree2.1 3ZOJ1156睻nscramblingImages2.1 4ZOJ1167睺reesontheLevel2.1 5ZOJ1016睵arencodings2.1 6ZOJ1944睺reeRecovery2.1 7ZOJ2104睱ettheBalloonRise上机练习题第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.1 0取余运算3.3 BigString上机练习题第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　01背包问题4.5.1 递归关系分析4.5.2 算法实现4.6 最长单调递增子序列4.7 数字三角形问题4.8 ZOJ1013睪reatEquipment4.9 ZOJ1027睭umanGeneFunctions4.1 0ZOJ1074睺otheMax4.1 1ZOJ1093睲onkeyandBanana4.1 2ZOJ1100睲ondriaan餾Dream4.1 3ZOJ1102睵hylogeneticTreesInherited4.1 4ZOJ1107睩atMouseandCheese4.1 5ZOJ1108睩atMouse餾Speed4.1 6ZOJ1132睷ailroad4.1 7ZOJ1147睩ormattingText4.1 8ZOJ1149睤ividing4.1 9ZOJ1163睺heStaircases4.2 0ZOJ1183睸chedulingLectures4.2 1ZOJ1196睩astFood4.2 2ZOJ1206瞁intheBonus4.2 3ZOJ1227睩reeCandies4.2 4ZOJ1234睠hopsticks上机练习题第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　ZOJ1012 Mainframe5.10 ZOJ1025 WoodenSticks5.11 ZOJ1029 MovingTables5.12 ZOJ1076 GeneAssembly5.13 ZOJ1161 GoneFishing5.14 ZOJ1171 SortingthePhotos5.15 ZOJ2109 FatMouse Trade上机练习题第6章 回溯算法6.1 回溯算法的理论基础6.1.1 问题的解空间6.1.2 回溯法的基本思想6.1.3 子集树与排列树6.2 装载问题6.3　01背包问题6.4 图的m着色问题6.5 n皇后问题6.6 旅行商问题6.7 流水作业调度问题6.8 子集和问题6.9 ZOJ1145睤reisamEquations6.1 0ZOJ1157睞PlugforUNIX6.1 1ZOJ1166睞nagramChecker6.1 2ZOJ1213睱umberCutting上机练习题第7章 分支限界算法7.1 分支限界算法的基本理论7.1.1 分支限界算法策略7.1.2 分支结点的选择7.1.3 提高分支限界算法的效率7.1.4 限界函数7.2 单源最短路径问题7.3 装载问题7.4　01背包问题7.5 旅行商问题7.6 ZOJ1136睲ultiple7.7 回溯算法与分支限界算法的比较上机练习题第8章 图的搜索算法8.1 图的深度优先搜索遍历8.2　ZOJ1002 FireNet8.3　ZOJ1008 GnomeTetravex8.4　ZOJ1047 ImagePerimeters8.5　ZOJ1084 ChannelAllocation8.6　ZOJ1142 Maze8.7　ZOJ1190 OptimalPrograms8.8　ZOJ1191 TheDieIsCast8.9 ZOJ1204 AdditiveEquations8.1 0 ZOJ1245 Triangles8.11　ZOJ2100 Seeding8.12 图的广度优先搜索遍历8.13 ZOJ1055 Oh,ThoseAchin餏eet8.14 ZOJ1079 RoboticJigsaw8.15 ZOJ1085 AlienSecurity8.16 ZOJ1103 HikeonaGraph8.17 ZOJ1148 TheGame8.18 ZOJ1217 Eight8.19 ZOJ1091 KnightMoves上机练习题参考文献