代序

多年前的一個(gè)晚上，本書(shū)作者找到我，說(shuō)會(huì)在《程序員》雜志連載一系列文章，主題是生活中的算法。連載結(jié)束后，會(huì)集結(jié)成冊(cè)匯成一本書(shū)，他想請(qǐng)我為這本八字還沒(méi)一撇的書(shū)繪制插圖。

一開(kāi)始我是拒絕的。我既不是專(zhuān)業(yè)插畫(huà)師，對(duì)所謂生活中的算法也沒(méi)什么概念，這本書(shū)能不能順利出版也還是未知數(shù)，但在他的一再堅(jiān)持下，最終還是答應(yīng)了這個(gè)縹緲的請(qǐng)求。當(dāng)時(shí)我倆誰(shuí)也沒(méi)想到，他所說(shuō)的這本書(shū)，從連載到最后成型出版，整整醞釀了八年。這八年間，我已經(jīng)和他結(jié)了婚，我們的兩個(gè)孩子都比這本書(shū)先“問(wèn)世”了。

連載的那段時(shí)間，他每完成一篇文章，都會(huì)先發(fā)給我看看。而我作為這個(gè)系列的第一個(gè)讀者，每次看完都會(huì)反饋給他能不能看懂、有沒(méi)有問(wèn)題、好不好玩，從一個(gè)業(yè)余讀者的角度，盡可能地監(jiān)督他把問(wèn)題簡(jiǎn)單有趣地講明白。

一個(gè)算法，可以講到它的前世今生，講到它在生活中的應(yīng)用，就連我們?cè)谏�活中遇到的真�?shí)問(wèn)題，也被他寫(xiě)進(jìn)書(shū)里做例子，甚至附上了日期時(shí)間�？缭桨四辏�有些例子也帶上了些許年代感，令人感嘆。

臨近出版，該給書(shū)寫(xiě)個(gè)序了。他坐在我邊上盯著屏幕發(fā)呆，似乎沒(méi)什么思路。瞄了一眼屏幕，這個(gè)家伙竟然在一本正經(jīng)地搜索“如何給一本書(shū)寫(xiě)序”……我說(shuō)要不我先從我的角度寫(xiě)寫(xiě)吧，拋磚引玉，看看我寫(xiě)完能不能給你點(diǎn)靈感。于是便有了這篇代序。

——蔡雪琴，2021 年 8 月

序言

小學(xué)時(shí)，我特別喜歡解數(shù)學(xué)謎題。為了把狼、羊、白菜運(yùn)到河對(duì)岸，為了找出重量較輕的那枚假幣，為了在 3 分鐘內(nèi)煎好全部大餅，為了判斷出誰(shuí)是騎士誰(shuí)是無(wú)賴(lài)，我常常會(huì)廢寢忘食地在紙上寫(xiě)寫(xiě)畫(huà)畫(huà)，最后為自己發(fā)現(xiàn)了答案而興奮不已。有個(gè)謎題讓我至今記憶猶新：把 4 個(gè) A、4 個(gè) B、4 個(gè)C、4 個(gè) D 排成一個(gè) 4 × 4 的方陣，使得每一行都沒(méi)有重復(fù)的字母，每一列也沒(méi)有重復(fù)的字母。我把它解決了，而且獲得了更大的爽快感。因?yàn)�，�?wèn)題的答案并不是我盲目地試出來(lái)的，而是用一個(gè)自己想到的“招數(shù)”得出的。在第一排按順序?qū)懴?A、B、C、D 這 4 個(gè)字母，然后把第一個(gè)字母挪到最后面，變成下一排的字母順序，并且不斷地這樣做下去。等 4 排都寫(xiě)完了，就會(huì)得到一個(gè)正確的答案。

A B C D

B C D A

C D A B

D A B C

而且我發(fā)現(xiàn)，這個(gè)“招數(shù)”十分萬(wàn)能，它可以直接用于字母更多的情況�，F(xiàn)在回想起來(lái)，這沒(méi)準(zhǔn)兒是我解決的第一個(gè)算法問(wèn)題。

中學(xué)時(shí)，我開(kāi)始搞信息學(xué)競(jìng)賽，才知道這是一個(gè)經(jīng)典問(wèn)題，叫作拉丁方陣（Latin square）。當(dāng)年我找到的，不過(guò)是 4 階拉丁方陣的一個(gè)最基本的解。4 階拉丁方陣還有很多，有些沒(méi)法拿我當(dāng)年的“招數(shù)”得出，比如下面這個(gè)：

