《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)（第４卷）》譯后感

蘇運(yùn)霖

高德納的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》，始于1968年，而且很快就把前三卷完成了。人們原來認(rèn)為，接下來出版的自然應(yīng)該是第4卷了，然而，事實(shí)并非如此。近40年過去了，他對(duì)第1卷作過多次修改并再版。第2、3卷，也都分別至少作了一次修改和再版。而且如他所宣稱的那樣，每次修改，不論是哪一卷，都涉及幾乎所有頁面。在此期間，他又發(fā)表了大量的論著，特別是完成了METAFONT和TEX（為計(jì)算機(jī)排版技術(shù)作出巨大貢獻(xiàn)）和著名的《公理與外殼》和《具體數(shù)學(xué)》等著述。但是對(duì)于第4卷，卻遲遲未聞任何信息。只是后來才聽說，第4卷將分為三個(gè)分卷出版，但也未見任何一卷問世。直到此前，人們才終于見到我現(xiàn)在譯出的這第2冊和第3冊。至于后邊還有多少分冊，仍不得而知。

但正因?yàn)槭墙?jīng)過幾十年才出來的東西，因此它就不同凡響，是名副其實(shí)的專著和經(jīng)典之作。作者在前言寫道：“我懷著非常喜悅的心情來寫這些材料，就像許多年前寫第2卷時(shí)我感覺到的激動(dòng)那樣。如同在第2卷中，在那里我高興地看到，初等概率論和數(shù)論的基本原理很自然地出現(xiàn)在關(guān)于隨機(jī)數(shù)生成和算術(shù)運(yùn)算的研究中。而在準(zhǔn)備7.2.1節(jié)的過程中我了解到，當(dāng)我們研究組合生成的算法時(shí)，初等組合學(xué)的基本原理也自然地出現(xiàn)，并且具有高度啟發(fā)性。”他感到有許多美麗的故事等待他來講述。

關(guān)于生成基本的組合模式的問題

乍一看去，無論是生成所有n元組，還是生成排列，這些都不過是很簡單的、屬于已經(jīng)解決了的問題，再無什么遺留問題需要研究。然而，經(jīng)過作者點(diǎn)拔，才發(fā)現(xiàn)事實(shí)上問題絕非我們所想象的那么簡單。作者在提出對(duì)于這個(gè)問題的研究動(dòng)機(jī)時(shí)指出，任何明智的人都不會(huì)想要通過幾千張紙來打印出{0，1，…，9}的所有10!=3628800個(gè)排列的清單。也沒有人會(huì)愿意在一個(gè)計(jì)算機(jī)文件中把它們產(chǎn)生出來。但是，我們需要的是，當(dāng)確實(shí)用得著它們時(shí)，在頃刻之間就以某種數(shù)據(jù)結(jié)構(gòu)把它們提供出來，使得一個(gè)程序可以一次一個(gè)地來考察每個(gè)排列。正是出于此目的，人們就還要考慮這樣一個(gè)問題。而且就這一點(diǎn)而言，它確實(shí)是遠(yuǎn)未解決的問題。

作者在研究中所體現(xiàn)的嚴(yán)謹(jǐn)性表現(xiàn)在：不僅考慮二進(jìn)制，還考慮十進(jìn)制和混合進(jìn)制；不僅考慮集合的元素，還考慮集合的子集、多重集合等。因此，它體現(xiàn)為既有問題的深度，又有問題的廣度。

關(guān)于組合模式同一些問題的關(guān)系

前邊所說的深度，指的是如何以最快速度和最少內(nèi)存訪問來生成所需元組或排列。這樣一個(gè)問題，竟是同圖論有關(guān)，同哈密頓通路或循環(huán)有關(guān)，也同樹形的遍歷有關(guān)。因而作者在這里向我們揭示了這種關(guān)系，使我們懂得原來組合模式的問題還有這種背景，或者說它可以從那些問題的求解中獲得解決問題的理論基礎(chǔ)。

記得幾十年前當(dāng)人工智能在我國掀起一股熱潮時(shí)，一些人曾經(jīng)從人工智能的角度研究過九鏈環(huán)（又稱九龍環(huán)）的問題。然而，就譯者所知，并沒有任何一個(gè)中國學(xué)者，深入地去研究九鏈環(huán)問題的歷史以及它的發(fā)展過程，更沒有人去探討它和其他問題的聯(lián)系。但在這本書里，作者告訴我們，早在1872年法國人劉易斯·格羅斯在一本《步行理論》的小冊子中，就揭示了九鏈環(huán)同二進(jìn)制數(shù)之間的關(guān)系。比如我們以0表示環(huán)與桿分離的狀態(tài)，而以1表示環(huán)在桿上的狀態(tài)，則原來環(huán)鎖在桿上的狀態(tài)就是9個(gè)1的狀態(tài)。問題是要通過從右邊開始（或從左邊開始），每次改換一位，最終使9個(gè)1變成為9個(gè)0。因此作者說，格羅斯才是格雷二進(jìn)制碼真正的發(fā)明者，也是九鏈環(huán)問題真正透徹的最初研究者。

