《计算机程序设计艺术（第４卷）》译后感

苏运霖

高德纳的《计算机程序设计艺术》，始于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多项。因此我们可以斩钉截铁地说：没有基础数学的研究成果，也就没有今天的计算机科学和经济学等的辉煌成果。我国今天取得的航天领域的成就，也是我们在基础理论和综合科学技术方面的成就。为了我国今后科学的持续发展，特别是为了使我国早日成为不仅是经济强国、军事强国，更是科学强国，我们应从振兴中华和民族的未来发展的角度来重视这个问题。如果我们能引导青少年一代，首先重视自己的思想和素质的成长，然后专注于包括娱乐数学、娱乐物理这种难题的研究，从而激发对科学本身的兴趣，那么，我们民族的科学素质就会大为改观。因此，我们出版高德纳的书，其深远意义也应包括这些，而不仅仅在于计算机的那些算法本身上。