代序
多年前的一个晚上,本书作者找到我,说会在《程序员》杂志连载一系列文章,主题是生活中的算法。连载结束后,会集结成册汇成一本书,他想请我为这本八字还没一撇的书绘制插图。
一开始我是拒绝的。我既不是专业插画师,对所谓生活中的算法也没什么概念,这本书能不能顺利出版也还是未知数,但在他的一再坚持下,最终还是答应了这个缥缈的请求。当时我俩谁也没想到,他所说的这本书,从连载到最后成型出版,整整酝酿了八年。这八年间,我已经和他结了婚,我们的两个孩子都比这本书先“问世”了。
连载的那段时间,他每完成一篇文章,都会先发给我看看。而我作为这个系列的第一个读者,每次看完都会反馈给他能不能看懂、有没有问题、好不好玩,从一个业余读者的角度,尽可能地监督他把问题简单有趣地讲明白。
一个算法,可以讲到它的前世今生,讲到它在生活中的应用,就连我们在生活中遇到的真实问题,也被他写进书里做例子,甚至附上了日期时间。跨越八年,有些例子也带上了些许年代感,令人感叹。
临近出版,该给书写个序了。他坐在我边上盯着屏幕发呆,似乎没什么思路。瞄了一眼屏幕,这个家伙竟然在一本正经地搜索“如何给一本书写序”……我说要不我先从我的角度写写吧,抛砖引玉,看看我写完能不能给你点灵感。于是便有了这篇代序。
——蔡雪琴,2021 年 8 月
序言
小学时,我特别喜欢解数学谜题。为了把狼、羊、白菜运到河对岸,为了找出重量较轻的那枚假币,为了在 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月