目录

第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．8ZOJ1004Anagrams by Stack

2．9ZOJ1094Matrix Chain Multiplication

2．10ZOJ1011NTA

2．11ZOJ1062Trees Made to Order

2．12ZOJ1097Code the Tree

2．13ZOJ1156Unscrambling Images

2．14ZOJ1167Trees on the Level

2．15ZOJ1016Parencodings

2．16ZOJ1944Tree Recovery

2．17ZOJ2104Let the Balloon Rise

上机练习题

第3章递归与分治策略

3．1递归算法

3．1．1Fibonacci数列

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．3ZOJ1633Big String

上机练习题

第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．501背包问题

4．5．1递归关系分析

4．5．2算法实现

4．6最长单调递增子序列

4．7数字三角形问题

4．8ZOJ1027Human Gene Functions

4．9ZOJ1074To the Max

4．10ZOJ1093Monkey and Banana

4．11ZOJ1107FatMouse and Cheese

4．12ZOJ1108FatMouses Speed

4．13ZOJ1147Formatting Text

4．14ZOJ1149Dividing

4．15ZOJ1163The Staircases

4．16ZOJ1183Scheduling Lectures

4．17ZOJ1196Fast Food

4．18ZOJ1206Win the Bonus

4．19ZOJ1227Free Candies

4．20ZOJ1234Chopsticks

上机练习题

第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．2Prim算法

5．6．3Kruskal算法

5．7删数问题

5．7．1问题的贪心选择性质

5．7．2问题的最优子结构性质

5．8多处最优服务次序问题

5．8．1问题的贪心选择性质

5．8．2问题的最优子结构性质

5．9ZOJ1012Mainframe

5．10ZOJ1025Wooden Sticks

5．11ZOJ1029Moving Tables

5．12ZOJ1076Gene Assembly

5．13ZOJ1161Gone Fishing

5．14ZOJ1171Sorting the Photos

5．15ZOJ2109FatMouse Trade

上机练习题

第6章回溯算法

6．1回溯算法的理论基础

6．1．1问题的解空间

6．1．2回溯算法的基本思想

6．1．3子集树与排列树

6．2装载问题

6．301背包问题

6．4图的m着色问题

6．5n皇后问题

6．6旅行商问题

6．7流水作业调度问题

6．8子集和问题

6．9ZOJ1145Dreisam Equations

6．10ZOJ1157A Plug for UNIX

6．11ZOJ1166Anagram Checker

6．12ZOJ1213Lumber Cutting

上机练习题

第7章分支限界算法

7．1分支限界算法的基本理论

7．1．1分支限界算法策略

7．1．2分支结点的选择

7．1．3提高分支限界算法的效率

7．1．4限界函数

7．2单源最短路径问题

7．3装载问题

7．401背包问题

7．5旅行商问题

7．6ZOJ1136Multiple

7．7回溯算法与分支限界算法的比较

上机练习题

第8章图的搜索算法

8．1图的深度优先搜索遍历

8．2ZOJ1002Fire Net

8．3ZOJ1008Gnome Tetravex

8．4ZOJ1047Image Perimeters

8．5ZOJ1084Channel Allocation

8．6ZOJ1142Maze

8．7ZOJ1190Optimal Programs

8．8ZOJ1191The Die Is Cast

8．9ZOJ1204Additive equations

8．10ZOJ1245Triangles

8．11ZOJ2100Seeding

8．12图的广度优先搜索遍历

8．13ZOJ1079Robotic Jigsaw

8．14ZOJ1085Alien Security

8．15ZOJ1103Hike on a Graph

8．16ZOJ1148The Game

8．17ZOJ1217Eight

8．18ZOJ1091Knight Moves

上机练习题

第9章图论

9．1网络流问题

9．1．1流和割的概念

9．1．2剩余网络和增广路径

9．1．3FordFulkerson算法

9．1．4EdmondsKarp算法

9．1．5ZOJ1734Power Network——EdmondsKarp算法

9．1．6ISAP算法

9．1．7ZOJ1734Power Network——ISAP算法

9．1．8Dinic算法

9．1．9ZOJ1734Power Network——Dinic算法

9．1．10最小费用流——SPFA算法

9．1．11ZOJ2404Going Home——SPFA算法

9．2二分图匹配问题

9．2．1匹配问题

9．2．2二分图最大匹配——匈牙利算法

9．2．3ZOJ1137Girls and Boys

9．2．4ZOJ1140Courses——匈牙利算法

9．2．5PJU1247The Perfect Stall——匈牙利算法

9．2．6HopcroftKarp算法

9．2．7ZOJ1140Courses——HopcroftKarp算法

9．2．8PJU1274The Perfect Stall——HopcroftKarp算法

9．2．9二分图最佳匹配——Kuhn Munkres算法

9．2．10ZOJ2404Going Home——Kuhn Munkres算法

上机练习题

第10章数论

10．1扩展欧几里得算法

10．2PJU2115C Looooops

10．3欧拉函数

10．4ZOJ1906Relatives

10．5PJU2480Longges problem

10．6PJU3696The Luckiest number

10．7中国剩余定理

10．8ZOJ1160Biorhythms

10．9一元线性同余方程组

10．10PJU2891Strange Way to Express Integers

10．11HDU1573X问题

上机练习题

第11章组合数学

11．1母函数

11．1．1普通型母函数

11．1．2指数型母函数

11．1．3Stirling数

11．1．4Catalan数

11．2HDU2082找单词

11．3HDU1521排列组合

11．4HDU2065“红色病毒”问题

11．5HDU3625Examining the Rooms

11．6POJ2084Game of Connection

11．7容斥原理与鸽巢原理

11．7．1容斥原理

11．7．2错排问题

11．7．3鸽巢原理

11．8HDU2048“恭喜你，中奖了！”

11．9POJ2356Find a multiple

11．10ZOJ2836Number Puzzle

上机练习题

参考文献