| ICPC培训讲义 算法与程序设计 前言 II 目录 iii 第一章 STL简介 1 一、引 言 1 二、STL组成结构 2 三、STL的应用 3 第二章 搜 索 28 一、宽度优先搜索 BFS 28 二、最小生成树的形成和求解(PRIM AND KRUSKAL) 34 1. 最小生成树的形成 34 2．Kruskal算法和Prim算法 37 三、深度优先搜索 DFS 44 1.概述 44 2.深度优先搜索的性质 48 3. 边的分类 50 第三章 计算几何学 53 一、引 言 53 二、线段的性质（LINE-SEGMENT PROPERITIES） 54 1.叉积（Cross Product） 54 2.线段是否相交（Determining Intersections） 55 三、点集的性质（POINT-SET PROPERITIES） 57 1.寻找凸包（Finding the convex hull） 57 第四章 动态规划 63 一、引言——由一个问题引出的算法 63 二、动态规划的基本概念 65 2.1动态规划的发展及研究内容 65 2.2多阶段决策问题 65 2.3决策过程的分类 66 三、动态规划模型的基本要素 66 四、动态规划的基本定理和基本方程 68 五、动态规划的适用条件 69 5.1最优化原理（最优子结构性质） 69 5.2无后向性 70 5.3子问题的重叠性 70 六、动态规划的基本思想 71 七、动态规划算法的基本步骤 72 八、动态规划的实例分析 73 例1 生产计划问题 73 例2 Bitonic旅行路线问题 74 例3计算矩阵连乘积 75 第五章 组合数学简介 80 一、概述 80 二、解组合数学题目的一些方法 81 三、PÓLYA原理及其应用 86 第六章 专题解析 93 一、模 拟 93 1. 模拟游戏类 93 2. 模拟编码类 97 二、密 码 102 1. Problem A 102 2. Problem B 106 3. Problem C 109 三、字符串处理 113 1. PROBLEM A 113 2. PROBLEM B 114 3. 字符串处理的应用实例 115 四、算法的优化 121 （一）算法优化的基本思想 121 （二）搜索的优化 125 （三）动态规划的优化 129 （四）一些特殊的数据结构 134 附录 课程实验 141 实验一 STL的熟悉与使用 141 实验二 搜索算法的实现 142 实验三 计算几何算法的实现 142 实验四 动态规划算法的实现 143 实验五 模拟/密码类问题的建模与实现 144 实验六 字符串/组合数学类问题的建模与实现 145 实验七 ICPC设计实验 146 |
查看评论
已有0位网友发表了看法