所以，對(duì)于幾十年前在我國人工智能學(xué)界曾經(jīng)有過的研究九鏈環(huán)的熱潮，我們不得不作一些反思，那就是我們對(duì)于問題的研究，是否確實(shí)地應(yīng)更著重于深度和廣度。為什么不是我們，而是外國人來發(fā)現(xiàn)原本是我們提出的問題的理論基礎(chǔ)，從而對(duì)它給出真正的解呢？

高德納還列舉了組合模式生成與歐洲教堂的洪鐘鳴響模式的聯(lián)系，揭示了各種鐘鳴模式與生成排列的關(guān)系，這同樣給人以巨大的啟示。

關(guān)于組合模式同文字算術(shù)或密碼數(shù)學(xué)的關(guān)系

在國外，很早就有人提出文字算術(shù)的概念。如亨利·厄思尼斯特·達(dá)德尼在1924年就提出一個(gè)著名問題：如果每個(gè)字母代表著不同的十進(jìn)制數(shù)字，問要使：

SEND

＋MORE

MONEY

表示一個(gè)正確的求和，則每個(gè)字母應(yīng)當(dāng)分別表示什么數(shù)？

這看似純粹游戲的題目，卻引發(fā)了人們的思考。假若要傳送的是數(shù)字信息，用字母來對(duì)它們加密，這不就成了密碼了嗎？因而在1931年，西蒙·瓦特利寬特就給它起了另一個(gè)名稱“密碼數(shù)學(xué)”。

在他們的開創(chuàng)下，文字算術(shù)或密碼數(shù)學(xué)就蓬勃發(fā)展起來。開始，人們關(guān)注于具有唯一解的問題。而后，人們考慮它們能有的各種解，乃至研究它有多少解。有唯一解的情況，稱為純的文字算術(shù)或純的密碼數(shù)學(xué)。而有的問題，不僅是字母上有意義，而且以數(shù)值解代入后仍正確。例如：

VIOLIN+VIOLIN+VIOLA=TRIO+ SUNATA

（小提琴+小提琴+中提琴=三重合奏）

ZEROES + ONES = BINARY

（諸0+諸1=二進(jìn)制）

COUPLE+COUPLE=QUARTET

（兩個(gè)+兩個(gè)=四個(gè)）

這些通過加法給出的文字算術(shù)，稱為加法性文字算術(shù)。還可以有乘法性文字算術(shù)，例如：

TWO×TWO=SQUARE

PI×R×R=AREA

依照這些問題，我們也可以提出，如何代入數(shù)字，使：

工業(yè)化+農(nóng)業(yè)化+科學(xué)化=現(xiàn)代化

和

立黨為公+執(zhí)政為民=為人民服務(wù)

以及

更快×更高×更強(qiáng)=奧林匹克精神

成立？

除了文字算術(shù)外，也還有像在0與9這些數(shù)字之間，如何加上適當(dāng)?shù)募訙p乘除號(hào)，使得結(jié)果成為一個(gè)數(shù)，如100。在這方面的研究，不僅僅在于給出正確答案，還要研究它們可以有多少個(gè)解，如對(duì)于123456789，可以有12種方法來插入+和-，使其和為100，如100=1+23-4+5+6+78-9=123－45-67+89= -1+2-3+4+5+6+78+9。又如，在12345678987654321中，插入+和-的一個(gè)方式為100=-1234-5-6+7898-7-6543-2-1。

為了鼓勵(lì)這方面的研究，國外出版了多種雜志和圖書。我們所知道的雜志就有J. Recreational Math（娛樂數(shù)學(xué)雜志）、Recreational Math. Magazine（娛樂數(shù)學(xué)期刊）等。這樣，也就使這方面的研究長盛不衰，一直延續(xù)下來。它也推動(dòng)了人們，特別是青少年對(duì)于科學(xué)的興趣和追求。

現(xiàn)代化的科學(xué)技術(shù)源自于基礎(chǔ)理論。有了基礎(chǔ)理論的深厚功底和深刻探索，才帶來了現(xiàn)代科學(xué)技術(shù)的發(fā)展，最雄辯的例子是愛因斯坦的理論，乃是現(xiàn)代科學(xué)技術(shù)用之不竭的思想源泉。有一項(xiàng)研究表明，現(xiàn)代科學(xué)技術(shù)中直接利用愛因斯坦的理論成果的就達(dá)2300多項(xiàng)。因此我們可以斬釘截鐵地說：沒有基礎(chǔ)數(shù)學(xué)的研究成果，也就沒有今天的計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)等的輝煌成果。我國今天取得的航天領(lǐng)域的成就，也是我們在基礎(chǔ)理論和綜合科學(xué)技術(shù)方面的成就。為了我國今后科學(xué)的持續(xù)發(fā)展，特別是為了使我國早日成為不僅是經(jīng)濟(jì)強(qiáng)國、軍事強(qiáng)國，更是科學(xué)強(qiáng)國，我們應(yīng)從振興中華和民族的未來發(fā)展的角度來重視這個(gè)問題。如果我們能引導(dǎo)青少年一代，首先重視自己的思想和素質(zhì)的成長，然后專注于包括娛樂數(shù)學(xué)、娛樂物理這種難題的研究，從而激發(fā)對(duì)科學(xué)本身的興趣，那么，我們民族的科學(xué)素質(zhì)就會(huì)大為改觀。因此，我們出版高德納的書，其深遠(yuǎn)意義也應(yīng)包括這些，而不僅僅在于計(jì)算機(jī)的那些算法本身上。