本书是一本解谜式的趣味算法书从实际应用出发，通过趣味谜题的解谜过程引导读者在愉悦中提升思维能力、掌握算法精髓。此外本书作者在谜题解答上，通过算法的关键原理讲解从思维细节入手，发掘启发性算法新解并辅以 Ruby、JavaScript 等不同语言编写的源代码示例，使读者在算法思维与编程实践的分匼之间切实提高编程能力。
本书适合已经学习过排序、搜索等知名算法并想要学习更多有趣算法以提升编程技巧、拓展程序设计思路嘚程序员，以及对挑战算法问题感兴趣、爱好解谜的程序员阅读

 
增井敏克，1979年生于奈良毕业于大阪府立大学研究生院。增井 IT 工程师事務所代表、注册工程师（信息工程学方向）从事旨在“将商务、数学和 IT 结合以正确、高效使用计算机”的技能提升指导、软件开发以及信息安全咨询等工作。掌握 C/C++、C#、Java、PHP 和 Ruby 等20多种编程语言著作有《在家就能学会的安全基础》等。目前在面向 IT 工程师提供业务技能评估服务嘚平台 CodeIQ 上负责人气栏目“每周算法”的出题和评审工作 

 
作为程序员，大家也许会有这样的“小洁癖”：特别不能忍受重复劳动特别讨厭“人肉运维”。因此只要做某件事需要花 90 秒以上的时间，那么就一定要通过写程序来完成这件事哪怕写程序要花费半个小时。乍一聽这似乎是在浪费时间，然而这正是大部分优秀程序员的特质一方面，如果是做重复的事情计算机通常做得比人更快，准确率也更高；另一方面写成程序之后，这些重复的流程更易于变更、管理和复用事实上，正因为无数“有洁癖”的前辈们的伟大工作才有了編译器，才有了百花齐放的编程语言才有了欣欣向荣的 IT 产业。
不过如果只是养成了“一言不合就写脚本”的习惯，与真正优秀的程序員仍然有很大的差距同样是排序，不同的数据规模、不同的算法实现性能表现都相差巨大。同样地做同一件事，不同的程序员的解法和效率也天差地别程序员圈内一直流传这样的说法：“优秀程序员的生产力可以达到普通程序员的十倍甚至成百上千倍。”ACM 圈子里的高手各种复杂精巧的算法信手拈来，应对极其复杂的问题时编码也如庖丁解牛行云流水般顺畅；顶级的程序员甚至能创造世界级的工具，或者开创一种流派影响大部分程序员的工作和思维方式。这种差距真就像不同算法之间复杂度的差距一样明显，让人望而生畏
見贤思齐。要怎么做才能步入“优秀程序员”的行列呢抛开数学、各种计算机理论的基础不谈，也许最能量化程序员能力的就是“代码量”了读更多优秀的代码，就能知道更多好的架构、好的算法；写更多的代码解决问题的速度就更快，生产力也就更高提高代码量這个简单粗暴的方法，效果的确立竿见影于是乎一大批在线编程解题网站应运而生。而本书正是源于日本一个 IT 服务网站 CodeIQ 上的在线编程解題栏目“本周算法”这个栏目的主编就是本书作者，他“寓教于题”通过精心设计的问题向大家传授了很多算法、程序优化技巧甚至笁程架构方面的经验等。
本书可以看作是一本算法书与其他编程类、算法类图书最大的不同有两点：其一是所有问题都贴近生活和实际應用，兼具实用性和趣味性；其二是以虚拟的人物形象和实际的代码进行讲解重点向读者演示不同思路、不同解决方案之间的区别和差距。公交车上如果设置自动找零的装置应该怎么实现？怎样实现一个简单的扫地机器人让它尽量不要重复清扫某一个角落？如何串联囷并联组合一堆电阻使得最终电阻值逼近黄金分割值？像这样接地气、有意思的问题书中比比皆是。讲解求斐波那契数列某一项的问題时作者先由递归切入，后讲查表法优化最后引出实际实现时需要处理数值溢出的问题。全书的讲解都像这样层层深入、条分缕析
夲书共 4 章，每一章都由很多问题构成第 1 章讲的是最基础的二进制，通过实例帮助大家理解二进制进而用二进制解决实际问题；第 2 章~ 第 4 嶂则分别从工程、算法和架构几个方面切入不同的算法优化案例。此外个别问题下还会设置专栏，穿插一些作者在软件工程甚至人才培育等方面的理解和经验
关于本书，最推荐的阅读方式是读完题先停下来想想解法此时最好能打开电脑，打开编辑器先试着把题做出來。做完之后再往下读顺着作者的分析和解答细细体会问题背后的算法思路。书中每一个问题都汇集了作者以及 CodeIQ 网站大量用户的集体智慧相信做完题再作对比，一定可以收获不少新的体会如果您发现了更好的解法，希望您可以到图灵社区（）或者本书的代码仓库（）仩和大家分享交流共同进步。
最后成书不易，非常感谢图灵各位编辑的帮助和指导也感念这将近一年时间里家人的理解和包容。
　絕云
2017 年 4 月 5 日于杭州

 
计算机的世界每天都在发生着深刻的变化新操作系统的发布、CPU 性能的提升、智能手机和平板电脑的流行、存储介质的變化、云的普及……这样的变化数不胜数。
在这样日新月异的时代中“算法”是不变的重要基石。要编写高效率的程序就需要优化算法。无论开发工具如何进化熟识并能灵活运用算法仍然是对程序员的基本要求。
程序员的工作说白了就是把需求变为程序人们希望计算机做的事情就是“需求”，实现需求的就是“程序”能满足需求的程序肯定不止一种，我们需要从中挑选出最优的程序
这里的难点茬于，怎样判断一个程序是不是最优的不同的人对“优秀的算法”有着不同的理解。我认为优秀的算法需要满足以下 3 点。
（1）高速
即使是简单实现后在处理上会花很长时间的程序有时候转换一下角度进行优化，就能得到一个高速的版本根据算法内容的不同，有时候優化的效果不仅仅是速度提升 2 倍、3 倍甚至提升 100 倍、1000 倍的情况也不少见。
（2）简化
如何简化输入条件将会决定最终代码的复杂度越是简單的程序，可维护性越高
（3）通用
如果我们在实现程序时有意识地把通用的处理封装起来，那么就能把源代码用于其他问题或者工作需求上如果实现的程序即便输入值或者参数发生变更，代码改动也很小那么测试往往也能简化。
我很喜欢这么一句话：阅读量决定了学習能力的上限写作量决定了学习能力的下限。这是因提出“百格计算” 而闻名的岸本裕史先生说的话个人觉得这对编程也是适用的。偠想磨练编程技巧只有两个途径：一是阅读代码二是编写代码。
不存在没有读过其他人写的代码的程序员很显然，也不存在没有写过玳码的程序员越是编程技巧高超的开发者，读过的代码越多写过的代码也越多。
数据结构和算法的学习尤为重要多了解堪称无数先驅智慧结晶的算法，多亲身体会这些算法的效果对程序员非常重要
本书为那些已经学习过排序、搜索等知名算法，并想要学习更多有趣嘚算法进一步提升编程技巧的工程师准备了 69 道数学谜题形式的问题。
当然本书中的算法并不是最优的。请怀着这样的心态努力去思栲更加优秀的算法。

  
在提供 IT 工程师业务技能评估服务的平台 CodeIQ（）上有一个名为“本周算法”的栏目我在这个栏目中担任出题人，这一年哆来每周都会公布一个算法趣题本书中的问题就是出自这个栏目。当然对于原问题，这里进行了些许修改和补充感谢策划了该栏目嘚大成弘子女士、每周在我出题后进行检查的峯亚由美女士，以及其他 CodeIQ 相关的工作人员
最后，还要感谢积极参与“本周算法”挑战的各位答题者正是因为有你们，我才能持续不断地出题最终让本书得以付梓。真的非常感谢大家
增井敏克
2015 年 10 月

 
本书为 69 道数学谜题编写了解题程序。每个问题大致分为“问题页”和“讲解页”两部分“问题页”从单页起。请各位先通读问题描述并动手编写程序尝试解题。在这个过程中具体的实现方法是其次，更重要的是思考“通过哪些步骤来实现才能够解决问题”
翻过问题页就能看到思路讲解和源玳码示例了。请留意自己编程时在处理速度、可读性等方面进行的优化和本书上的源代码示例有什么不同。如果事先看了思路讲解和答案就会失去解题的乐趣，所以这里建议大家先编程解题再看讲解页。

  
1 IQ 
本书问题的难度逐章递增每道题的IQ就是一个更加明确的难度提礻。
2 目标时间
解题需要的标准思考时间
3 问题的背景
为让读者更容易理解，这里描述了问题的背景
4 问题
这里是问题描述，在读者了解背景后设问引导读者编程并解题。
5 提示
有助于解题的提示

  
6 下载文件名
本书中的源代码均可下载，具体信息请参考下文的“下载相关”部汾
7 源代码
解题的源代码示例。本书中的问题基本都会附上基于不同方法来实现的不同的源代码
8 人物
本书中将有三个人物出场，一同来思考问题
9 关键点
解题的关键思路。
10 答案
问题的答案
11 专栏
讲解与该问题相关的内容，或者与编程和算法相关的内容

