基础算法艺术

零基础选手参加算法竞赛的必读书

重点介绍各种基础算法，如分治算法、贪心算法、枚举算法、动态规划算法等。注重培养学生用“多向思考”“一题多解”和“一题多变”的方式解决问题。一书在手、尽在掌握。

张新华，毕业于浙江大学计算机与科学专业，信息学奥赛金牌教练。从教十年间，培养的学生多次获得全国青少年信息学奥林匹克竞赛一等奖，以及太平洋地区信息学奥林匹克竞赛金奖，其中绝大多数被清华大学、北京航空航天大学、中国科技大学、浙江大学、上海交通大学等重点大学提前录取。

目录 第一章分治算法 折半查找法 递归二分算法★ 非递归二分法★ 拓展与练习 魔法石的诱惑 分治算法★ 数学方法★ 拓展与练习 逃亡 分治算法★ 数学方法1★★ 数学方法2★★ 拓展与练习 快速幂运算 基本快速幂算法★ 位优化快速幂算法★ 拓展与练习 运动会 循环比赛★ 残缺棋盘★ 解一元三次方程 枚举法★ 二分法★ 拓展与练习 数的查找 第k小数1★ 第k小数2★ 第k小数3★ 拓展与练习 剔除多余括号 二分法★★ 非二分法★ 聪明的质检员 二分法+前序和★★ 拓展与练习 最接近点对问题 一维算法★★ 二维算法★★ 拓展与练习 第二章递归算法 棋子移动 递归算法★ 拓展与练习 地盘划分 朴素递归算法★ 优化递归算法★ 拆分自然数 递归算法★ 回溯算法★ 分形图 分形图1★★ 分形图2★★ 拓展与练习 N皇后问题 递归算法1★ 递归算法2★ 递归算法3★★ 递归算法4★ 回溯算法★ 位运算法★★★ 拓展与练习 求子集 递归算法★ 位运算法★ 数字三角形 递归算法★ 记忆化搜索优化算法★ 深度优先搜索算法★ 位运算法★ 回溯算法★ 动态规划算法★ 滚动数组优化算法★ 非完美算法★ 拓展与练习 油桶问题 穷举法★ 递归算法★ 动态规划算法1★ 动态规划算法2★ 拓展与练习 传球游戏 递归搜索法★ 穷举法★ 递推算法★ 第三章排列组合问题 全排列问题 非字典序递归算法★ 深搜字典序★ 位运算法★★ STL模板法★ 火星人问题★ 拓展与练习 组合问题 组合公式法★ 递推法★ 递归算法★ 位运算法★★ Jam的计数法★ 拓展与练习 乘法游戏 全排列法★★ 区间动态规划法★★ 邮票面值问题 排列组合法★★ DFS+动规★★ 第四章高精度算法 被限制的加法★ 简单高精度加法★ 简单高精度减法★ 简单高精度乘法★★ 高精度幂 普通快速幂算法★★ 指针交换地址优化算法★★ 高精度分数 朴素算法★ 优化算法★★ 高精度阶乘 非递归式算法★★ 朴素高精度算法★ 优化算法1★ 优化算法2★ 优化算法3★★ 高精度数除以低精度数1 ★ 高精度数除以低精度数2★ 普通高精度数除以高精度数 普通算法★★★ 改进算法★★★ 万进制高精度加法★ 万进制高精度减法★ 万进制高精度乘法★★ 万进制高精度除法★★★ 组合数的高精度算法 算法1★ 算法2★ 算法3★★ 算法4★★★ 第五章排序算法 一次查找两元素★ 常用排序法 直接插入排序法★ 选择排序法★ 朴素快速排序法★ 随机化快速排序法★ 简单计数排序法★ 稳定计数排序法★ 基数排序法★ 希尔排序法★ 归并排序法★ 各种排序算法的比较 紧急集合★ 求逆序对数 归并排序求逆序对数★ 树状数组求逆序对数★★★ 拓展与练习 第六章穷举算法 火柴棒等式 穷举法★ 拓展与练习 加急密文★ 翻转棋盘 枚举+DFS★ 枚举+BFS+位运算★★ 拓展与练习 排队 穷举法★ 动态规划法★★ 选择客栈 朴素算法★ 优化算法1★ 优化算法2★ 时钟问题 普通枚举法★ 优化枚举法★★ 位运算法★★ 拓展与练习 快算24点 回溯算法★★ 全排列+枚举算法★★ 检测方法 推理练习 侦探推理★★★ 拓展与练习 第七章贪心算法 删数问题★ 数列极差问题★ 不相交区间问题 电视节目安排★ 拓展与练习 区间选点问题 监测点★ 雷达问题★★ 广告问题★★ 区间覆盖问题 时空定位1★ 时空定位2★ 平均分配问题 均分纸牌★★ 作业调度问题 流水作业调度问题★ 赶作业★ 钓鱼★★ 田忌赛马★★ 普通贪心法 动态规划法 贪心+动规法 拓展与练习 第八章递推算法 过河卒★ 数的计数 递推算法★ 递归算法★ 动态规划算法★ 储油点★ 挖地雷★ 偶数3的个数★ 布阵 方法一★ 方法二★ 方法三★ 方法四★ 极值问题★★ 区域划分问题★ 军事情报★ 密文传送★★ 汉诺塔问题 标准汉诺塔问题★ 双塔问题★ 四塔问题★★ M塔问题★★ 妖兽特攻队★★ 平面分割问题 凸多边形的三角形剖分★★ 拓展与练习 实数数列 算法1★★★ 算法2★★★ 第九章搜索算法 四色地图★ 迷宫问题 宽度优先搜索★ 宽度优先搜索STL版★ 深度优先搜索★ 深度优先搜索递归法★ 骑士遍历问题 骑士遍历初级版★ 骑士遍历普通版★ 骑士遍历优化版★★★ 拓展与练习 八数码问题 康托展开★ 康托展开逆运算★ 哈希函数★ 宽搜算法★ 双向宽度优先搜索★★ 双向宽度搜索+康托展开★★ A*算法★★★ IDA*算法★★ 拓展与练习 魔板问题 宽搜算法★★ 虫食算★★ 数独游戏★★ 拓展与练习 第十章模拟算法 猫和老鼠★ 奶牛的命运★★ 世纪梭哈★★ 小球钟★★ 第十一章动态规划 最长不下降子序列 机器人军团★ 抄近路★ 魔法石矿★ 拦截导弹★★ 楼兰宝藏★★ 和谐俱乐部★★ 滑雪★★ 拓展与练习 简单背包问题 枚举算法★ 递归算法★ 0/1背包问题 动态规划算法★ 拓展与练习 货币问题 货币系统问题★ 拓展与练习 数字分组问题 数字分组1★ 数字分组2★ 完全背包问题 完全背包问题★ 完全背包算法的优化★ 0/1背包算法的优化★ 拓展与练习 多重背包问题 多重背包★ 太空梯★ 拓展与练习 混合背包问题 忙碌★★ 拓展与练习 理想收入问题 朴素动态规划★ 优化算法1★ 优化算法2★ 优化算法3★ 优化算法4★ 优化算法5★ 优化算法6★ 优化算法7★ 优化算法8★ 贪心算法★ 数的划分 枚举算法★ 递归算法★ 动规算法1★ 动规算法2★ 动规算法3★ 楼梯问题 动规算法1★ 动规算法2★ 动规算法3★ 动规算法4★ 动规算法5★ 动规算法6★ 母函数算法★★ 拓展与练习 合并问题 合并魔法石1★ 合并魔法石2★★ 多边形魔法阵★★ 能量项链★★ 路径问题 最短路径★ 最小交通费用问题★ 放置问题 书架问题1★ 书架问题2★ 安排车厢 ★ 唱片录制★ 双色马★ 拓展与练习 数字游戏 乘积最大★ 添加号问题★ 加减人生★ 模拟人生★ 矩阵连乘★ 拓展与练习 相遇问题 动规算法1★ 递归算法★ 宽度搜索算法★ 动规优化1★ 动规优化2★ 动规优化3★ 动规优化4★★ 动规优化5★★ 拓展与练习 最大连续子序列问题 最大连续子序列和★ 最大连续子序列积★★ k个最大连续子序列和★ 子矩阵问题 二维最大子矩阵问题★★ 扩展最大子矩阵问题★★ 子矩阵变形问题★★ 子串问题 最长前缀★ zipper★ 最长公共子串问题★★ 确定基因功能★★ 拓展与练习 最长公共上升子序列 优化算法1★ 优化算法2★ 购物问题 购物问题★ 收购魔法石★ 商店购物★ 资源分配问题 机器分配★ 系统可靠性★ 邮局问题★ 快餐问题★ 切割能量棒★ 调度问题★ 分割问题 凸多边形三角划分★★ 凸多边形分割★★ 拓展与练习 双重动规 城市交通★★ 复杂的审批★★ 拓展与练习 多进程动规 方格取数★★ 3取方格数★★ 拓展与练习 状态压缩动态规划 猛兽军团1★★ 猛兽军团2★★ 炮兵阵地★★ 清扫计划★★ 拓展与练习 树型动态规划 加分二叉树★★ 宝藏★★ 选课★★★ 鸿门宴★★★ 拓展与练习 附录AC++语言使用参考 类和对象 类的继承 函数重载 操作符重载 显式类型转换 异常处理 名字空间 友员函数 内联函数 静态成员 附录B标准模板库使用参考 vector向量容器 deque双端队列容器 list双向链表容器 set集合容器 multiset多重集合容器 map映照容器 multimap多重映照容器 stack堆栈容器 queue队列容器 priority_queue优先队列容器 adjacent_find查找相邻元素 find_first_of查找第一个匹配字符 count统计个数 堆排序 sort排序算法 归并算法merge inplace_merge内部归并 stable_sort稳定排序 lower_bound下确界 upper_bound上确界 折半搜索binary_search Includes判断集合包含关系 集合操作 最值 产生组合数 ⅩⅦ 附录C常用在线评测网站 参考文献

