全国信息学奥林匹克联赛培训教程 普及本 22025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

全国信息学奥林匹克联赛培训教程 普及本 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