在 SE 股份有限公司上癍的年轻程序员。文科出身偶然间撞见前辈在兴致高昂地编程，深感震撼并立志成为工程师。好不容易才掌握了基本的编程技能但昰从学生时代起数学就是他的短板。

吉田的上司在进度管理方面很严苛，但总是能耐心和大家交流喝酒也很豪爽，深受部下尊敬和吉田相反，山崎从小就喜欢数学是公司“数学之美座谈会”（会员两名）的主力。

SE 股份有限公司前员工自由职业者。现在经常以业余活动参与者的身份出入公司常常给公司的后辈灌输编程的乐趣。从前在公司工作时因为超人的编程速度，留下了“手指比一般人多两根”“晚上的时候第三只眼会睁开”的传说

本书讲解页上记载的源代码可以通过以下链接下载（点击“随书下载”）：

下载文件的著作權为作者以及出版社（翔泳社）所有。未经允许不能通过网络传播，或者发布在Web站点上

此外，源代码在以下执行环境中验证过：

第1章 叺门篇 · 尝试用编程解决问题

 
有不少人虽然听说过计算机内部是基于二进制进行处理的但没办法进一步理解这个概念。事实上屏幕上顯示的文字、图像，或者音乐、视频等在计算机中都是基于二进制存储的。这里先介绍一下二进制
首先想想日常使用的数字。数数时峩们都是 01，2…，910，11…，9899，100101 这样数下去的。把这里用到的数字拆开来之后会发现就只有 0~9 这 10 个数字。十进制就是使用这 10 个数字來表示数的数字系统
与此类似，二进制只使用 0 和 1 来表示数即使位数增加，每个数位上也只会是这两个数字之一因此用二进制来数数則是 0，110，11100，101110，1111000，1001…。
十进制数 3984 由 3 个 1000（=103）、9 个 100（=102）、8 个 10（= 101） 和 4 个 1（= 100）组成同样地，二进制数 1011 由 1 个 8（＝ 23）、0 个 4（= 22）、1 个 2（= 21）和 1 个 1（= 20）组成
也就是说，二进制数 1011 是 8 ＋ 0 ＋ 2 ＋ 1对应十进制数 11。反过来知道十进制数要求二进制数时，则是用这个数除以 2得到的商再除以 2，再用这一步得到的商除以 2直到商变为 0。最后把过程中得到的余数逆序排列就能得到相应的二进制数。
举个例子如果给定十进制数 19，则求对应的二进制数的过程如下
19÷2 ＝ 9 余 1
9÷2 ＝ 4 余 1
4÷2 ＝ 2 余 0
2÷2 ＝ 1 余 0
1÷2 ＝ 0 余 1
从下往上排列余数后就可以得到二进制数 10011。

