《计算机程序设计艺术・卷1》试读：前言

本书应数以千计的读者来信之邀而出版．我们用了多年的时间对大量的食谱进行了反复检验，挑选出最佳的、有趣的、完美的食谱奉献给大家．现在我们可以自信满满地说，不管是谁，即使此前从来没有做过菜，只要严格按书中的说明进行操作，也能获得跟我们一样的烹饪效果． ——McCall's Cookbook（1963） 为数字计算机编写程序的过程特别愉快，因为我们不仅可以获得经济和科学两方面的收益，还能尽享写诗或作曲般的艺术体验．本书是多卷丛书中的第一卷，整个丛书旨在培训读者掌握程序员必备的各种技能． 在接下来的章节中，我不打算介绍计算机程序设计的入门知识，而是假定读者已有了一定的基础．预备知识实际上非常简单，但初学者恐怕需要一些时间并动手实践，方能理解数字计算机的概念．读者应该具有如下知识． (a) 对存储程序式数字计算机的工作原理有一些认识．不一定需要电子学背景，但需要知道指令在机器内存中是如何保存和连续执行的． (b) 能够用计算机可以“理解”的确切术语来描述问题的解决方案．（这些机器不懂所谓的常识，它们只会精准地按要求干活，不会多做也不会少做．这是刚开始接触计算机时最难领悟的概念．） (c) 掌握一些最基本的计算机技术，例如循环（重复执行一组指令）、子程序的使用、下标变量的使用． (d) 能够了解常见的计算机术语，如内存、寄存器、位、浮点、溢出、软件等．正文中未给出定义的一些术语，会在每卷最后的索引部分给出简明的定义．或许可以把这四点归结为一个要求：读者起码为一台计算机编写和测试过至少（比如说）4个程序． 我力图使本套丛书能满足两方面的需求．首先，这些书总结了几个重要领域的知识，可以作为参考书；其次，它们可以用作自学教材或计算机与信息科学专业的大学教材．为此，我在书中加入了大量的习题，并为多数习题提供了答案．此外，我在书中尽可能地用事实说话，言之有据，避免做一些含糊的泛泛而谈． 这套书针对的读者不是那些对计算机只有一时兴趣的人，但也绝不仅限于计算机专业人士．其实，我的一个主要目标是使其他领域的广大工作者能够方便地了解这些程序设计方法，他们本可以利用计算机获得更丰硕的成果，但却没时间去技术刊物中查找必需的信息． 本套丛书的主题可以称为“非数值分析”．在传统意义上，计算机是与方程求根、数值插值与积分等数值问题求解联系在一起的，但我不会专门讨论数值问题，最多顺带提一下．数值计算的程序设计是一个发展迅猛、引人入胜的领域，目前已出版了许多相关图书．不过，从20 世纪60 年代初期开始，计算机更多地用于处理那些很少出现数值的问题，此时用到的是计算机的决策能力而非算术运算能力．非数值问题中也会用到一些加法和减法，但基本不需要乘法和除法．当然，即便是主要关注数值计算的程序设计的人也可以在非数值方法的学习中受益，因为数值程序中也会用到非数值方法． 非数值分析的研究成果散见于大量科技刊物中．通过研究，我从大量文献中提炼出了一些可以用于多种编程场合的最基本的方法，并尝试着将其组织为一套“理论”．同时，我还展示了如何应用这一理论解决大量的实际问题． 当然，“非数值分析”是一种太过负面的否定性的提法，使用肯定性的描述语来刻画这一研究领域要好得多．“信息处理”对于我们的内容而言过于宽泛，“程序设计技术”又显得太狭窄了，因此我提出用算法分析来概括本套丛书的主题比较恰当，这一名称暗示我们将探讨“与特定计算机算法的性质有关的理论”． 整套丛书以《计算机程序设计艺术》为题，内容总览如下． 卷1. 基本算法 第1 章：基本概念 第2 章：信息结构 卷2. 半数值算法 第3 章：随机数 第4 章：算术 卷3. 排序与查找 第5 章：排序 第6 章：查找 卷4. 组合算法 第7 章：组合查找 第8 章：递归 卷5. 语法算法 第9 章：词法扫描 第10 章：语法分析 第4 卷涉及的范围很大，实际上包含三本书（卷4A、4B 和4C）．此外，我还计划编写两卷更具专业性的内容：第6 卷语言理论（第11 章）和第7 卷编译器（第12 章）． 1962 年，我打算按顺序把上述章节组织成一本书，但很快就意识到应该深入介绍这些主题，而不能蜻蜓点水般地只讲些皮毛．最终写成的篇幅表明，每一章包含的内容都无法在一学期的大学课程中讲完，因此只能分卷出版．我知道一本书仅有一章或两章会显得很奇怪，但为了便于相互参照，我决定保留原来的章节编号．我计划出一本第1 卷至第5 卷的精简版，供大学用作本科计算机课程的参考书或教材．该精简版的内容是这5 卷的子集，但略去了专业性较强的信息．精简版与完整版的章节编号将保持一致． 本卷可以看成是整套丛书的交集，因为它包含了其他各卷都需要用到的基本内容，而第2卷至第5 卷则可以彼此独立地阅读．第1 卷不仅可以作为阅读其他各卷的参考书，还可以用作下述课程的大学教材或自学读物：数据结构（主要是第2 章的内容），或者离散数学（主要是1.1 节、1.2 节、1.3.3 节和2.3.4 节的内容）、机器语言程序设计（主要是1.3 节和1.4 节的内容）等． 我撰写本书的出发点不同于当前的大多数计算机程序设计书籍．我教给读者的不是如何使用别人的软件，而是如何自己编写更好的软件． 我最初的目标是引领读者到达每个主题的知识前沿．然而，身处一个经济上有利可图的领域，要保持不落伍是极端困难的，计算机科学的迅猛发展使我这一梦想最终破灭了．我们讨论的每一个主题都包含了全世界成千上万的能人异士所贡献出的成千上万的精妙成果．因此，我一改初衷，开始专注于那些很可能在多年后仍然很重要的“经典”方法，并尽我所能来描述它们．特别地，我尽力跟踪了每个主题的演变历史，为其未来的发展打好坚实的基础；我尽力选择了与当前用法一致的简明术语；我尽力囊括了与顺序计算机程序设计相关的所有美妙且易于表述的思想． 对于本套丛书的数学内容还需要说几句．从内容选择上来说，具有高中代数知识的普通读者就可以阅读这些书，遇到涉及较多数学知识的部分时可以略读，而偏好数学的读者则可以学到许多与离散数学相关的很有意思的数学方法．为在行文上兼顾这两类读者，我给每道习题都标定了等级，数学性强的题目会被特别标示出来，我还在多数章节里把主要数学结果放在其证明之前陈述．相关证明要么留作习题（答案单独用一节集中给出），要么在小节的最后给出． 如果读者主要对程序设计而非相关的数学内容感兴趣，那么可以在感觉数学难度显著加大时停止阅读这一节，而对数学有兴趣的读者则能在这些节中发现许多丰富而有趣的内容．不少已经发表的与计算机程序设计有关的数学文章都含有错误，本书的目标之一就是用正确的数学方法向读者传授相关的内容．我自认为是一名数学家，因此会竭尽所能地维护数学的完整性，对此我责无旁贷． 其实有基本的微积分知识就足够理解本丛书中的多数数学内容，因为所需的其他理论大多是由此建立起来的．当然，有时我会用到复变函数理论、概率论、数论等更深入的定理，这种情况下我会列出相应的教科书供读者参考． 撰写这套丛书时最艰难的抉择，在于如何展示各种各样的方法．采用流程图且非形式化地逐步描述算法显然很有优势，相关讨论可以参考《ACM 通讯》第6 卷（1963 年9 月）第555-563 页的“Computer-Drawn Flowcharts”（计算机绘制流程图）一文．不过，描述任何计算机算法时，形式化的准确语言也是必不可少的，我需要决定是使用ALGOL 或FORTRAN这样的代数语言，还是使用一种面向机器的语言．可能当今的许多计算机专家都不赞同我最终使用了面向机器的语言，但我确信自己的选择是恰当的，理由如下． (a) 程序员在很大程度上受编程语言的影响．如今的主流趋势就是，使用语言中最简单的结构而不是对机器而言性能最好的特性来构建程序．如果学习并理解了面向机器的语言，程序员会倾向于使用一种效率高得多的方法，这更贴近实际． (b) 除了个别情况，我们所用的程序都相当短小．因此只要有台合适的计算机，理解这些程序不会有什么难度． (c) 高级语言不适合用来讨论协同程序链接、随机数生成、多精度算术以及与内存有效使用相关的许多问题的底层细节． (d) 只要不是对计算机只有一时兴趣的人，都应该学好机器语言，这是计算机的基础． (e) 无论如何，我们都需要某种机器语言作为许多示例中的软件程序的输出． (f) 代数语言每隔5 年左右就会改朝换代，而我想强调的是永恒的思想． 从另一个角度来看，我承认如果使用高级程序设计语言，程序的编写要容易一些，程序的调试更是容易很多．事实上，计算机已非常强大快速，我从1970 年开始就很少使用低级的机器语言编写程序了．然而，对于书中许多有趣的问题而言，程序员的技巧是至关重要的．例如，某些组合计算需要重复1 万亿次，其内循环时间每减少1 微秒，我们就能节省11.6 天．类似地，多花些时间编写每天需要在许多计算机装置中多次使用的软件也是值得的，因为软件只需要编写一次． 既然已经决定了使用面向机器的语言，下一个问题就是应该用哪种语言．我可以选择特定机器X 上的语言，但若如此，没有机器X 的人就会认为本书是仅仅针对X 用户的．此外，机器X 可能具有许多与本书内容无关的特性，仍需加以解释．两年后，生产机器X 的厂家可能会推出X + 1 或10X，那时候就不会再有人对X 感兴趣了． 为了避免陷入这样的窘境，我尝试着设计了一种操作规则非常简单（甚至只要一个小时就能掌握）的“理想”计算机，它跟实际的机器很类似．学生没有理由对学习多种计算机的特性感到恐惧：一旦掌握了某种机器语言，其他机器的语言自然就很简单了．毫无疑问，真正的程序员在职业生涯中会碰到许多种机器语言．对于我们的假想机而言，现在唯一的缺陷就是难以执行为它编写的程序．幸运的是，许多志愿者已经自告奋勇地站出来为其编写模拟程序了，因此程序的执行也不再是问题了．这些模拟程序非常适合于教学目的，因为它们甚至比实际的计算机还要易于使用． 我尽量在讨论每个主题时引用最好的早期论文，并摘录一些新的进展．对期刊文献的引用一般采用标准的缩写方式，但下列引用最频繁的杂志例外，它们的缩写如下： CACM = Communications of the Association for Computing Machinery（《ACM 通讯》） JACM = Journal of the Association for Computing Machinery（《ACM 杂志》） Comp. J. = The Computer Journal (British Computer Society)（英国计算机学会《计算机杂志》） Math. Comp. = Mathematics of Computation（《计算数学》） AMM = American Mathematical Monthly（《美国数学月刊》） SICOMP = SIAM Journal on Computing（《SIAM 计算杂志》） FOCS = IEEE Symposium on Foundations of Computer Science（《IEEE 计算机科学基础论文集》） SODA = ACM-SIAM Symposium on Discrete Algorithms（《ACM-SIAM 离散算法论文集》） STOC = ACM Symposium on Theory of Computing（《ACM 计算理论论文集》） Crelle = Journal fur die reine und angewandte Mathematik（《理论与应用数学杂志》）例如，我将用“CACM 6 (1963), 555{563”表示前面提到的那篇文献．此外，还会用《具体数学》表示Concrete Mathematics 一书，1.2 节引言部分会引用到它． 这套丛书的许多技术性内容出现在习题中．有些重要习题的构思不是我的原创，我会尽力给出原创者的信息．相应的文献引用通常在该节的正文或者习题的答案中给出．但许多情况下，习题基于未发表的材料，此时就无法给出进一步的引文信息了． 许多人在本套丛书的撰写过程中给予了帮助，在此表示深深的谢意．首先是我的妻子高精蘭，感谢她的极大耐心，感谢她为本书绘制了部分插图，感谢她各方面无尽的支持．其次感谢罗伯特•弗洛伊德，他早在20 世纪60 年代就为增强本套丛书的内容投入了大量的时间．此外，其他数以千计的人士也提供了重要的帮助，如果要一一列出他们的名字还需要一本书的篇幅！他们中的许多人无私地允许我使用其尚未公开发表的内容．我在加州理工大学和斯坦福大学从事研究工作时，国家科学基金会和海军研究署给予了多年的慷慨赞助．从我1962 年开始写书起，Addison-Wesley 公司就一直提供着大力的支持和合作．我知道，向他们表示感谢的最好方法就是尽我所能把书写成他们所期待的样子，不负他们的投入． 第3 版前言 花10 年时间开发了用于计算机排版的TEX 系统和METAFONT 系统之后，我现在已经能够实现当初的一个梦想了：用这些系统来排版《计算机程序设计艺术》．最终，本书的全部内容都存储在我的个人电脑中，该电子格式可以随时适应印刷技术和显示技术的改进．新的设置使得我可以在文字上进行数千处的改进，这是我多年来一直想做的． 我对新版的文字逐字进行了认真的审阅，力图在保持原有的蓬勃朝气的同时，加入一些可能更成熟的论断．新版增加了几十道新的习题，并为原有的几十道习题给出了改进的新答案． 《计算机程序设计艺术》丛书尚未完稿，因此书中有些部分还带有“建设中”的图标，以向读者致歉——这部分内容还不是最新的．我电脑中的文件里堆满了重要的材料，打算写进第1 卷最后壮丽无比的第4 版中，或许从现在算起还需要15 年的时间．但我必须先完成第4卷和第5 卷，非到万不得已，我不想拖延这两卷的出版时间． 我一直在努力扩展和改进这套书，从1980 年开始，有了Addison-Wesley 出版公司的编辑彼得•戈登的指导，这一工作的进展大有提高．他已经不仅是我的出版伙伴，而且成为了我私交很好的朋友，是他不断地促使我朝着卓有成效的方向前进．的确，这三十多年来，我和出版社数十位朋友的互动交往，恐怕是远远超过了一个作者所能享受到的待遇．特别值得赞许的是，责任编辑约翰•富勒永不知疲倦地提供支持，尽管我频繁更新书中内容，他也始终如一地注重任何一个细节，让这套书以最高质量标准面世． 准备这一新版本的大部分艰苦工作是由菲利斯•温克勒、西尔维奥•利维和杰弗里•奥尔德姆完成的．温克勒和利维把第2 版的全部文本熟练地录入了计算机，并做了编辑修改，奥尔德姆则几乎把所有的插图都转换成了METAPOST 格式．我修正了细心的读者在第2 版中发现的所有错误（还有读者未能察觉的一些错误），并尽量避免在新增内容中引入新的错误．但我猜测可能仍然有一些缺陷，我希望能尽快加以改正．因此，我很乐意向首先发现技术性错误、印刷错误或历史知识错误的人按每处支付$2.56．下列网页上列出了所有已反馈给我的最新勘误：http://www-cs-faculty.stanford.edu/~knuth/taocp.html． 高德纳 加利福尼亚斯坦福 1997 年4 月 过去二十年里发生了巨变． ——比尔• 盖茨（1995）