ACM程序设计竞赛基础教程

出版时间：2010-10  出版社：清华大学  作者：俞经善//王宇华//于金峰  页数：207  字数：337000  
Tag标签：无  

前言

从1970年开始，ACM／ICPC赛事就影响着计算机与信息专业的许多大学生，引导着他们应用计算机技术展示自己分析问题解决问题的才能。哈尔滨工程大学于2005年开始积极投身于ACM／ICPC活动中。时至今日，令我欣慰的是，从仅有的几名程序设计爱好者到如今上百人参与集训的规模，我们的校代表队已形成了一套自己的训练方法。在多年的磨炼中，我看到我们的队员走了一些弯路，也经历了一些波折。经过不断的尝试、努力，以及与其他高校参赛选手积极的交流，他们渐渐成长起来。今天，他们把自己的经验编辑成为一本系统的教材，既是对自己多年来训练学习的总结，也为了使更多的ACM／ICPC爱好者有“据”可依。

内容概要

　　《ACM程序设计竞赛基础教程》以循序渐进的方式对ACM程序设计竞赛中所涉及的基本题型和知识点进行了综合的介绍。全书共分9章，包括基础知识讲解、典型题目分析和算法设计，每道例题均给出完整的源程序作为参考。内容涵盖了基础算法、数据结构、字符串、搜索、图论、动态规划、组合数学和初等数论等。
　　《ACM程序设计竞赛基础教程》内容全面，针对性强，言简意赅，讲解透彻，通俗易懂，图例丰富，所有源代码均可进行评测。《ACM程序设计竞赛基础教程》作为ACM程序设计竞赛的培训教程，不仅为大学生们提供了竞赛入门的指导，而且对参赛学生拓展解题思路和提高训练水平也有很大的帮助。《ACM程序设计竞赛基础教程》也可供喜爱程序设计的学生以及从事算法设计的教师学习参考。

书籍目录

第1章 基础算法
1.1 分治
1.2 递归
1.3 枚举
1.4 贪心
第2章 排序、查找算法
2.1 基本排序算法
2.1.1 插入排序
2.1.2 冒泡排序
2.1.3 快速排序
2.1.4 其他排序
2.2 基本查找算法
2.2.1 顺序查找
2.2.2 折半查找
2.3 实例分析
2.4 小结
第3章 数据结构基础
3.1 常用数据结构简介
3.1.1 线段树简介
3.1.2 并查集简介
3.1.3 树状数组简介
3.2 实例分析
第4章 字符串
4.1 字符串匹配
4.1.1 朴素的字符串匹配算法
4.1.2 KMP算法
4.1.3 其他匹配算法
4.2 实例分析
4.3 小结
第5章 搜索算法
5.1 基本搜索算法
5.1.1 递归与迭代
5.1.2 深度优先搜索与广度优先搜索
5.1.3 回溯
5.2 搜索算法的一些优化
5.2.1 剪枝函数
5.2.2 双向广度搜索
5.3 实例分析
5.4 小结
第6章 图论算法
6.1 最短路径
6.1.1 Dijkstra算法
6.1.2 Floyd算法
6.1.3 Bellman-Ford算法
6.2 最小生成树
6.2.1 Kruskal算法
6.2.2 Prim算法
6.3 最大匹配--匈牙利算法
6.4 最优权匹配问题
6.4.1 理论基础
6.4.2 基本思想
6.4.3 样例代码
6.5 割点、割边以及连通分量
6.5.1 理论基础
6.5.2 求割点
6.5.3 求强连通分量
6.6 网络流
6.6.1 理论基础
6.6.2 最大流问题
6.6.3 最小费用最大流问题
6.7 实例分析
6.8 小结
第7章 动态规划算法
7.1 基本思想
7.2 基本概念
7.3 基本原理
7.3.1 最优化原理
7.3.2 无后效性
7.4 基本步骤
7.5 经典例子
7.6 实例分析
7.7 小结
第8章 计算几何基础
8.1 矢量
8.1.1 矢量的概念
8.1.2 矢量加减法
8.1.3 矢量叉积
8.1.4 矢量叉积的应用
8.2 包含关系
8.2.1 判断图形是否包含在矩形中
8.2.2 判断图形是否包含在多边形中
8.2.3 判断图形是否包含在圆中
8.3 凸包
8.3.1 凸包的概念
8.3.2 凸包的求法
8.4 实例分析
第9章 数论
9.1 基本数学算法
9.1.1 素数筛选
9.1.2 最大公约数
9.1.3 快速乘方
9.2 实例分析
附录A 综合训练题
A.1 LuckyBird
A.2 Josephusproblem
A.3 Counter Strike
A.4 Gauss Elimination
A.5 The Math Problem
A.6 Mobile phones
A.7 Japan
A.8 骨灰级玩家考证篇
A.9 括号匹配
A.10 食物链

章节摘录

插图：搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的结点的过程。所有的搜索算法从其最终的算法实现上来看，都可以划分成两个部分——控制结构和产生系统，而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。5.1 基本搜索算法5.1.1 递归与迭代递归程序设计是编程语言设计中的一种重要的设计方法，它使许多问题简单化，易于求解。递归的特点：函数或过程直接的或间接的调用它自己本身。所谓迭代，就是在程序中用同一个变量存放每一次推算出的值，每一次循环都执行同一语句，给同一变量赋以新值，即用一个新值代替旧值。5.1.2 深度优先搜索与广度优先搜索深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展结点选取上。由于其保留了所有的前驱结点，所以在产生后继结点时可以去掉一部分重复的结点，从而提高了搜索效率。

编辑推荐

《ACM程序设计竞赛基础教程》：教育部“高等学校教学质量与教学改革工程”立项项目

用户评论 (总计19条)

•   对编程算法有很深的指导作用
•   对于OIer很好上手，更适合没有程设基础的人。
•   真的非常不错，书很好物流也很给力
•   书收到了，物流四天。晚了一天，书还是不错的。
•   比较薄，代码完整。需要基础才行哦。
•   这本书精简概要，很适合初学者，对ACM感兴趣的大一的童鞋不可错过！！！
•   书倒是不错，对于初学者有点难度~
•   真心的不错的 还行 虽然比赛结果一般
•   适合新手阅读，书是全新的，还可以。
•   中规中矩的一本书，还没看完正在看。。。
•   书不错，而且比附近书店的便宜。挺好
•   书不错，不过没有一定基础的人自学有相当大的困难。我到现在都没入门！
•   内容编排还挺合理，但是很多代码还不如网友写的优化，可读性也不强
•   这书适合初学者读 我觉得挺好的
•   个人表示非常喜欢这本书，非常实用！！！！值得买
•   正版,快速...比较喜欢...
•   书不错，但不太适合初学者，还是要有一点功底
•   这书即不适合新手也不适合老手，讲的不清不楚。买了就会后悔。
•   给男友买的，他说质量很好，内容不错！