首页 > 科技 > 计算机 > 编程语言

算法竞赛实战笔记

作译者：梁博等

出版时间：2024-01 千字数：341 版次：01-01 页数：244

开本：16开装帧： I S B N ：9787121470127

换版：

纸质书定价：￥78.0

库存:无

分享到：

共有图书评论0条【查看评论摘要】

看了又看

{{data.bookName}}

￥{{data.price}}

内容简介

前言

上架建议

作者简介

编辑推荐

音视频专区

第 0 章 一些不那么常识的常识 ············································································.1 
0.1 本地编程环境的配置··············································································.1 
0.1.1 在 Windows 系统上安装使用 Dev C++···············································.1 
0.1.2 在 MacOS 系统上安装 Xcode ··························································.4 
0.2 在线评测系统—洛谷···········································································.7 
0.2.1 注册洛谷 ···················································································.8 
0.2.2 提交题目 ···················································································.9 
0.2.3 团队管理 ···················································································11 
第 1 章 线性数据结构 ························································································15 
1.1 数据结构·····························································································15 
1.1.1 数据结构的定义 ··········································································15 
1.1.2 数据结构的运算 ··········································································17 
1.1.3 线性数据结构 ·············································································17 
1.2 栈······································································································18 
1.2.1 栈的定义 ···················································································18 
1.2.2 栈的作用 ···················································································20 
1.2.3 栈的固定数组实现 ·······································································21 
1.2.4 STL 中的栈 ················································································24 
1.2.5 括号匹配问题 ·············································································26 
1.2.6 前缀、中缀、后缀表达式 ······························································30 
1.2.7 后缀表达式的计算 ·······································································32 
1.2.8 中缀表达式转换为后缀表达式 ························································36 
1.2.9 中缀表达式的计算 ·······································································41 
1.3 队列···································································································43 
1.3.1 队列的定义 ················································································44 
1.3.2 队列的作用 ················································································46 
1.3.3 队列的固定数组实现 ····································································46 
1.3.4 STL 中的队列 ·············································································47 
1.3.5 基数排序（Radix Sorting）·····························································50 
1.3.6 结构体的构造函数 ·······································································56 
1.3.7 队列的应用 ················································································59
1.4 前缀和·······························································································.66 
1.4.1 前缀和的引入 ············································································.66 
1.4.2 一维数组前缀和 ·········································································.66 
1.5 动态数组····························································································.75 
1.5.1 动态数组 vector ··········································································.75 
1.5.2 STL 中的动态数组 ······································································.75 
1.5.3 vector 的缺点 ·············································································.76 
1.5.4 vector 与迭代器 iterator·································································.76 
1.5.5 vector 与 C++11 ··········································································.78 
1.5.6 vector 的实现原理 ·······································································.80 
1.6 树·····································································································.82 
1.6.1 树的相关概念 ············································································.82 
1.6.2 树的性质 ··················································································.84 
1.6.3 特殊的树—二叉树 ···································································.84 
1.6.4 完全二叉树的性质 ······································································.85 
1.6.5 树的存储方式 ············································································.86 
1.6.6 树的遍历 ··················································································.89 
1.6.7 知二求一 ··················································································101 
1.6.8 树的宽度优先遍历 ······································································105 
1.7 本章习题····························································································105 
第 2 章 基础算法 ·····························································································106 
2.1 贪心算法····························································································106 
2.1.1 贪心算法的概念 ·········································································106 
2.1.2 基础贪心问题举例 ······································································107 
2.1.3 线段覆盖问题 ············································································111 
2.2 高精度计算·························································································113 
2.2.1 C++语言中的数据类型·································································113 
2.2.2 高精度加法 ···············································································115 
2.2.3 高精度减法 ···············································································118 
2.2.4 高精度乘法 ···············································································121 
2.2.5 高精度除法取余数 ······································································126 
2.3 归并排序····························································································129 
2.3.1 归并 ························································································130 
2.3.2 归并排序的时间复杂度分析 ··························································134 
2.3.3 归并排序的应用 ·········································································135
2.4 快速排序··························································································.143 
2.4.1 快速排序的思想················································································.143 
2.4.2 快速排序的时间复杂度分析 ························································.146 
2.5 STL ································································································.151 
2.5.1 algorithm 头文件中的函数 ···························································.152 
2.5.2 容器 ······················································································.156 
2.6 本章习题··························································································.159 
第 3 章 搜索算法 ···························································································.160 
3.1 深度优先搜索····················································································.160 
3.1.1 迷宫寻路与烤鸡问题 ·································································.160 
3.1.2 全排列问题与回溯 ····································································.166 
3.1.3 洪水填充（Flood Fill）算法·························································.168 
3.1.4 八皇后问题与剪枝 ····································································.171 
3.1.5 数独问题 ················································································.174 
3.1.6 剪枝 ······················································································.177 
3.2 宽度优先搜索····················································································.181 
3.2.1 找眼镜 ···················································································.181 
3.2.2 马的遍历 ················································································.182 
3.2.3 01 迷宫···················································································.185 
3.2.4 八数码问题 ·············································································.188 
3.3 本章习题··························································································.190 
第 4 章 动态规划 ···························································································.191 
4.1 动态规划入门····················································································.191 
4.1.1 斐波那契数列 ··········································································.191 
4.1.2 数字三角形 ·············································································.193 
4.1.3 递推+填表···············································································.195 
4.2 动态规划解题步骤··············································································.199 
4.2.1 分解子问题 ·············································································.199 
4.2.2 确定状态 ················································································.200 
4.2.3 状态转移 ················································································.200 
4.2.4 动态规划能解决的问题的特点 ·····················································.201 
4.3 线性动态规划····················································································.201 
4.3.1 最长上升子序列问题（LIS）·······················································.201 
4.3.2 最长公共子序列问题（LCS）······················································.209 
4.4 背包类动态规划·················································································.213
4.4.1 01 背包问题···············································································213 
4.4.2 多重背包问题 ············································································225 
4.4.3 完全背包问题 ············································································228 
4.4.4 分组背包问题 ············································································231 
4.4.5 二维费用背包问题 ······································································241 
4.5 区间动态规划与多维动态规划·············································································243 
4.5.1 区间动态规划 ············································································243 
4.5.2 多维动态规划 ············································································248 
4.6 本章习题····························································································256

