计算机程序设计艺术卷1：基本算法(英文版.第3版)（计算机大师高德纳权威著作，精装版）

.　　第2 卷半数值算法
　　第3 章随机数
　　第4 章算术
　　第3 卷排序与查找
　　第5 章排序
　　第6 章查找
　　第4 卷组合算法
　　第7 章组合查找
　　第8 章递归
　　第5 卷语法算法
　　第9 章词法扫描
　　第10 章语法分析
　　第4 卷涉及的范围很广，实际上是3 本书（卷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 für die reine und angewandte Mathematik（ 《理论与应用数学杂志》）
　　例如，我将用“CACM 6 (1963), 555-563”表示前面提到的那篇文献。此外，我用“CMath”表示Concrete Mathematics（《具体数学》）一书，1.2 节的引言部分会引用到它。
　　这套书的许多技术性内容出现在习题中。有些重要习题的构思不是我的原创，我会尽力给出原创者的信息。相应的文献引用通常在该节的正文或者习题的答案中给出。但许多情况下习题是基于未发表的材料的，此时就无法给出进一步的文献信息了。
　　许多人在这套书的撰写过程中给予过我帮助，在此表示深深的谢意。首先是我的妻子Jill，感谢她的极大耐心，感谢她为本书绘制了部分插图，感谢她各方面无尽的支持。其次感谢Robert W. Floyd，他早在20 世纪60 年代就为增强这套书的内容投入了大量的时间。此外，数以千计的其他人士也提供了重要的帮助，如果要一一列出他们的名字还需要一本书的篇幅！他们中的许多人无私地允许我使用其尚未公开发表的内容。我在加州理工大学和斯坦福大学从事研究工作时，美国国家科学基金会和海军研究局给予了多年的慷慨赞助。从1962 年我开始写这套书的时候起，Addison-Wesley 公司就一直给予我极大的帮助与配合。我知道，向他们表示感谢的最好方法就是尽我所能把书写成他们所期望的样子，不负他们的投入。第3 版前言
　　花10 年时间开发了用于计算机排版的系统和系统之后，我现在已经能够实现当初的一个梦想了：用这些系统来排版《计算机程序设计艺术》。最终，本书的全部内容都存储在我的个人电脑中，该电子格式可以随时适应印刷技术和显示技术的改进。新的设置使得我可以在文字上进行数千处的改进，这是我多年来一直想做的。
　　我对新版的文字逐字进行了认真的审阅，力图在保持原有的蓬勃朝气的同时加入一些可能更成熟的论断。新版增加了几十道新的习题，并为原有的几十道习题给出了改进过的新答案。
　　《计算机程序设计艺术》这套书尚未完稿，因此书中有些部分还带有“建设中”的图标，以向读者致歉——这部分内容还不是最新的。我电脑中的文件里堆满了重要的材料，打算写进第1 卷最终的壮丽无比的第4 版中，或许从现在算起还需要15 年的时间。但我必须先完成第4 卷和第5 卷，非到万不得已，我不想拖延这两卷的出版时间。
　　准备这一新版本的大部分艰苦工作是由Phyllis Winkler、Silvio Levy 和JeffreyOldham 完成的。Phyllis 和Silvio 把第2 版的全部文本熟练地录入了计算机，并进行了编辑，Jeffrey 则几乎把所有的插图都转换成了格式。我修正了细心的读者在第2 版中发现的所有错误（以及读者未能察觉的一些错误），并尽量避免在新增内容中引入新的错误。但我想可能仍然有一些缺陷，我希望能尽快加以改正。因此，我很乐意向首先发现技术性错误、印刷错误或历史知识错误的人按每处错误2.56 美元支付报酬。下列网页上列出了所有已反馈给我的错误的最新更正：http://www-cs-faculty.stanford.edu/~knuth/taocp.html。
　　高德纳（Donald E. Knuth）
　　1997 年4 月于加利福尼亚州斯坦福市
　　过去20 年里发生了巨变。
　　—— 比尔·盖茨 (1995)