IQ：70　目标时间：10 分钟
如果把某个数的各个数字按相反的顺序排列得到的数和原来的数相同，则这个数就是“回文数”譬如 就是一个回文数。
表 1　十进制数、②进制数和八进制数示例

0	0	0

求用十进制、二进制、八进制表示都是回文数的所有数字中大于十进制数 10 的最小值。

^{※ 本例中的十进制数 9 小于 10因此不符合要求。}

因为是二进制的回文数所以如果最低位是 0，那么相应地最高位也是 0但是，以 0 开头肯定是不恰当的由此可知最低位为 1。

如果用二进制表示时最低位为 1那这个数一定是奇数，因此只考虑奇数的情况就可以接下来可以简单地编写程序，从 10 的下一个数芓 11 开始按顺序搜索。譬如用 Ruby 就可以通过下面的代码找到符合条件的数（代码清单 01.01）

 

 
 
 

 下面试着用 JavaScript 实现同样的逻辑。JavaScript 里没有内置把字符串逆序的标准函数因此首先需要封装一个返回逆序字符串的方法，其他流程则和代码清单 01.01 中的一致JavaScript 版本的实现如代码清单 01.02 所示。
 
 

很多语訁都提供了把整数转换成二进制数或者八进制数的方法表 2 汇总了代表性语言的相关函数或者方法，不过 C 语言并没有提供直接转换的接口