亲爱的读者，我十分荣幸地把本书献给你。你可能是准备踏入算法竞赛大门的学生，也可能是久经考验的赛场高手，或者是多年工作在一线的工程师。虽然我不认识你，但是我知道你一定对算法竞赛充满热情和憧憬。
是的，热情。我在小学五年级的时候第一次接触编程。那时候凭一本很薄的VB 语言编程手册开始自学，是热情让我独立“啃下”深奥的教材，并且尝试写小游戏给全班同学玩。上了中学以后，在教练老师的指导下，我开始系统地学习算法，也是热情让我放弃假期和周末，预习大学计算机专业的课程，天天在机房里面刷题、研究算法。面对有几千道题的题库，只有热情才能让我支撑下来。
但是，只有热情是不够的。学习不是闭门造车，学习资源是否充足，对于竞赛准备来说十分重要。我很荣幸能在且有丰富资源的顶尖中学里学习。当时国内算法竞赛刚刚起步，我的教练孔维玲老师和王晓光老师去国外的网站搜集学习资料，翻译成中文，用 U 盘复制给我们。我很深刻地记得，孔老师还打印了一张 A4纸塞给我，上面密密麻麻地写满了 50 道动态规划算法的题目。这张纸对我来说就是“武林秘籍”，50 道题让我学会了动态规划算法。老师们还请已经保送清华的学长回来分享学习经验，给我们讲一些“黑科技”的新算法。这些对我的成长都至关重要。
现在，虽然网络非常便捷，但是学习资源依旧被强校垄断。竞赛中成绩斐然的中学和大学，有非常厉害的教练老师，有传承多年的题库资源，还有已经毕业的学长、学姐回来分享经验。而对于没有资源的初学者，入门难于登天。竞赛算法体系巨大，知识点之间相互依赖、错综复杂，按照什么顺序学习？各种在线评测网站上的题目动辄上千条，怎么做题训练？每道题目是考查什么算法？对于我想学习的算法如何找对应的练习题？而且，算法的知识梳理和题目的题解往往都源于热心同学的博客，有的语焉不详，有的只能针对特定问题，有的甚至还埋藏一些错误。对于初学者来说，难点不一定是找不到资料，而是找到好几份互相矛盾、写法不同的资料，不知道哪一份才是对的，也不知道正确的学习路线。
本书的初衷，就是不辜负每个读者的热情。我与李睿琦、娄兰两位老师根据北京大学附属中学和北京师范大学第二附属中学多年的竞赛授课经验，总结出合适的学习路线，并且配套例题和习题集，让读者能身临其境地感受强校训练的氛围。另外，我们不想故作高深，这本书语言力图做到通俗易懂，并且用 100 余张插图辅助读者理解算法。希望能够营造出与读者聊天的氛围，一步一步地分析问题。也希望读者在阅读的时候，跟着思考，并且不时地停下来看看自己能否想到下一步。自己想明白一道题，激动到像阿基米德一样喊出一句“尤里卡！”的时候，你会获得发自内心的成就感。
算法竞赛和体育竞赛一样，重要的是“训练”而不是“学习”。只看一遍，不实际把程序写出来，是不能真正学会一个算法的。在之前很多介绍算法的著作上，都没有对应的在线做题环境，或者使用国外的、小众的在线评测网站，不方便提交。目前，算法竞赛领域最著名的在线评测网站之一就是洛谷，在本书成书之际，洛谷的总用户数刚刚突破 100 万人。非常感谢洛谷平台对本书的支持，书中所有例题和习题都可以直接在洛谷上提交评测。希望读者把每一道题都自己做一遍，同时通过评测进行验证，确保真正学会。
关于阅读本书的门槛，读者只需要具备一些基本的 C++语言编程知识和能力即可。一些略微复杂的语法知识，比如，结构体的构造函数和动态数组的用法，本书会展开介绍。不用有任何心理负担，跟我们一起出发吧！当然，由于我们面向刚刚起步的算法竞赛爱好者，所以一些概念我们不会给出非常严格的定义和描述。如果有兴趣，可以以本书为路标，继续探索更深入的知识。
由于篇幅有限，本书只选择了一部分在算法竞赛入门阶段最为重要的基础数据结构和基础算法进行介绍，力求做到对于基础算法的各种变形全面覆盖，比如，介绍了动态规划算法的分组背包、二维费用背包等在其他著作中不太常见的类型，以及高精度计算中不太常见的除法取余算法，希望把这些只在传统强校中口口相传的“秘术”展现出来，避免读者在学习这些重要的基础算法时只能“蜻蜓点水”，知其然不知其所以然。
本书经过接近三年的时间的修改与编辑，终于出版面世。非常感谢电子工业出版社的支持，感谢钱维扬编辑帮我不厌其烦地修改语言问题，打磨细节。除了编著者外，本书部分章节由中国人民大学附属中学吴习哲编写，插图由北京化工大学王帆同学、首都师范大学梁爽同学绘制。也感谢对本书编写工作提供帮助和提出宝贵意见的老师们：北京市十一学校信息学竞赛教练汪星明老师、北京一零一中学信息学竞赛教练董华星老师、清华大学附属中学教练徐岩老师、北京师范大学第二附属中学信息学竞赛教练王析多老师、北京大学附属中学信息学教练杜昊老师。本书内容源于多年教学实践和教师交流，感谢北京大学附属中学信息中心毛华均老师，首都师范大学附属中学杨森林老师等前辈给予的无私奉献和大力推动，促进了北京算法竞赛的发展。感谢东北师范大学附属中学教练王晓光老师、孔维玲老师启蒙我的算法竞赛之路。
虽然几经删改和审阅，但是由于编著者水平有限，难免有不足和疏漏之处。如有错误或者意见，欢迎与编著者探讨，联系方式：微信公众号“信息学奥赛梁老师”。
希望本书不辜负每一份热情！
梁 博

查看更多 > 图书评论

暂无评论

发表图书评论

评论标题：
评论内容：
验证码：: 看不清楚
点击刷新
: 您还没有登录，请登录后再评论。
点击“登录”

购买过本书的顾客还买过

{{data.bookName}}

￥{{data.price}}