算法竞赛入门经典

出版者:清华大学出版社

作者:刘汝佳

页数:225

出版时间:2009-11

价格:24.00元

isbn号码:9787302206088

具体描述

《算法竞赛入门经典》是一本算法竞赛的入门教材，把C/C++语言、算法和解题有机地结合在了一起，淡化理论，注重学习方法和实践技巧。全书内容分为11章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、基础题目选解、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法，覆盖了算法竞赛入门所需的主要知识点，并附有大量习题。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧。另外，书中包含的各种开发、测试和调试技巧也是在传统的语言、算法类书籍中难以见到的。

《算法竞赛入门经典》可作为全国青少年信息学奥林匹克联赛（NOIP）的复赛教材及ACM国际大学。

作者简介

刘汝佳，1982年12月生，高中毕业于重庆市外国语学校。

2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名，进入国家集训队，并因此保送到清华大学计算机科学与技术系。大一时获2001年ACM／ICPC国际大学生程序设计竞赛亚洲一上海赛区冠军和2002年世界总决赛银牌(世界第四)，2005年获学士学位，2008年获硕士学位。

学生时代曾为中国计算机学会NOI科学委员会学生委员，担任IOI2002-2008中国国家队教练，并为NOI系列比赛命题十余道。现为NOI竞赛委员会委员，并在NOI 25周年时获得中国计算机学会颁发的“特别贡献奖”。

2004年至今共为ACM／ICPC亚洲赛区命题二十余道，担任6次裁判和2次命题总监，并应邀参加IOI和ACM／lCPC相关国际研讨会，发表论文两篇。

2004年初作为第一作者出版专著《算法艺术与信息学竞赛》，2009年出版译著《编程挑战》。

多年来在全国二十余个城市进行中学生竞赛培训工作，为北京、上海、吉隆坡等地的著名高校授课与宣讲，并多次与TopCodet、百度和网易有道等知名企业合作举办比赛，让更多的IT人才获得展示自我的平台。

目录信息