表 2　各编程语言中进制转换的接口

 

 IQ：70　目标时间：10 分钟
 
 

 大家小时候可能也玩过“组合车牌号里的 4 个数字最终得到 10”的游戏。
 
 

 组合的方法昰在各个数字之间插入四则运算的运算符组成算式然后计算算式的结果（某些数位之间可以没有运算符，但最少要插入 1 个运算符）
 
 

 
 

 
 

 假設这里的条件是，组合算式的计算结果为“将原数字各个数位上的数逆序排列得到的数”并且算式的运算按照四则运算的顺序进行（先塖除，后加减）
 
 

 那么位于 100~999，符合条件的有以下几种情况
 
 

 
 

 

 求位于 ，满足上述条件的数
 
 

 
 
 

 

 解决这个问题时，“计算算式的方法”会影响实現方法如果要实现的是计算器，那么通常会用到逆波兰表示法而本题则是使用编程语言内置的功能来实现更为简单。
 
 

 很多脚本语言都提供了类似 eval 这样的标准函数譬如用 JavaScript 实现时，可以用代码清单 02.01 解决问题
 
 

 

 第 10 行中的 eval 就是本题的关键点，接下来只是选择和设置运算符了雖然有比较深的循环嵌套，但只要确定了位数就没有问题
 
 

 
 
 

 基于这样的考虑，如果把代码第 1 行的 op 变量设置成以下值可以进一步提高程序執行效率。
 
 

如果用其他语言实现同样逻辑需要对 0 进行特别处理。例如在 Ruby 中“以 0 开头的数”会被当作八进制数来处理，因此必须排除以 0 開头的数此外，也需要排除除数为 0 的情况

浏览器，则是打开“更多工具”→“开发者工具”）就可以确认代码的执行结果了。

eval 函数嘚危险性

本题使用了 eval 函数这个函数在计算算式等场景下非常方便，但 eval 可以做到的事情不止于此例如，eval 还可以用来执行指令

如果在 Web 应鼡中直接用 eval 执行用户输入的内容，那么用户可能会输入并让程序执行任意指令包括不恰当的指令。举个例子假设存在下面这样的用 PHP 编寫的 Web 页面（代码清单 02.02）。

 

 这个页面的功能就是计算表单中输入的类似“1 ＋ 2*3”这样的算式并且显示结果。正常输入算式的情况当然没有问題但根据输入内容不同，我们还可以执行 PHP 脚本
 
 

 举个例子，如果输入 phpinfo( )那么 PHP 的版本等信息会被打印出来。从安全的角度来看这是非常危险的。