图灵社区会员 feiifan([email protected]) 专享 尊重版权 图灵社区的电子书没有采用专有客户 端，您可以在任意设备上，用自己喜 欢的浏览器和PDF阅读器进行阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知和 觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能对 该用户实施包括但不限于关闭该帐号 等维权措施，并可能追究法律责任。 图灵社区会员 feiifan([email protected]) 专享 尊重版权 图灵社区会员 feiifan([email protected]) 专享 尊重版权 图灵社区会员 feiifan([email protected]) 专享 尊重版权 图书在版编目（CIP）数据 程序员的算法趣题 /（日）增井敏克著；绝云译 . -- 北京：人民邮电出版社，2017.7 （图灵程序设计丛书） ISBN 978-7-115-45923-7 Ⅰ. ①程… Ⅱ. ①增… ②绝… Ⅲ . ①程序设计 Ⅳ. ① TP311.1 中国版本图书馆 CIP 数据核字（2017）第130676 号 内 容 提 要 本书是一本解谜式的趣味算法书，从实际应用出发，通过趣味谜题的解谜过程， 引导读者在愉悦中提升思维能力、掌握算法精髓。此外，本书作者在谜题解答上，通 过算法的关键原理讲解，从思维细节入手，发掘启发性算法新解，并辅以 Ruby、 JavaScript 等不同语言编写的源代码示例，使读者在算法思维与编程实践的分合之 间，切实提高编程能力。 本书适合已经学习过排序、搜索等知名算法，并想要学习更多有趣算法以提升 编程技巧、拓展程序设计思路的程序员，以及对挑战算法问题感兴趣、爱好解谜的 程序员阅读。 ◆著 ［日］增井敏克 译 绝 云 责任编辑 杜晓静 执行编辑 高宇涵 侯秀娟 责任印制 彭志环 ◆ 人民邮电出版社出版发行 北京市丰台区成寿寺路11号 邮编 100164 电子邮件 [email protected] 网址 http://www.ptpress.com.cn 北京 印刷 ◆ 开本：880×1230 1/32 印张：9.75 字数：320 千字 2017 年 7 月第1 版 印数：1- 4 000 册 2017 年 7 月北京第1次印刷 著作权合同登记号 图字：01-2016-4462 号 定价：55.00 元 读者服务热线：(010)51095186 转 600 印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东工商广登字 20170147 号 图灵社区会员 feiifan([email protected]) 专享 尊重版权 版权声明 プログラマ脳を鍛える数学パズル （ProgrammerNou wo Kitaeru Sugaku Puzzle：4245-6） Copyright © 2015 by Toshikatsu Masui. Original Japanese edition published by SHOEISHA Co., Ltd. Simplified Chinese Character translation rights arranged with SHOEISHA Co., Ltd. through CREEK & RIVER Co., Ltd. and CREEK & RIVER SHANGHAI Co., Ltd. Simplified Chinese Character translation copyright © 2017 by Posts & Telecom Press. 本书中文简体字版由 SHOEISHA Co., Ltd. 授权人民邮电出版社 独家出版。未经出版者书面许可，不得以任何方式复制或抄袭本书 内容。 版权所有，侵权必究。 图灵社区会员 feiifan([email protected]) 专享 尊重版权 图灵社区会员 feiifan([email protected]) 专享 尊重版权 译者序 作为程序员，大家也许会有这样的“小洁癖”：特别不能忍受重复 劳动，特别讨厌“人肉运维”。因此，只要做某件事需要花 90 秒以上的 时间，那么就一定要通过写程序来完成这件事，哪怕写程序要花费半 个小时。乍一听，这似乎是在浪费时间，然而这正是大部分优秀程序 员的特质。一方面，如果是做重复的事情，计算机通常做得比人更快， 准确率也更高；另一方面，写成程序之后，这些重复的流程更易于变 更、管理和复用。事实上，正因为无数“有洁癖”的前辈们的伟大工 作，才有了编译器，才有了百花齐放的编程语言，才有了欣欣向荣的 IT 产业。 不过，如果只是养成了“一言不合就写脚本”的习惯，与真正优秀 的程序员仍然有很大的差距。同样是排序，不同的数据规模、不同的算 法实现，性能表现都相差巨大。同样地，做同一件事，不同的程序员的 解法和效率也天差地别。程序员圈内一直流传这样的说法： “优秀程序员 的生产力可以达到普通程序员的十倍甚至成百上千倍。”ACM 圈子里的 高手，各种复杂精巧的算法信手拈来，应对极其复杂的问题时编码也如 庖丁解牛，行云流水般顺畅；顶级的程序员甚至能创造世界级的工具， 或者开创一种流派，影响大部分程序员的工作和思维方式。这种差距， 真就像不同算法之间复杂度的差距一样明显，让人望而生畏。 见贤思齐。要怎么做才能步入“优秀程序员”的行列呢？抛开数 学、各种计算机理论的基础不谈，也许最能量化程序员能力的就是“代 码量”了。读更多优秀的代码，就能知道更多好的架构、好的算法；写 更多的代码，解决问题的速度就更快，生产力也就更高。提高代码量这 个简单粗暴的方法，效果的确立竿见影，于是乎一大批在线编程解题网 站应运而生。而本书正是源于日本一个 IT 服务网站 CodeIQ 上的在线编 程解题栏目“本周算法”。这个栏目的主编就是本书作者，他“寓教于 题”，通过精心设计的问题向大家传授了很多算法、程序优化技巧甚至 工程架构方面的经验等。 本书可以看作是一本算法书，与其他编程类、算法类图书最大的不 同有两点：其一是所有问题都贴近生活和实际应用，兼具实用性和趣味 性；其二是以虚拟的人物形象和实际的代码进行讲解，重点向读者演示 不同思路、不同解决方案之间的区别和差距。公交车上如果设置自动找 译者序 v 图灵社区会员 feiifan([email protected]) 专享 尊重版权 零的装置，应该怎么实现？怎样实现一个简单的扫地机器人，让它尽量 不要重复清扫某一个角落？如何串联和并联组合一堆电阻，使得最终电 阻值逼近黄金分割值？像这样接地气、有意思的问题，书中比比皆是。 讲解求斐波那契数列某一项的问题时，作者先由递归切入，后讲查表法 优化，最后引出实际实现时需要处理数值溢出的问题。全书的讲解都像 这样层层深入、条分缕析。 本书共 4 章，每一章都由很多问题构成。第 1 章讲的是最基础的二 进制，通过实例帮助大家理解二进制，进而用二进制解决实际问题；第 2 章 ~ 第 4 章则分别从工程、算法和架构几个方面切入不同的算法优化案 例。此外，个别问题下还会设置专栏，穿插一些作者在软件工程甚至人才 培育等方面的理解和经验。 关于本书，最推荐的阅读方式是读完题先停下来想想解法。此时最 好能打开电脑，打开编辑器，先试着把题做出来。做完之后再往下读， 顺着作者的分析和解答细细体会问题背后的算法思路。书中每一个问 题都汇集了作者以及 CodeIQ 网站大量用户的集体智慧，相信做完题再 作对比，一定可以收获不少新的体会。如果您发现了更好的解法，希望 您可以到图灵社区（http://www.ituring.com.cn/）或者本书的代码仓库 （https://github.com/leungwensen/70-math-quizs-for-programmers）上和大 家分享交流，共同进步。 最后，成书不易，非常感谢图灵各位编辑的帮助和指导，也感念这 将近一年时间里家人的理解和包容。 绝云 2017 年 4 月 5 日于杭州 vi 译者序 图灵社区会员 feiifan([email protected]) 专享 尊重版权 前言 计算机的世界每天都在发生着深刻的变化。新操作系统的发布、 CPU 性能的提升、智能手机和平板电脑的流行、存储介质的变化、云的 普及……这样的变化数不胜数。 在这样日新月异的时代中，“算法”是不变的重要基石。要编写高 效率的程序，就需要优化算法。无论开发工具如何进化，熟识并能灵活 运用算法仍然是对程序员的基本要求。 程序员的工作说白了就是把需求变为程序。人们希望计算机做的事 情就是“需求”，实现需求的就是“程序”。能满足需求的程序肯定不止 一种，我们需要从中挑选出最优的程序。 这里的难点在于，怎样判断一个程序是不是最优的。不同的人对“优 秀的算法”有着不同的理解。我认为，优秀的算法需要满足以下 3 点。 （1）高速 即使是简单实现后在处理上会花很长时间的程序，有时候转换一下 角度进行优化，就能得到一个高速的版本。根据算法内容的不同，有时 候优化的效果不仅仅是速度提升 2 倍、3 倍，甚至提升 100 倍、1000 倍 的情况也不少见。 （2）简化 如何简化输入条件将会决定最终代码的复杂度。越是简单的程序， 可维护性越高。 （3）通用 如果我们在实现程序时有意识地把通用的处理封装起来，那么就能 把源代码用于其他问题或者工作需求上。如果实现的程序即便输入值或 者参数发生变更，代码改动也很小，那么测试往往也能简化。 我很喜欢这么一句话：阅读量决定了学习能力的上限，写作量决定 了学习能力的下限。这是因提出“百格计算”A 而闻名的岸本裕史先生说 的话，个人觉得这对编程也是适用的。要想磨练编程技巧只有两个途 径：一是阅读代码，二是编写代码。 A 岸本裕史先生于昭和 40 年代（1965—1974 年）提出的儿童数学运算训练方法。 在 10×10 的格子的最左一列和最上一行随机填入 0~9 的数字，并在左上角的空 格里指定运算符号（加减乘除），按照运算符号计算行与列中两个数字的运算结 果，然后将结果填入该行与该列对应交叉的那个空格里。 ——译者注 前言 vii 图灵社区会员 feiifan([email protected]) 专享 尊重版权 不存在没有读过其他人写的代码的程序员。很显然，也不存在没有 写过代码的程序员。越是编程技巧高超的开发者，读过的代码越多，写 过的代码也越多。 数据结构和算法的学习尤为重要。多了解堪称无数先驱智慧结晶的 算法，多亲身体会这些算法的效果对程序