第1部分 语言篇
第1章 程序设计入门 1
1.1 算术表达式 1
1.2 变量及其输入 3
1.3 顺序结构程序设计 6
1.4 分支结构程序设计 9
1.5 小结与习题 13
1.5.1 数据类型实验 13
1.5.2 scanf输入格式实验 13
1.5.3 printf语句输出实验 13
1.5.4 测测你的实践能力 14
1.5.5 小结 14
1.5.6 上机练习 15
第2章 循环结构程序设计 16
2.1 for循环 16
2.2 循环结构程序设计 19
2.3 文件操作 23
2.4 小结与习题 27
2.4.1 输出技巧 28
2.4.2 浮点数陷阱 28
2.4.3 64位整数 28
2.4.4 C++中的输入输出 29
2.4.5 小结 30
2.4.6 上机练习 31
第3章 数组和字符串 33
3.1 数组 33
3.2 字符数组 37
3.3 最长回文子串 41
3.4 小结与习题 45
3.4.1 必要的存储量 45
3.4.2 用ASCII编码表示字符 45
3.4.3 补码表示法 46
3.4.4 重新实现库函数 47
3.4.5 字符串处理的常见问题 47
3.4.6 关于输入输出 47
3.4.7 I/O的效率 47
3.4.8 小结 49
3.4.9 上机练习 50
第4章 函数和递归 51
4.1 数学函数 51
4.1.1 简单函数的编写 51
4.1.2 使用结构体的函数 52
4.1.3 应用举例 53
4.2 地址和指针 56
4.2.1 变量交换 56
4.2.2 调用栈 57
4.2.3 用指针实现变量交换 59
4.2.4 初学者易犯的错误 61
4.3 递归 62
4.3.1 递归定义 62
4.3.2 递归函数 63
4.3.3 C语言对递归的支持 64
4.3.4 段错误与栈溢出 66
4.4 本章小结 67
4.4.1 小问题集锦 67
4.4.2 小结 68
第2部分 算法篇
第5章 基础题目选解 69
5.1 字符串 69
5.1.1 WERTYU 69
5.1.2 TeX括号 70
5.1.3 周期串 71
5.2 高精度运算 71
5.2.1 小学生算术 72
5.2.2 阶乘的精确值 72
5.2.3 高精度运算类bign 73
5.2.4 重载bign的常用运算符 75
5.3 排序与检索 77
5.3.1 6174问题 77
5.3.2 字母重排 78
5.4 数学基础 81
5.4.1 Cantor的数表 81
5.4.2 因子和阶乘 82
5.4.3 果园里的树 84
5.4.4 多少块土地 86
5.5 训练参考 86
5.5.1 黑盒测试 86
5.5.2 在线评测系统 87
5.5.3 推荐题目 88
第6章 数据结构基础 89
6.1 栈和队列 89
6.1.1 卡片游戏 89
6.1.2 铁轨 91
6.2 链表 93
6.2.1 初步分析 93
6.2.2 链式结构 95
6.2.3 对比测试 96
6.2.4 随机数发生器 98
6.3 二叉树 99
6.3.1 小球下落 99
6.3.2 层次遍历 101
6.3.3 二叉树重建 105
6.4 图 106
6.4.1 黑白图像 107
6.4.2 走迷宫 108
6.4.3 拓扑排序 110
6.4.4 欧拉回路 111
6.5 训练参考 112
第7章 暴力求解法 114
7.1 简单枚举 114
7.1.1 除法 114
7.1.2 最大乘积 115
7.1.3 分数拆分 115
7.1.4 双基回文数 116
7.2 枚举排列 116
7.2.1 生成1～n的排列 116
7.2.2 生成可重集的排列 118
7.2.3 解答树 118
7.2.4 下一个排列 119
7.3 子集生成 120
7.3.1 增量构造法 120
7.3.2 位向量法 121
7.3.3 二进制法 122
7.4 回溯法 123
7.4.1 八皇后问题 123
7.4.2 素数环 126
7.4.3 困难的串 127
7.4.4 带宽 128
7.5 隐式图搜索 129
7.5.1 隐式树的遍历 129
7.5.2 一般隐式图的遍历 130
7.5.3 八数码问题 131
7.5.4 结点查找表 133
7.6 训练参考 136
第8章 高效算法设计 138
8.1 算法分析初步 138
8.1.1 渐进时间复杂度 138
8.1.2 上界分析 140
8.1.3 分治法 140
8.1.4 正确对待算法分析结果 142
8.2 再谈排序与检索 143
8.2.1 归并排序 143
8.2.2 快速排序 145
8.2.3 二分查找 145
8.3 递归与分治 148
8.3.1 棋盘覆盖问题 148
8.3.2 循环日程表问题 149
8.3.3 巨人与鬼 149
8.3.4 非线性方程求根 150
8.3.5 最大值最小化 151
8.4 贪心法 151
8.4.1 最优装载问题 151
8.4.2 部分背包问题 152
8.4.3 乘船问题 152
8.4.4 选择不相交区间 152
8.4.5 区间选点问题 153
8.4.6 区间覆盖问题 154
8.4.7 Huffman编码 154
8.5 训练参考 156
第3部分 竞赛篇
第9章 动态规划初步 158
9.1 数字三角形 158
9.1.1 问题描述与状态定义 158
9.1.2 记忆化搜索与递推 159
9.2 DAG上的动态规划 161
9.2.1 DAG模型 161
9.2.2 最长路及其字典序 162
9.2.3 固定终点的最长路和最短路 163
9.3 0-1背包问题 167
9.3.1 多阶段决策问题 167
9.3.2 规划方向 168
9.3.3 滚动数组 169
9.4 递归结构中的动态规划 170
9.4.1 表达式上的动态规划 170
9.4.2 凸多边形上的动态规划 171
9.4.3 树上的动态规划 171
9.5 集合上的动态规划 172
9.5.1 状态及其转移 173
9.5.2 隐含的阶段 173
9.6 训练参考 174
第10章 数学概念与方法 176
10.1 数论初步 176
10.1.1 除法表达式 176
10.1.2 无平方因子的数 178
10.1.3 直线上的点 179
10.1.4 同余与模算术 180
10.2 排列与组合 182
10.2.1 杨辉三角与二项式定理 182
10.2.2 数论中的计数问题 184
10.2.3 编码与解码 186
10.2.4 离散概率初步 187
10.3 递推关系 188
10.3.1 汉诺塔 188
10.3.2 Fibonacci数列 189
10.3.3 Catalan数 191
10.3.4 危险的组合 192
10.3.5 统计n-k特殊集的数目 193
10.4 训练参考 194
第11章 图论模型与算法 196
11.1 再谈树 196
11.1.1 无根树转有根树 196
11.1.2 表达式树 197
11.1.3 最小生成树 199
11.1.4 并查集 200
11.2 最短路问题 201
11.2.1 Dijkstra算法 202
11.2.2 稀疏图的邻接表 203
11.2.3 使用优先队列的Dijkstra算法 204
11.2.4 Bellman-Ford算法 205
11.2.5 Floyd算法 206
11.3 网络流初步 207
11.3.1 最大流问题 207
11.3.2 增广路算法 208
11.3.3 最小割最大流定理 210
11.3.4 最小费用最大流问题 211
11.4 进一步学习的参考 212
11.4.1 编程语言 213
11.4.2 数据结构 213
11.4.3 算法设计 213
11.4.4 数学 214
11.4.5 参赛指南 214
11.5 训练参考 215
附录A 开发环境与方法 216
A.1 命令行 216
A.1.1 文件系统 216
A.1.2 进程 217
A.1.3 程序的执行 217
A.1.4 重定向和管道 218
A.1.5 常见命令 218
A.2 操作系统脚本编程入门 219
A.2.1 Windows下的批处理 219
A.2.2 Linux下的Bash脚本 220
A.2.3 再谈随机数 221
A.3 编译器和调试器 221
A.3.1 gcc的安装和测试 221
A.3.2 常见编译选项 222
A.3.3 gdb简介 223
A.3.4 gdb的高级功能 224
A.4 浅谈IDE 225
· · · · · · (收起)

