本专栏从 Donald E. Knuth 的《计算机程序设计艺术》第 1 卷《基本算法》开始阅读底本为第 3 版中文译本苏运霖译国防工业出版社2002 年。本文是专栏导言主要依据原书前言、阅读说明、习题说明与目录并借用 §1.1 的欧几里得算法说明后续的阅读方法。正文中的代码和例子由本专栏另行整理。一段程序通过了测试我们通常会接着问还有没有漏掉的边界情况数据变大以后会慢多少如果换一种数据结构哪些操作会变便宜哪些又会变贵这些问题需要我们把代码再往下拆一层明确输入和输出找出执行过程中保持不变的关系解释循环为什么结束再数清楚主要操作做了多少次。这个专栏就从这里开始。《计算机程序设计艺术》的英文书名是The Art of Computer Programming本专栏简称 TAOCP。面对这样一部内容密集的书先确定读法比给自己定下每天读多少页更有用。1. 这个专栏想把什么讲清楚后续文章会围绕原书的小节展开。遇到一个算法我们会先明确它处理的问题再沿着具体输入走一遍随后检查正确性、终止条件和运行代价。需要实现时再把这些步骤落实到代码。我尤其想把那些容易被一句“显然”带过的地方写出来。例如一次替换为什么不会改变答案一个求和式的下标为什么从 0 开始指针改写的先后顺序为什么会影响结果。这些地方往往比最后的公式更值得停下来。文章会保留必要的数学推导同时给出可以手算或运行的小例子。实验能帮助我们发现错误、观察规律一般性的正确性结论仍然需要论证。读者可以把笔记和原书对照着看再回到习题检验自己的理解。2. 第 1 卷的内容地图这份第 3 版中文译本的正文分为两章基本概念和信息结构。下面列的是本卷的阅读主线页码均指书内印刷页码。原书位置内容阅读时关注的问题§1.11 页起算法怎样明确描述计算过程怎样判断它是否终止、是否正确§1.29 页起数学准备怎样使用归纳法、求和、数论、生成函数与渐近表示分析算法§1.3120 页起MIX在一个明确的机器模型中指令如何执行操作代价如何计算§1.4178 页起某些基本程序设计技术子程序、共行程序、解释程序以及输入输出怎样组织§2.1222 页起§2.2227 页起信息结构引论与线性表栈、队列、数组和链式结构怎样表示存储方式如何影响操作§2.3293 页起树如何表示和遍历树如何分析树的结构与路径§2.4399 页起§2.5409 页起多重链接结构与动态存储分配数据之间有多种联系时怎样组织空间怎样分配和回收目录里有些术语带有译本的时代特点。例如 §1.4.2 的“共行程序”对应 coroutine后续讲解时会同时注明现在常用的“协程”并结合原书的控制转移过程解释。从这个目录也能看出“基本算法”中的“基本”覆盖得很深既要理解抽象步骤也要关心数据放在哪里、程序怎样调度、空间如何管理。3. 用一个小算法试试这种读法原书 §1.1 用欧几里得算法作为开头的例子。给定两个正整数m , n m,nm,n要求它们的最大公因子。例如求119 119119和34 3434的最大公因子119 3 × 34 17 , 34 2 × 17 0. 1193\times3417,\qquad 342\times170.1193×3417,342×170.于是答案是17 1717。把这个过程写成 Python代码只有几行defgcd_euclid(m:int,n:int)-int:输入两个正整数返回它们的最大公因子。ifm0orn0:raiseValueError(m 和 n 必须是正整数)whilen!0:m,nn,m%nreturnmprint(gcd_euclid(119,34))# 17这里约定调用者传入整数并显式检查它们为正数与本节讨论的输入范围保持一致。Python 的同时赋值先计算右侧再更新两个变量。写完代码后有几件事还需要说清楚。替换前后的问题为什么等价设m q n r mqnrmqnr。一个正整数如果同时整除m , n m,nm,n就整除r m − q n rm-qnrm−qn反过来如果它同时整除n , r n,rn,r就整除m q n r mqnrmqnr。两组数的公因子完全相同因此gcd ⁡ ( m , n ) gcd ⁡ ( n , r ) . \gcd(m,n)\gcd(n,r).gcd(m,n)gcd(n,r).这给出了循环中的不变量当前两个数的最大公因子始终等于最初的答案。循环为什么一定结束当n 0 n0n0时余数满足0 ≤ r n 0\le rn0≤rn。每次进入下一轮第二个数都会严格减小而非负整数不可能无限严格下降。最终第二个数变为 0此时第一个数就是所求结果。运行代价怎样计算对于119 , 34 119,34119,34程序做了两次取余。对其他输入次数可能不同。进一步分析时需要说明是在数取余次数、机器指令数还是实际运行时间如果整数很大一次取余自身的代价也要纳入考虑。这个例子展示了后续文章的写法算法步骤之后继续解释每一步依据什么以及效率结论采用了什么计数方式。欧几里得算法的完整讨论留到 §1.1。4. 数学准备和 MIX 应该怎么读§1.2 包含归纳法、数与幂和对数、和与积、初等数论、排列与阶乘、二项式系数、调和数、斐波那契数、生成函数以及算法分析和渐近表示。它们会在后续算法中反复出现。如果你也在读本博客的《具体数学》专栏很多工具会比较熟悉。可以把已有的求和、递归和渐近分析知识带过来用它们处理实际算法中的计数问题。遇到同名概念时仍要检查本节的符号、下标和适用条件。第一次读时可以先弄清公式想计算什么完成一个小规模例子再补全推导。遇到暂时不会的技巧把卡住的位置记下来后面碰到它的具体用途时再回来往往更容易理解。原书的阅读说明也允许初读时略过带星号的专门内容。MIX 则需要换一个角度看。这个版本使用 MIX 及其汇编语言来描述机器层面的计算。读这部分时重点是建立具体的执行过程寄存器里有什么内存单元怎样变化一条指令完成了哪些操作。后续笔记会用 Python 辅助展示算法思想。涉及 MIX 指令行为、存储布局或精确计数时会回到原书的模型分别说明二者的用途。Python 示例测得的耗时不能直接当作原书 MIX 程序的执行代价。5. 先学会看习题标记原书在正文之前专门解释了习题的难度标记。这部分值得先读否则很容易把一项需要长期研究的问题当成自己理应马上做出的课后题。下面是对几个代表性分值的概括分值大致含义00理解正文后可以直接回答10简单练习需要稍作思考20检验基本理解的普通题目30需要较多思考或工作的题目40很难或工作量较大可以达到课程项目的规模50按作者编写该版时所知尚未得到满意解决的研究问题这些数值是阅读参考不是做题限时。尤其是 50 分只能表达原书写作时的状态讨论具体题目时还需要查清后来的研究进展。另外M表示偏重数学HM表示涉及书中没有充分提供的高等数学背景三角标记▶表示作者特别推荐。字母标记和数值难度需要一起看HM本身并不等于难度最高。对第一次阅读我建议先做能检查定义和基本步骤的题目再选择与当前小节最相关的推荐题。先留下自己的尝试再比较书后答案。比较时要找的是思路的差异用了哪个性质省略了哪些中间步骤有没有忽略输入条件。6. 后续文章怎样组织专栏先按第 1 卷的原书顺序推进。标题保留原书节号并写明卷号例如【计算机程序设计艺术 TAOCP】卷1·1.1 算法【计算机程序设计艺术 TAOCP】卷1·1.2.1 数学归纳法篇幅较长的小节可以拆成“上、下”或主题补充篇开头仍会注明对应的原书位置。页码以这份 2002 年中文译本的书内页码为准其他版本可以优先通过节号对照。每篇会交代所需前置知识围绕具体问题展开推导并在合适的位置加入手算过程、示意表或可运行代码。原书结论、笔记中的解释和额外推广会分别说明避免把新增的例子或约定归到作者名下。读完一篇可以先合上文章试着用自己的话说明算法为什么正确再换一组输入亲手执行。如果这两步都能完成就有了继续读下一节的基础。下一篇从卷 1 的 §1.1“算法”开始明确算法的含义并继续分析欧几里得算法。参考与版本Donald E. Knuth 著苏运霖译《计算机程序设计艺术》第 1 卷《基本算法》第 3 版国防工业出版社2002 年。本文主要参照卷首“阅读本套书的步骤”“关于习题的说明”、目录与 §1.1欧几里得算法见书内第 2 页。Donald Knuth 的 TAOCP 官方页面。版本信息和勘误可从作者页面进一步查阅。