A D B C

B C A D

C B D A

D A C B

更讓我吃驚的是，這個(gè)看似純粹的數(shù)字游戲，在生產(chǎn)生活中竟然有非常真實(shí)的應(yīng)用。假設(shè)某汽車(chē)發(fā)動(dòng)機(jī)制造商想要測(cè)試并比較 4 種汽油添加劑的性能。不妨把這 4 種汽油添加劑分別記作 A、B、C、D。如果所有試驗(yàn)全在某一輛車(chē)上進(jìn)行，可能會(huì)出現(xiàn)一些問(wèn)題，比方說(shuō)該車(chē)的某些特性正好能讓A 充分發(fā)揮性能，最終的試驗(yàn)結(jié)果會(huì)顯示 A 的性能更好，但這個(gè)結(jié)論無(wú)法廣泛適用于各種場(chǎng)合。類(lèi)似地，駕駛員的習(xí)慣或許也會(huì)無(wú)意地影響到試驗(yàn)結(jié)果。為了消除這些因素的影響，我們可以選擇 4 輛不同的車(chē)（編號(hào)分別為 1、2、3、4）、4 名不同的駕駛員（編號(hào)也分別為 1、2、3、4）。在我當(dāng)年得出的拉丁方陣中，第 2 行第 3 列是 D，我們就把 D 裝進(jìn) 2 號(hào)車(chē)，交給3 號(hào)駕駛員去開(kāi)。所有 16 次測(cè)試中，每種汽油添加劑都用了 4 次，這 4 次都是跟不同的車(chē)、不同的駕駛員搭配，而且每一名駕駛員都沒(méi)開(kāi)過(guò)重復(fù)的車(chē)。這樣得到的試驗(yàn)結(jié)果就能很好地反應(yīng)更普遍的情況。

算法，不但是編寫(xiě)程序的人需要掌握的一門(mén)學(xué)問(wèn)，在人們的日常生活中也扮演著重要的角色。拉丁方陣就是一個(gè)非常好的例子。

大學(xué)時(shí)，看了不少科普書(shū)，自己也試著寫(xiě)了一些。當(dāng)時(shí)，市面上有很多經(jīng)濟(jì)學(xué)、心理學(xué)等“興趣學(xué)科”的優(yōu)秀科普書(shū)，既不像教科書(shū)那樣無(wú)趣，又不像“快餐書(shū)”那樣泛泛而談，不管是門(mén)外漢還是業(yè)內(nèi)人士，看完后都覺(jué)得收獲頗豐。我忽然萌生了一個(gè)想法：算法也是一個(gè)應(yīng)用廣泛、妙趣橫生的學(xué)科，計(jì)算機(jī)行業(yè)內(nèi)外的人應(yīng)該都會(huì)有興趣，但為什么沒(méi)有寫(xiě)給大家看的算法書(shū)呢？那時(shí)，我就計(jì)劃著自己寫(xiě)一本。

我和很多人分享了這個(gè)想法。2012 年，應(yīng)盧鶇翔編輯的邀請(qǐng)，我開(kāi)始為《程序員》雜志的算法欄目供稿。2013 年末，稿件數(shù)量已經(jīng)累積到我覺(jué)得比較滿意的程度了，我便著手將它們串聯(lián)并擴(kuò)充成一本完整的算法書(shū)。2015年，這本書(shū)的初稿終于完成了。接下來(lái)，這本書(shū)進(jìn)入了漫長(zhǎng)而曲折的審校打磨階段，圖書(shū)編輯和插畫(huà)師輪番抱娃，耽誤了不少進(jìn)度，我作為完美主義者、拖延癥患者和插畫(huà)師的孩子他爸，對(duì)此書(shū)跳票亦有卓越貢獻(xiàn)。一眨眼，已經(jīng)到 2020 年了。八年的時(shí)間里凝聚了太多人的智慧和汗水。這里，向所有對(duì)這本書(shū)的寫(xiě)作和出版有幫助的人致謝。

最后，也想對(duì)正在閱讀序言的你說(shuō)一句，祝愿這本書(shū)能陪伴你度過(guò)一段難忘的算法之旅。如果你喜歡剛才那個(gè)拉丁方陣的例子，那你可要做好準(zhǔn)備了。拉丁方陣不過(guò)是算法這個(gè)游樂(lè)園里的旋轉(zhuǎn)木馬，后面的內(nèi)容將會(huì)像過(guò)山車(chē)一樣驚險(xiǎn)刺激！

——顧森，2021年8月