序言

小学时,我特别喜欢解数学谜题。为了把狼、羊、白菜运到河对岸,为了找出重量较轻的那枚假币,为了在3分钟内煎好全部大饼,为了判断出谁是骑士谁是无赖,我常常会废寝忘食地在纸上写写画画,最后为自己发现了答案而兴奋不已。有个谜题让我至今记忆犹新:把4个A、4个B、4个C、4个D排成一个4×4的方阵,使得每一行都没有重复的字母,每一列也没有重复的字母。我把它解决了,而且获得了更大的爽快感。因为,问题的答案并不是我盲目地试出来的,而是用一个自己想到的“招数”得出的。在第一排按顺序写下A、B、C、D这4个字母,然后把第一个字母挪到最后面,变成下一排的字母顺序,并且不断地这样做下去。等4排都写完了,就会得到一个正确的答案。

A B C D

B C D A

C D A B

D A B C

而且我发现,这个“招数”十分万能,它可以直接用于字母更多的情况。现在回想起来,这没准儿是我解决的第一个算法问题。

中学时,我开始搞信息学竞赛,才知道这是一个经典问题,叫作拉丁方阵(Latin square)。当年我找到的,不过是4阶拉丁方阵的一个最基本的解。4阶拉丁方阵还有很多,有些没法拿我当年的“招数”得出,比如下面这个:

A D B C

B C A D

C B D A

D A C B

更让我吃惊的是,这个看似纯粹的数字游戏,在生产生活中竟然有非常真实的应用。假设某汽车发动机制造商想要测试并比较4种汽油添加剂的性能。不妨把这4种汽油添加剂分别记作A、B、C、D。如果所有试验全在某一辆车上进行,可能会出现一些问题,比方说该车的某些特性正好能让A充分发挥性能,最终的试验结果会显示A的性能更好,但这个结论无法广泛适用于各种场合。类似地,驾驶员的习惯或许也会无意地影响到试验结果。为了消除这些因素的影响,我们可以选择4辆不同的车(编号分别为1、2、3、4)、4名不同的驾驶员(编号也分别为1、2、3、4)。在我当年得出的拉丁方阵中,第2行第3列是D,我们就把D装进2号车,交给3号驾驶员去开。所有16次测试中,每种汽油添加剂都用了4次,这4次都是跟不同的车、不同的驾驶员搭配,而且每一名驾驶员都没开过重复的车。这样得到的试验结果就能很好地反应更普遍的情况。

算法,不但是编写程序的人需要掌握的一门学问,在人们的日常生活中也扮演着重要的角色。拉丁方阵就是一个非常好的例子。

大学时,看了不少科普书,自己也试着写了一些。当时,市面上有很多经济学、心理学等“兴趣学科”的优秀科普书,既不像教科书那样无趣,又不像“快餐书”那样泛泛而谈,不管是门外汉还是业内人士,看完后都觉得收获颇丰。我忽然萌生了一个想法:算法也是一个应用广泛、妙趣横生的学科,计算机行业内外的人应该都会有兴趣,但为什么没有写给大家看的算法书呢?那时,我就计划着自己写一本。

我和很多人分享了这个想法。2012年,应卢鸫翔编辑的邀请,我开始为《程序员》杂志的算法栏目供稿。2013年末,稿件数量已经累积到我觉得比较满意的程度了,我便着手将它们串联并扩充成一本完整的算法书。2015年,这本书的初稿终于完成了。接下来,这本书进入了漫长而曲折的审校打磨阶段,图书编辑和插画师轮番抱娃,耽误了不少进度,我作为完美主义者、拖延症患者和插画师的孩子他爸,对此书跳票亦有卓越贡献。一眨眼,已经到2020年了。八年的时间里凝聚了太多人的智慧和汗水。这里,向所有对这本书的写作和出版有帮助的人致谢。

最后,也想对正在阅读序言的你说一句,祝愿这本书能陪伴你度过一段难忘的算法之旅。如果你喜欢刚才那个拉丁方阵的例子,那你可要做好准备了。拉丁方阵不过是算法这个游乐园里的旋转木马,后面的内容将会像过山车一样惊险刺激!

顾森
2021年8月