《計算機程序設計藝術（第４卷）》譯后感

蘇運霖

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

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

關于生成基本的組合模式的問題

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

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

關于組合模式同一些問題的關系

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

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

所以，對于幾十年前在我國人工智能學界曾經有過的研究九鏈環的熱潮，我們不得不作一些反思，那就是我們對于問題的研究，是否確實地應更著重于深度和廣度。為什么不是我們，而是外國人來發現原本是我們提出的問題的理論基礎，從而對它給出真正的解呢？

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

關于組合模式同文字算術或密碼數學的關系

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

SEND

＋MORE

MONEY

表示一個正確的求和，則每個字母應當分別表示什么數？

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

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

VIOLIN+VIOLIN+VIOLA=TRIO+ SUNATA

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

ZEROES + ONES = BINARY

（諸0+諸1=二進制）

COUPLE+COUPLE=QUARTET

（兩個+兩個=四個）

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

TWO×TWO=SQUARE

PI×R×R=AREA

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

工業化+農業化+科學化=現代化

和

立黨為公+執政為民=為人民服務

以及

更快×更高×更強=奧林匹克精神

成立？

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

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

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