程序员的数学(第 2 版)— 全书拆解
30 秒导读: 这本书不教你算题。它教的是一套看问题的眼光—— 遇到一件做不动的事,先问「能不能给它换一种写法」「能不能切成小块」 「能不能不看细节只看类别」。
它的价值有两半。前一半是九件具体的工具,每一件都配一道谜题: 蒙眼魔术师怎么识破观众动没动过棋子、一张纸对折几次能够到月球、 十五个数里怎么问三次就找出目标。
后一半更少见:它老老实实划了两条界。 第一条是「每多一样条件就翻一倍」——三十个开关就有十亿多种组合,一分钟测一次要跑两千年, 于是「有限」和「人等得起」头一回分了家; 第二条更硬——有些程序谁都写不出来,和机器多快没关系。
谁该读它: 会四则运算就能读,一行代码不会也能读。 想学怎么把程序调得更快、想补统计那一块的,这本书给不了(第 18 章会把这条界说清楚)。
1. 先交代清楚:这是谁在什么时 候写的
作者结城浩,日本人。这本书有两个成书时间:正文九章写于 2005 年 2 月1, 十二年后加了一份附录,落款是 2017 年 12 月于横滨2。 所以读它的时候要分开看:正文那九章讲的是不会过期的东西,附录那部分带着 2017 年的时代印记。
第 2 版为什么要加附录,作者自己写明了:那几年机器学习 (不由人来写规则,而是让计算机从大量数据里自己把规则找出来的一类做法) 这个词越来越频繁地出现在生活中,关注的人越来越多3。
这本书最要紧的一条自我设限:尽量不用算式。 作者说他自己遇到书里的算式也想跳过不看, 所以正文九章几乎不出现算式,也没有过多的定义、定理和证明4。 附录是唯一的例外,那里开始有算式,而且作者说让读者熟悉算式的用法本身就是附录的目的之一。
门槛低到什么程度: 作者说读它只需要四则运算和乘方(2³ = 2 × 2 × 2), 其余的书里都会解释5。这条承诺基本兑现了——本组拆解遇到没兑现的地方会当场标出来。
有没有利益相关: 有一处很轻的。第 7 章讲密码那一节,作者推荐了自己的另一本书 《图解密码技术》6。这是作者自荐,不是第三方评价,但也谈不上藏着掖着。
2. 全书一条主线(读完这一节,你就懂了这本书)
这一节是一条链子,十二级,每一级都由上一级逼出来。 只读这一节,不看后面任何一章,你也能把这本书讲给别人听。
① 起点是一条关于人的事实:一次抓不住太多东西
罗马数字里,IIIIIIIIII 和 IIIIIIIIIII 哪个大?得一根根数。 换成 X 和 XI,一眼就看出来了。
差别不在数,在写法。这本书从头到尾都在做同一件事:换一种写法、换一个角度, 把「人做不动」 变成「人做得动」,再变成「机器照做就行」。
② 第一招:给「没有」一个位子,规则就变简单
2503 里那个 0 不表示任何东西,却不能省——省掉就成了 253。 它占住十位那个位置,让「左边那个 5 一定是百位」这件事成立。
这就是全书第一个套路:为「什么都没有」也造一个记号,换来一条不用分情况的规则。 生活里也一样:药盒里每四粒混进一粒没药效的假胶囊,吃药的规矩就从 「吃三天停一天」简化成「每天一粒」。
③ 第二招:把大问题切成一个个小块
为什么先贤要发明 V 和 X,而不是一直画 I?因为数一大就管不住。 造出「五个一组」「十个一组」这样的块,大数才写得下、比得出。
这个动作后面十七章会反复出现:把大问题切小,切出来的每一块就叫一个单元 (能单独处理、还能重复拿来用的那一小块)。 原书自己说这是「贯穿本书」的主旨,一直贯到最后一章。
④ 但切之前,得先学会不重不漏地分两半
「6 岁以上收 100 元,不到 6 岁免费」——这条规则没毛病。 把「6 岁以上」改成「大于 6 岁」,正好 6 岁的人就没人管了; 改成「6 岁以下免费」,6 岁的人又有两种价钱。
一条 if 语句就是一次分两半,而漏和重就藏在边界那一格上。 几百条 if 叠起来出的 bug,病根多半在这里。
⑤ 一眼看不出怎么切,就换个角度分组
今天星期日,一亿天以后是星期几?一天天数要三年多。 可星期是七天一转,所以一亿除以 7,余数是几就是星期几——一次除法,大数直接降成小数。
更狠的一种是只分两组:桌上八枚棋子里黑的是单数还是双数。 这一位信息就够魔术师蒙着眼睛断定观众动没动过棋子; 也够你在不试任何一种铺法的前提下,断定那个房间铺不满。
⑥ 分完还得数得清
数数看着不用教,可「10 米路每隔 1 米种一棵树」有人会答 10 棵——正确答案是 11 棵。
于是有四条法则:两堆没重复就相加、有重复要把重复的减掉、 「每一类分别有几个」就相乘、一样东西重复 n 次就连乘 n 个。 一副扑克牌上能把四条全走一遍:13 张红桃 → 其中 8 张 → 整副 52 张 → 32 个灯泡 42.9 亿种亮灭花样。
⑦ 涉及无穷多个数的断言,两步就能证完
「从 0 加到 n,结果等于 n × (n+1) ÷ 2」——n 有无穷多个,一个个验是验不完的。
但只要两步:先证 n = 0 时成立,再证「若第 k 个成立则第 k+1 个也成立」,就全证完了。 像一排多米诺骨牌:推倒第一张,再保证每一张都能带倒下一张。 写循环时也是这个道理——每转一圈都成立的那句话想清楚了,错就少一半。
⑧ 有的问题身上藏着一个小一号的自己
六层汉诺塔怎么解?先把上面五层挪走、把最大那个挪过去、再把五层挪回来。 也就是说,解六层要用到解五层的办法,而解五层要用到四层……一直缩到零层,零层什么也不用做。
在问题自己身上找出一个小一号的它自己,这就叫递归。 一旦找到,「六层要移动多少次」就能从「零层要移动 0 次」一路算上来,答案是 63 次。
⑨ 可是每多一样条件就翻一倍,「有限」和「人等得起」从这里分家
一张 1 毫米厚的纸对折 39 次,厚度就超过地球到月球的 39 万公里。 注意是 39 次,不是几十万次。
程序里的设置项也是这样:30 个复选框、每个两种状态,全测一遍是 10.7 亿种组合; 一分钟测一次,要跑两千多年。数值翻倍时长在 2 的肩膀上那个数,这个数就叫指数。
于是有了一条要记一辈子的分界:「有限」不等于「做得完」。 说「反正有限,让机器全速跑总会跑完」是没用的——要跑两千年的解决方案,对人不算解决。
⑩ 反过来用它:数据排好序,就能一路砍半
同一件事掉个头就成了利器。十五个排好序的数里找一个,每判断一次砍掉一半: 15 → 7 → 3 → 1,三次就到手。
判断 10 次能覆盖 2047 个数,20 次覆盖 209 万个,30 次覆盖 21 亿个—— 多判断一次,能查的数据就翻一倍。
同一件事还能反着看:与其扛着 100 000 这个大数,不如只数它有几个 0(五个)。 「数一数 0 有几个」得出的那个小数就叫对数——100 000 的对数是 5。 两个大数 相乘,只要把各自的 0 数一数、加起来,再还原回去就行——乘法降成了加法。
⑪ 但有些事不是慢,是数量级上就不够
到这里为止,难题都是「太慢」。第 17 章换了一种难:根本做不到。
理由是数出来的。能写出来的程序可以一个个编号:程序不过是有限种字符的有限排列, 按长短排、同长按字典序排,一个都不漏。可要计算的函数编不完—— 把它们摆成一张表,取对角线上的数各加 1,造出来的那一个必定不在表里。 编得完的东西,盖不住编不完的东西。
具体到一个例子:没人写得出一个程序,能判断「随便给一个程序和一份输入,它会不会停下来」 ——这道题叫停机问题,和机器多快没有关系。
⑫ 全书的落点:人不擅长的地方,长出了这些工具
回头看,每件工具都对着人的一处短板:记不住大数,就发明计数法; 判断容易出错,就发明逻辑;管不了大量事物,就分组;处理不了无穷,就用有限的步骤对付无穷。
目标始终是同一个:把问题化到「机械照做就行」的程度,然后把接力棒交给计 算机。
附录讲的机器学习,是同一套思路的现代版。 它先给一件事假设一种形状(比如「销售额 = 广告费 × a + b」),这个假设出来的形状叫模型; 形状里留着几个待定的数。
然后不由人来定这几个数,而是拿一堆「输入 + 正确答案」反复喂给它, 每次看输出离答案差多远,再把那几个数往「差得少一点」的方向挪一丁点——这个过程就叫训练。 挪的时候不看全局、只看脚下这一步该往哪边走,正是第 ③ 级那句「把大问题切成小块」的又一次应用。
3. 二十一章地图
原书 9 章 + 附录,我们拆成 21 章。
拆的依据是新面孔的密度,不是字数——一节塞不下的概念就另起一节,
一章的节数多到找不着北就拆章。原书哪一章对应我们哪几章,见每章开头的 sourceChapters。
第一组:换一种写法(第 01–05 章)。 对应原书第 1、2 章。
| 章 | 讲什么 | 什么时候来读 |
|---|---|---|
| 01 | 2503 换四种写法;0 干的两件活;全书总方法「切成小单元」 | 想知道这本书到底在教什么,先读这一章 |
| 02 | 漏和重长什么样;一条 if 语句在干什么 | 写过条件判断、被边界坑过 |
| 03 | 「不是、并且、或者、异或、相等」各自的表 | 读需求文档时对「或者」拿不准 |
| 04 | 若 A 则 B、反过来说成不成立、德摩根定律 | 想搞明白「反过来说到底靠不靠得住」 |
| 05 | 把复杂规则压简的二维表;第三个值 undefined | 手上有一堆缠在一起的判断条件 |
第二组:换一个角度(第 06–10 章)。 对应原书第 3、4、5 章。
| 章 | 讲什么 | 什么时候来读 |
|---|---|---|
| 06 | 余数就是分组;找周期;10 的 100 次方天以后是星期几 | 碰上「数大到算不动」的题 |
| 07 | 黑白棋魔术、铺不满的房间、走不完的七座桥 | 想学会「不试一次就断定做不到」 |
| 08 | 两步证完无穷;循环不变式;一个错的归纳证明 | 写循环,或者想知道「证明」是怎么回事 |
| 09 | 加法法则、容斥原理、乘法法则,一副扑克牌走完 | 要估一件事有多少种情况 |
| 10 | 置换、排列、组合;顺序算不算决定要不要除 | 同上,而且要算准 |
第三组:两条界(第 11–18 章)。 对应原书第 6、7、8、9 章。
| 章 | 讲什么 | 什么时候来读 |
|---|---|---|
| 11 | 递归;六层汉诺塔的 63 次;找递归结构的固定动作 | 面对复杂问题想不出下手处 |
| 12 | 斐波那契数列、帕斯卡三角形、自己画自己的图形 | 读完第 11 章想看更多例子 |
| 13 | 对折 39 次;30 个复选框两千年;「有限」不等于「做得完」 | 全书最该先读的一章 |
| 14 | 一路砍半;判断 30 次覆盖 21 亿;对数与计算尺 | 想知道「排好序」为什么这么值钱 |
| 15 | 反证法;质数有无穷多个 | 读第 16、17 章之前必读 |
| 16 | 可数;对角论证法;哪些集合无论怎么编号都会漏 | 同上 |
| 17 | 停机问题;为什么这个程序谁都写不出来 | 想知道计算机的原理性上限在哪 |
| 18 | 全书回顾;书刻意没讲的东西;我们补了哪些 | 读完想把整本书串起来 |
第四组:附录(第 19–21 章)。 对应原书附录「迈向机器学习的第一步」。
| 章 | 讲什么 | 什么时候来读 |
|---|---|---|
| 19 | 为什么偏偏是现在;预测问题与分类问题;考试题为什么要另留 | 完全没接触过这一行 |
| 20 | 一组输入 (1, 0, 1) 从头走到尾:加权和、闸门、差多远、往哪边挪 | 想知道「学习」这两个字具体指什么动作 |
| 21 | 把感知器摞成层;怎么把错处往回捎;人类还剩下哪四件事 | 读完第 20 章 |
推荐顺序: 按 01 → 21 顺序读最省力。原书作者也推荐从第 1 章顺读7。 只想拿一个东西走的话,读第 13 章(为什么「有限」不等于「做得完」)。
4. 这本书覆盖什么、不覆盖什么
覆盖: 按位计数法与 0 的作用、逻辑(真值表 / 文氏图 / 卡诺图 / 三值逻辑)、 余数与奇偶性、数学归纳法与循环不变式、排列组合、递归与递推公式、指数爆炸、 二分法查找与对数、反证法、可数与对角论证法、停机问题,以及机器学习的入门概念。
不覆盖(书里明说或明显没有的):
| 没讲什么 | 依据 |
|---|---|
| 「这段程序会慢多少」的正式写法 | 全书搜不到「O(」这种记号;作者的方针是尽量不用算式 |
| 概率(一件事有多大可能发生,用 0 到 1 之间的数表示)与统计 | 附录小结自己写明「完全没有涉及概率统计等知识」8 |
| 极限、微积分,以及成批处理一排排数的那套数学 | 全书没有;附录里有个最关键的名词一个字都没解释,译者专门加注说明了这一点9 |
| 具体编程语言 | 书里只有几段 C 语言示例,而且作者说不懂 C 也不妨碍理解 |
| 2018 年以后这一行的变化 | 附录落款 2017 年 12 月 |
本组拆解补了什么: 四处,全部在正文里标成「补充(不在书里)」并附查阅日期—— 第 14 章那两个「出门一定会撞见、书里却没给」的名字、第 07 章欧拉那篇论文的年份、 第 17 章图灵那篇论文发表在哪里,以及第 21 章那篇比附录早半年的 2017 年论文。 第 18 章第 6 节把这笔账逐条列了出来——那里连「一句话的通用常识」都记了账。
5. 我们的判断
判断(我们的,不是书里的):这本书真正的门槛不在数学,在耐心。 它的每一章都是「先给你一道题,你先自己想」的结构;跳过思考题直接看答案, 读完只会剩下几个名词。它的价值在推导过程,不在结论。 如果错,会错在: 如果读者本来就受过数学训练,那么这本书对他确实只剩几个名词—— 判据是:一个学过离散数学的人读完第 15、16 章,会不会觉得「这不就是课本第一章」。
判断(我们的,不是书里的):正文九章不会过期,附录三章已经过期了一半。 正文讲的是余数、逻辑、归纳、递归这类几百年不动的东西; 而附录写于 2017 年 12 月,那之后这一行的重心整个移到了另一支(见第 21 章第 8 节)。 如果错,会错在: 附录讲的那台最小的机器、以及「看差多远、再往哪边挪一点」这条路子, 到今天仍然是地基,并没有被替换;过期的是「机器学习现在主要在做什么」这一层。 判据是:今天入门的人是不是仍然从这台最小的机器学起。
判断(我们的,不是书里的):书里那句「人机合力」比它看起来更重要。 作者在前言里说,人不擅长重复劳动但擅长解决问题,计算机反过来10。 **这不是励志话,是全书的方法论:**每一章都在把问题往「机械照做就行」的方向推, 推到那一步就交给机器。如果错,会错在: 这条分工正在被机器学习本身冲刷—— 附录讲的正是「让机器自己找规则」。判据是:原书第 9 章那句「把接力棒传给计算机」, 在附录那套做法下还成不成立。
6. 许诺兑现表
规矩:正文里每一处往后指的话(「第 N 章讲」「后面会讲」「这笔账后面还」) 都要在这张表里记一行,写完逐行核。 往回指的(「第 01 章说过」)不用记—— 那不是欠债,是还账。
三条口径,写在这里免得下次核表的人重数一遍:
- 同一处许诺在引言、边界、可带走里重复出现的,只记最早那一处—— 它们说的是同一笔债,记三次不会让它更容易被还上;
- 第 3 节章节地图里的「读完第 N 章再来」是导航,不是许诺,不记;
- 写成「原书第 N 章」的一律不记——那指的是结城浩那本书的章,不是我们的拆解章。
| 许诺在哪 | 应兑现在哪 | 核过了吗 |
|---|---|---|
index.md §2 ⑥ | 09 第 4–7 节(加法法则 → 容斥原理 → 乘法法则 → 连乘) | ✓ |
index.md §2 ⑪ | 17 第 1 节(「根本做不到」的准确含义)· 16 第 4–7 节(「理由是数出来的」那一步) | ✓ |
index.md §2 ⑫ | 20 第 8 节(「只看脚下往哪走」是「切成小块」的又一次应用) | ✓ |
index.md §导读 | 18 第 6 节(这本书刻意没讲 什么) | ✓ |
index.md §4 | 18 第 6 节(我们补进来的书外内容清单) | ✓ |
index.md §5 判断二 | 21 第 8 节(附录之后这一行的变化) | ✓ |
01 第 6 节 | 14 第 9 节(指数法则变成工具:用加法做乘法) | ✓ |
01 第 8 节 | 02 第 7 节(把大条件拆成两半)· 06 第 3 节(分成七组)· 11 第 3 节(六层化五层)· 14 第 2 节(一刀砍半) | ✓ |
01 第 8 节 | 20 第 8 节(「切成小单元」在附录里的回指) | ✓ |
01 第 8 节末 | 14 第 7 节(「只盯 0 的个数」的正式名字是对数) | ✓ |
01 第 10 节判断块 | 10 第 2 节(0! = 1 用的是同一条准绳) | ✓ |
02 第 8 节边界 | 05 第 3 节(条件一多,改用二维表) | ✓ |
03 第 1 节引言 | 04 第 2–7 节(用这些连接词推出更绕的关系) | ✓ |
03 第 3 节 | 05 第 8 节(同样的逐行核对,用在九行表上) | ✓ |
03 第 9 节边界 | 08 第 4 节(情况无限多时怎么证) | ✓ |
03 第 9 节判断块 | 13 第 3 节(条件一多,行数翻倍) | ✓ |
03 第 9 节边界 | 05 第 6 节(&&、` | |
04 第 4 节 | 07 第 6 节(同一条判断的另一种形式:只能证「不能」) | ✓ |
04 第 5 节 | 15 第 2 节(反证法和「两头取反再对调」是近亲) | ✓ |
04 第 9 节边界 | 05 第 8 节(德摩根定律在三值逻辑里还成不成立) | ✓ |
05 第 1 节引言 | 06 第 1 节(换工具:开始讲余数) | ✓ |
05 第 9 节边界 | 13 第 3 节(格子数为什么是翻倍涨的) | ✓ |
06 第 1 节引言 | 07 第 2 节(把分组压到最少的两组) | ✓ |
06 第 6 节 | 14 第 7 节(「看 0 的个数」的正式说法是对数) | ✓ |
06 第 7 节判断块 | 08 第 4 节(试出来的规律怎么变成证明) | ✓ |
08 第 1 节引言 | 11 第 9 节(递归与归纳是同一件事的两个方向) | ✓ |
08 第 1 节引言 | 15 第 1 节 · 16 第 5 节 · 17 第 5 节(「不能靠试,必须证明」一路用到底) | ✓ |
08 第 9 节边界 | 12 第 3–4 节(斐波那契要往回看两层) | ✓ |
09 第 1 节引言 | 10 第 4–5 节(排列与组合) | ✓ |
09 第 1 节引言 | 13 第 2 节(这一章最后那个连乘长成了指数爆炸) | ✓ |
09 第 8 节边界 | 10 第 4–5 节(组合与排列在那一章讲) | ✓ |
09 第 7 节 | 13 第 2、5 节(连乘 → 指数爆炸 → 「有限」不等于「做得完」) | ✓ |
10 第 2 节 | 11 第 8 节(0! = 1 的递归解释) | ✓ |
10 第 1 节引言 | 12 第 6 节(帕斯卡三角形里的组合数) | ✓ |
10 第 2 节 | 13 第 2 节(阶乘的爆炸式增长) | ✓ |
11 第 1 节引言 | 12 第 3、6、9 节(同一把钥匙开三把锁) | ✓ |
11 第 1 节引言 | 13 第 2 节 · 14 第 2 节(每缩一层翻一倍,以及反过来用它) | ✓ |
11 第 6 节 | 13 第 2 节(2ⁿ − 1 里的 2ⁿ 会爆炸) | ✓ |
12 第 1 节引言 | 13 第 2 节(这串数长得飞快) | ✓ |
13 第 1 节引言 | 14 第 2 节(反过来用它:一路砍半) | ✓ |
13 第 1 节引言 | 17 第 1、5 节(比「跑不完」更硬的那条界) | ✓ |
13 第 8 节边界 | 14 第 5 节(那两个书外的名字在这一节补上) | ✓ |
13 第 5 节 | 17 第 1、5 节(比「跑不完」更硬的那条界) | ✓ |
14 第 5 节 | 18 第 6 节(那两个书外的名字是我们补的) | ✓ |
15 第 1 节引言 | 16 第 5 节与 17 第 5 节(反证法在这两处各用一次) | ✓ |
16 第 7 节 | 17 第 6 节(同一个坑在停机问题这一章再出现一次) | ✓ |
16 第 8 节 | 17 第 6 节(程序可数、函数不可数,是那一章的地基) | ✓ |
18 第 6 节 | 19 第 10 节(附录自己承认没讲概率统计) | ✓ |
19 第 1 节 | 20 第 1–7 节(换一台更具体的机器,走完整个调参过程) | ✓ |
19 第 2 节 | 21 第 5 节(层数更多的那一种是怎么回事) | ✓ |
19 第 10 节边界 | 21 第 7 节 ②(训练数据可不可靠,由谁来判断) | ✓ |
19 第 10 节边界 | 21 第 8 节(附录之后这一行的变化) | ✓ |
20 第 8 节 | 21 第 4 节(要调的数一多,就不能一个个试) | ✓ |