全国信息学奥林匹克联赛培训教程 普及本 2PDF电子书下载

第一篇 程序的测试和效率分析 3

第1章 测试程序 3

1.1 系统的测试工具 3

1.1.1 调试初始化 6

1.1.2 单步跟踪 7

1.1.3 执行到光标所在行 7

1.1.4 断点 7

1.1.5 求值和修改 7

1.1.6 路标 8

1.1.7 准备编译运行调试后的程序 8

1.2 测试用例的选取方法 8

1.2.1 白箱法 8

1.2.2 黑箱法 11

1.2.3 综合策略 13

习题 15

第2章 程序的效率分析 17

2.1 程序工作量的度量方法 17

2.1.1 基本运算 17

2.1.2 输入尺寸 18

2.1.3 输入情况 18

2.1.4 复杂度的阶 20

2.2 优化时间效率的方法 21

2.2.1 常数计算 22

2.2.2 尽可能在编译时赋值 23

2.2.3 算术运算 23

2.2.4 避免重复计算 24

2.2.5 应有利于编译优化 25

2.2.6 关于循环结构 25

2.2.7 关于选择语句 28

2.2.9 关于下标变量 30

2.2.8 关于逻辑表达式 30

2.2.10 尽量利用库模块 32

2.3 程序的最优性 32

2.4 程序的空间复杂度 35

2.4.1 压缩存储技术 36

2.4.2 原地工作 37

习题 37

第二篇 数据结构 41

第3章 顺序存储结构的线性表 41

3.1 线性表的定义 41

3.1.1 顺序存储结构 42

3.1.2 链式存储结构 43

3.2 栈 44

3.2.1 栈的定义 44

3.2.2 栈的基本运算 45

3.2.3 栈的重要应用——计算表达式值 46

3.3 队列 50

3.3.1 队列的定义 50

3.3.2 队列的基本运算 51

3.3.3 循环队列 52

3.3.4 队列的应用——计算广义线性表 54

3.4 串 58

3.4.1 串的基本概念 58

3.4.2 串运算的库函数 60

3.4.3 串运算的应用——子串模式匹配 61

习题 66

第4章 非线性结构——树和图 69

4.1 树 69

4.1.1 树的概念 70

4.1.2 树的表示方法和存储结构 72

4.1.3 二叉树的概念 74

4.1.4 树或森林转换成二叉树 76

4.1.5 二叉树的存储结构 78

4.1.6 树或森林的遍历 79

4.1.7 由二叉树的两种遍历顺序确定树结构 87

4.1.8 二叉树的重要应用 90

4.2 图 97

4.2.1 图的基本概念 97

4.2.2 图的存储结构 99

4.2.3 图的遍历和图的生成树 102

4.2.4 图的应用 106

习题 124

第三篇 算法设计 129

第5章 高精度运算 129

5.1 高精度的十进制运算 129

5.1.1 数据类型 129

5.1.2 基本运算 130

5.2.1 扩大进制数 132

5.2 改善高精度运算的效率 132

5.2.2 建立因子表 134

习题 135

第6章 构造法 141

6.1 对应策略 142

6.1.1 对应经典问题 142

6.1.2 对应简单问题 147

6.1.3 对应数学问题 151

6.2 分治策略 159

6.2.1 递推的分治策略 160

6.2.2 递归的分治策略 162

6.3 归纳策略 166

6.3.1 递推法 166

6.3.2 递归法 174

6.3.3 制定目标 177

6.3.4 贪心法 178

6.4 模拟策略 185

6.4.1 直叙式模拟 186

6.4.2 筛选法模拟 188

6.4.3 构造法模拟 189

习题 194

第7章 搜索法 203

7.1 枚举法 203

7.1.1 “直译”的枚举算法 204

7.1.2 枚举算法的优化 207

7.2 回溯法 213

7.2.1 回溯法的基本思路 213

7.2.2 回溯法的应用实例 219

7.2.3 回溯法的优化 225

7.3 广度优先搜索 229

7.3.1 广度优先搜索的基本思路 229

7.3.2 求初始状态所能到达的所有状态 230

7.3.3 计算初始状态到目标状态的最短路径 235

习题 239

第8章 动态程序设计方法 243

8.1 问题的引出 243

8.2 动态程序设计方法的基本概念 246

8.2.1 阶段和状态 246

8.2.2 决策和策略 247

8.2.3 最优化原理与无后效性 248

8.2.4 最优指标函数和状态转移方程 248

8.3 动态程序设计方法的基本思维方式 249

8.4 动态程序设计方法的应用实例 254

8.4.1 计算所有方案 254

8.4.2 计算一些阶段性明显、但不具备最优子结构特征的问题 256

8.4.3 双重动态程序设计 257

8.4.4 多进程的最优化决策问题 263

习题 266