读后感

刘汝佳大神的名声很广（据说他曾经发现RP和请客时长有关系？哈哈）。不过鄙人孤陋寡闻，在OI数N次碰壁后才看了他的书，顿时张了张姿势。不过，我决定还是要转战CLRS的。 这本书写的很好，但是优缺点共有。下面先列一下优点： 1、简单易懂，可谓是初学者的福音。 2、算法程序写...  

想搞算法竞赛(比如你们最熟悉的OI或者ACM/ICPC)？如果你觉得你已经掌握了C语言，那么最好就从这本书开始竞赛之旅吧！ 这本书的优点有： 1 平易近人 如果你连这本书都不能看懂(如果你会C语言)，请你先思考自己是不是有认真在看(有没有思考啊，复习啊，做后面的练习啊……之类的)...  

想搞算法竞赛(比如你们最熟悉的OI或者ACM/ICPC)？如果你觉得你已经掌握了C语言，那么最好就从这本书开始竞赛之旅吧！ 这本书的优点有： 1 平易近人 如果你连这本书都不能看懂(如果你会C语言)，请你先思考自己是不是有认真在看(有没有思考啊，复习啊，做后面的练习啊……之类的)...  

ABC=A^2+B^2+C^2 ???? 应该是ABC=A^3+B^3+C^3 应该是引述错误吧。。。。。 感觉这本书比较容易，我要用一星期看完，算是熟悉熟悉c++吧，一个多月不碰了，是时候练点了，虽然这本书超级容易的说。。。  

ABC=A^2+B^2+C^2 ???? 应该是ABC=A^3+B^3+C^3 应该是引述错误吧。。。。。 感觉这本书比较容易，我要用一星期看完，算是熟悉熟悉c++吧，一个多月不碰了，是时候练点了，虽然这本书超级容易的说。。。  

用户评价

这本《算法竞赛入门经典》带给我的惊喜远不止于此。我一直认为，学习算法不仅仅是记忆几个公式或套路，更重要的是理解其背后的思想和思想的灵活运用。这本书在这方面做得非常出色。作者在讲解时，常常会穿插一些“题外话”，比如某个算法的提出背景，或者它在实际工程中的应用场景，这些看似不经意的细节，却能极大地激发我的学习兴趣，让我明白学习这些算法的意义所在。我记得在学习字符串匹配算法时，书中不仅讲解了KMP算法，还对比了它与朴素匹配算法的效率差异，并且用通俗易懂的比喻解释了next数组的构建原理。这种对比和类比，让我对算法的理解更加深刻，也更能体会到算法优化带来的巨大价值。而且，书中的题目设计也非常巧妙，往往是看似简单，实则蕴含着一些小技巧，需要我反复思考才能找到最佳解法。这种不断挑战自我、突破瓶颈的过程，让我收获了满满的成就感，也对未来的算法学习充满了信心。