前言 为什么编写这套书？ 随着计算机逐步深入人类生活的各个方面，利用计算机及其程序设计来分析、解决问题的算法在计算机科学乃至于整个科学界的作用日益明显。相应地，各类以算法为主的程序设计竞赛也层出不穷： 在国内，有全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces，简称NOIP)，该联赛与全国中学生生物学联赛、全国中学生物理竞赛、全国高中数学联赛、全国高中学生化学竞赛，并称为国内影响力最大的“五大奥赛”； 在国际，有中学生的国际信息学奥林匹克竞赛(International Olympiad in Informatics，简称IOI)、面向亚太地区在校中学生的信息学科竞赛(即亚洲与太平洋地区信息学奥林匹克,AsiaPacific Informatics Olympiad，简称APIO)和面向大学生的国际大学生程序设计竞赛(ACM International Collegiate Programming Contest，简称ACM/ICPC)等。 各类算法竞赛要求参赛选手不仅必须具有深厚的计算机算法功底、快速、准确的编程能力以及创造性的思维，而且还必须具备团队合作精神和抗压工作的能力，因此算法竞赛在高校、IT公司和其他社会各界中获得越来越多的认同和重视。算法竞赛的优胜者，更是微软、Google、百度、Facebook等全球著名IT公司争相高薪招募的对象。因此，不仅是各类参加算法竞赛的选手，即使是不参加此类竞赛的很多研究工作者和从事IT行业的人士，都希望能获得这方面的专业训练并从中得到一定的收获。 但是，长期以来，算法竞赛的内容以其高难度、高要求而困住了许多有志于参加算法竞赛的爱好者的求索脚步。部分已出版的同类书籍或艰深难懂、或教条灌输，使不少爱好者望而却步，半途而废，以至于研究算法成了一种“曲高和寡”的学问，严重制约了算法竞赛优秀人才的培养。 殊不知，书上多数看似复杂难懂的知识或内容，其实总是可以找到一种深入浅出、化难为易的表述方法，使读者能看得懂、学得透，并最终达到触类旁通、举一反三的学习目标。因此本套丛书的写作初衷，是试图将看似晦涩难懂的算法表述得轻松、活泼、易懂。同时也是为了弥补国内算法竞赛以及普及读物方面的不足。 希望本套书的出版，能够给那些学有余力的中学生、计算机专业的大学生、程序算法爱好者以及IT从业者提供一个学习计算机科学的机会。 为什么要学习算法？ 经常有人说： 我不学算法也照样可以编程写软件。那么，为什么还要学习算法呢？ 首先，算法(algorithm)一词源于算术(algorism)，具体地说，算术方法是一个由已知推求未知的运算过程。后来，人们把它推广到一般，即把进行某一工作的方法和步骤称为算法。一个程序要完成一个任务，其背后肯定要涉及算法的实现，算法的优劣，直接决定了程序的优劣，因此，算法是程序的灵魂。学好了算法，就能够设计出更加有效的软件，以最为有效的方式完成复杂的功能。例如设计完成一个具有较强人工智能的人机对弈棋类游戏，程序员没有深厚的算法功底是根本不可能实现的。 其次，算法是对事物本质的数学抽象，是初等数学、高等数学、线性代数、计算几何、离散数学、概率论、数理统计和计算方法等知识的具体运用。真正学懂计算机的人(不只是“编程匠”)都对数学有相当的造诣，既能用科学家的严谨思维来求证，也能用工程师的务实手段来解决问题——而这种思维和手段的最佳演绎就是“算法”。学习算法，能锻炼我们的思维，使思维变得更清晰、更有逻辑，变得更有深度和广度。学习算法更是培养逻辑推理能力的非常好的载体之一。因此，学会算法思想，其意义不仅仅在算法本身，更重要的是，对日后的学习生活和思维方式也会产生深远的影响。 最后，学习算法本身很有意思、很有趣味。所谓“技术做到极致就是艺术”，当一个人真的沉浸到算法研究里时，他会感受到一个个精妙绝伦的算法的艺术之美，他会为它的惊人的运行速度和巧夺天工的构思而深深震撼，并从中体会到一种不可言喻的美感和愉悦。当然，算法的那份优雅与精巧虽然吸引人，却也令很多人望而生畏。事实证明，对很多人来说，学习算法是一件很痛苦的事情。 本套书的特色 本套书的第一个特点是具备一定理解能力的读者可以凭自学看懂书中的多数内容。由于地区的不平衡性等原因，很多算法竞赛选手及算法爱好者面对的一个最大难题是没有合适的教材以及找不到合适的导师给予引导。考虑到这种情况，本书作者尽可能地对书中每一个可能的难点和重点都进行了不厌其烦、深入仔细的讲解，此外，书中的绝大多数题目均附有带注释的完整源代码及测试数据供读者参考和检测。当然，不管怎样，你永远也不要指望阅读一本算法书能像阅读一本通俗小说那般轻松惬意。 本套书的第二个特点摒弃了一些算法书过于“学究气”，片面强调学术性、严谨性而忽略了可读性的“四平八稳”的表述手法，代之以轻松、活泼、搞笑的故事情节和穿插以历史、文化、科技等要素的情境导入，读者不仅在学习过程中获得编程的乐趣，还能够跟随书中的众多人物，一同经历一场奇妙的冒险之旅。本书作者热切希望读者不仅最终能够在计算机科学的领域大展宏图，更能够在故事中获得感悟，对社会、人生、理想、价值和信念等有更深刻的思考和认识。 本套书的第三个特点是绝大多数题目均采用了“多向思考”、“一题多解”和“一题多变”的解决方法，其目的主要有三点： 一是为了充分调动读者思维的积极性，提高综合运用已学知识解答问题的技能技巧； 二是为了锻炼读者思维的灵活性，促进知识和智慧的增长； 三是训练思维深度和广度，引导读者灵活地掌握知识的纵横联系，培养和发挥读者的创造性。所以，这种训练，决不能简单地看作是编程技巧的花哨卖弄，而是通过这种训练，培养读者思维的敏捷性，促进读者智力和思维的发展，提高读者的变通能力与综合运用所学知识的能力。读者若能坚持这种思维训练方法，必能起到意想不到的良好学习效果。 本套书内容简介 本套书的第一部——《语言及算法入门》，主要介绍在算法竞赛中需要用到的C++语言的语法知识及一些简单算法的运用。但与一般C++语言入门书不同的是，本部书在介绍C++语言的同时，更加侧重于数学思维的培养和简单算法的应用，因此其学习难度远高于一般市面上的C++语言入门书。书中很多表面看上去似乎非常简单的题目，由于采取了“一题多解”及“数学求解”等方法，其程序复杂度直线上升。因此这就要求读者具备一定的数学功底和思维能力，并且需要花费相当长的时间去思考和练习，才可能深刻理解题目的本质和内涵。此外，为了防止初学者原封不动地照抄源代码而不理解代码真实含义的“恶习”，书中凡可写可不写源代码的地方，一律采用伪代码形式表述，当然，在出版社网站上，读者可以下载到书中所有的源代码及测试数据等资源。 本套书的第二部——《基础算法艺术》，重点介绍了各种基础算法，如分治算法、贪心算法、枚举算法、动态规划算法等。书中的绝大多数题目都采用了“多向思考”、“一题多解”和“一题多变”的方式来解决。读者不仅可以通过出版社网站下载的简单测试数据验证所写程序的正确性，还可以根据书中标注的题目原始出处，访问相关的在线评测网站提交所写代码进行测试。需要注意的是，与多数教材从头读到尾的习惯不同的是，本书的各章节划分并不是严格按从难到易、从简到繁的顺序编排，各章节基本都可以独立阅读，互不影响。读者在阅读过程中，有时可根据需要翻到其他章节学习完相关内容后再返回本章节继续学习。此外，每一道题的各种算法按难易程度粗略地以★号表示，★号越多，表示难度越大，读者若遇到难度过大的题，不必硬“啃”，完全可以在学习完其他章节的相关内容后再来学习。 本套书的第三部——《基础数据结构》，详细介绍了链表、堆栈、队列、树、图等基础数据结构的相关知识。为了便于读者的理解，本书对数据结构众多知识点进行了详细的解释和分析，随书还配有难易适中的练习题。本书中的多数题目未配置相应测试数据，读者编写的代码正确与否，需要去相关的在线评测网站提交代码进行测试。这样做是培养读者善于应用无限网络资源的能力，使读者能逐渐脱离书本的束缚，最终达到独立、自主学习的目的。 全套书中以调侃化的形式出现的公司和人名等，均为故事情节而服务，与现实无更多的关联。 适合阅读本书的读者 本套书可作为全国青少年信息学奥林匹克联赛(NOIP)系列的复赛教材及ACM国际大学生程序设计竞赛(ACM/ICPC)的参考和学习用书，还可作为计算机系学生、IT工程师、科研人员、算法爱好者的参考和学习用书。 致谢 感谢原乌鲁木齐高级中学(前身为乌鲁木齐市第六中学)的李念、刘悠然、朱生龙、陆智、李智杰、刘毅东、吕亚伟、徐兆鹏、戴文轩、杜同心、胡亚欣、徐菲鹏、戴维、张欢、郑斐、彭胡杰、肖阳等同学； 感谢浙江省瑞安中学钱瑞源、潘伟达、张元煌、周望威、林展、杨丰、张颖洁、卢众意、沈小洲、肖煜伟、郑立言、金泽豪、章奎亮、蔡子豪、陈云帆、方佳豪、陈士俊、李心怡、孙一言、蔡凡、黄海同、王络、肖瑞宇、潘洲阳、陈可、张夏悦、陈振哲、林江浩、魏书扬等同学，他们在我的指导下，用简洁易懂的程序代码实现了本书的部分算法。 感谢全国各省市中学、大学的信息学奥赛指导师们，他们给本套书提了许多真诚而有益的建议，并对本人在写书过程中遇到的一些困惑和问题给予了热心的解答。 感谢浙江省瑞安中学为本人搭建的学习、研究、竞赛的平台以及对本人工作的大力支持。 本套书在完成过程中，使用了NOIP的部分原题、在线评测网站的部分题目，并参考和收集了其他创作者发表在互联网、杂志等媒体上的相关资料，无法一一列举，在此一并表示衷心感谢。 最后，感谢我的女儿，你是我完成这套书的动力，因为这套书专为你而写。 最后要说的话 本套书花费了本人巨大的精力和时间，这些年来的多数闲暇时间，都用在了这套书的编写和反复校验上。但尽管如此，由于时间和水平所限，书中难免存在不妥和错误之处，欢迎同人或读者赐正，如果在阅读中发现任何问题，请发送电子邮件到hiapollo@sohu．com告诉本人，更希望读者对本书提出建设性意见，以便修订再版时改进。 针对本套书的题库网站正在不断完善中，网址为： www．razxhoi．com。 张新华 2014年8月于浙江瑞安