算法艺术与信息学竞赛.学习指导

《算法艺术与信息学竞赛.学习指导》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、前言本书是《算法艺术与信息学竞赛》的学习指导。所谓学习指导，是告诉读者学什么，如何学。算法包罗万象，很难在一本书中的篇幅覆盖很多内容的通知对每个知识点进行细致讲解，因此本书更多的是作为一本导引、工具书、手册或者学习大纲，给读者以宏观上的学习指导。和原书《算法艺术与信息学竞赛》相比，本书的特点有：²大量知识讲解。²更多循序渐进的习题。²重要算法的源代码。从知识结构上看，本书的覆盖面比原书更广，补充了原书没有涉及到在知识点，包括计算理论中的NP完全理论和图灵机的基本概念、数据结构中的伸展树、Treap，左偏树、二项堆、Fibonacci堆、数论中

2、的指数和原根、分解因数的快速算法、数值计算中的高斯消元法和FFT、组合游戏论初步、更多序列经典问题和线段树、后缀数组等数据结构的应用、树更多经典问题、多模式串匹配算法、后缀树构造的Ukkonen算法、后缀数组构造的Skew算法、更加详细的强连通分量/双连通分量算法、最大流和最小费用流算法、二分图和任意图的最大基数匹配算法和最大权匹配算法、稳定婚姻问题、线性规划在网络优化中的作用、向量代数基础、多边形剖分算法、平面剖分、半平面交、三维凸包、Voronoi图和直线排列的构造算法、几何对偶性的应用、Minkowski和与简单运动规划问题等。从题目上

3、看，本书的题目集中在习题部分，这样保证知识讲解部分相对完整和纯粹，也避免了用过多篇幅叙述和具体题目相关的内容。这些题目选择范围更广，难度搭配也更加合理，且包含了常见的小技巧，和原书那些巧妙但难以理解的题目比较起来更适合于初学者入门与提高，也为深入阅读原书打下了基础。刘汝佳周源周戈林2005年10月15日目录前言i插图目录iii表格目录iv第一章概述11.1认识计算机...................................11.1.1计算机的优势..............................11.1.2限制和解决方案

4、.............................41.2问题、算法及其分析..............................51.2.1问题实例................................51.2.2算法描述................................61.2.3算法分析................................81.2.4难解问题................................111.3问题求解与程序设计竞赛..................

5、.........121.3.1问题求解周期..............................121.3.2程序设计竞赛：问题求解实践.....................131.4C++语言介绍..................................151.4.1第一个C++程序............................161.4.2静态分析................................181.4.3动态分析................................201.4.

6、4编译器和IDE..............................211.4.5C++词法................................22目录iii1.4.6二进制和十六进制...........................231.4.7内存和变量...............................251.4.8变量的类型...............................261.4.9变量的声明和使用...........................291.4.10运算符和表达式..

7、...........................311.4.11函数...................................351.4.12控制流和程序结构...........................381.5数据结构基础..................................411.5.1逻辑结构：线性表、树和图......................411.5.2逻辑结构的物理实现..........................431.5.3外部特性和内部结构...............

8、...........471.5.4抽象数据类型..............................491.5.5时间复杂度................