这本书简直是为我量身定做的！我一直对算法竞赛充满热情，但总觉得基础不够扎实，遇到一些难题就束手无策。这次能读到《算法竞赛入门经典》，真的太幸运了。刚翻开目录，我就被深深吸引了，从基础的排序、查找，到更复杂的图论、动态规划，内容安排得循序渐进，一点也不枯燥。我尤其喜欢它在讲解每一个算法时，不仅给出了清晰的原理阐述，还附带了大量的例题和代码实现。我按照书中的步骤，一步步跟着敲代码，然后运行，再思考其中的逻辑，感觉自己真的在一点点进步。特别是学习到二分查找的时候，书中通过几个巧妙的例子，让我对这个看似简单的算法有了全新的认识，原来它在很多问题中都有着惊人的效率。还有后面的图论部分，将各种图的遍历、最短路径算法讲得透彻，虽然一开始有些概念比较抽象，但在作者的引导下，我逐渐掌握了其中的精髓。这本书不仅仅是知识的堆砌，更像是一位经验丰富的导师，在默默地指引着我前进的方向，让我不再迷茫。

读完《算法竞赛入门经典》，我最大的感受就是它的“实用性”和“指导性”。这本书不是那种只会讲理论的书，它更像是一本实战手册。作者在每一章的结尾都会给出一些精选的题目，这些题目涵盖了该章节所讲知识点的各种应用，而且难度适中，既不会打击初学者的积极性，又能有效地检验学习成果。我按照书中的建议，先是独立思考，实在做不出来再参考书中的提示和代码。这个过程让我体会到了“独立思考”的重要性，也让我学会了如何从题目中提取关键信息，如何将抽象的算法应用到具体的场景中。特别是后面关于数据结构的部分，比如链表、树、图的讲解，虽然内容很多，但通过图文并茂的解释，我很容易就理解了它们的结构和操作。这本书的价值在于，它不仅教会了我“是什么”，更教会了我“怎么做”，让我能够真正地将算法知识转化为解决问题的能力。

我之前接触过一些算法相关的书籍，但很多要么过于理论化，要么就是题目难度过高，让我望而却步。直到我遇到了《算法竞赛入门经典》，才真正体会到什么叫做“循序渐进”的学习过程。这本书的语言风格非常友好，作者仿佛就是一位耐心的老师，用最平实的语言解释最复杂的概念。我记得在学习栈和队列的时候，书中的插图非常生动形象，让我一下子就明白了它们的“后进先出”和“先进先出”的特性。而且，书中的代码风格也很规范，注释清晰，这对于我这个编程初学者来说，简直是福音。我跟着书中的代码，一点点地调试，理解每一行代码的作用，仿佛在跟着作者一起构建整个算法体系。这本书就像一座灯塔，照亮了我算法学习的道路，让我不再害怕那些看似遥不可及的难题，而是充满信心地迎接每一个挑战。

《算法竞赛入门经典》不仅仅是一本书，更像是算法竞赛领域的一本“秘籍”。它没有华丽的辞藻，没有故弄玄虚的概念，而是用最直接、最有效的方式，将算法竞赛的核心知识和技巧传授给读者。我尤其欣赏书中的“思维导图”式的讲解方式，作者总是能够将一个大的算法体系分解成若干个小的、易于理解的模块，然后逐个击破。这种结构化的学习方法，让我能够清晰地把握知识的全貌，而不至于陷入细节的泥潭。而且，书中的题目质量非常高，每一道题都经过精心设计，能够有效地考察我对算法的理解程度。我经常会在完成一个章节的学习后，尝试去做其中的习题，有时候一道题会卡住我很久，但当我最终找到解法时，那种豁然开朗的感觉是无与伦比的。这本书让我深刻体会到，算法竞赛的精髓在于“理解”和“应用”，而这本书正是帮助我达到这两个境界的绝佳工具。

好书啊，要是早点看到，没准我也去搞ACM了~

讲的挺好。。虽然太简单了

还是想看看，呵呵

结构欠佳

为了比赛,技巧书。