数数的四条法则 — 一副扑克牌上的加、减重复、乘、连乘
这一章讲三件事: 数数为什么会出错、错在哪; 四条能把「数不清」变成「算得出」的法则; 以及每条法则各自的前提——用错前提,答案就是错的。
它在全书链条里的位置: 第 02 章讲了漏和重是切分的两种失败, 这一章说的是同两件事在数数上的样子。 第 10 章接着讲更复杂的数法(排列、组合), 第 13 章会拿这一章最后那个连乘引出全书最重要的一条界。 需要的基础: 会乘法就行。
1. 先看现象:10 米长的路,每隔 1 米种一棵树,要几棵
很多人脱口而出:10 ÷ 1 = 10 棵。
答案是 11 棵1。
0 1 2 3 4 5 6 7 8 9 10 ← 米数
│ │ │ │ │ │ │ │ │ │ │
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ← 树,一共 11 棵
图说:10 ÷ 1 算出来的 10 不是树的棵数,是「树与树之间的间隔数」。
两端的树各占一个位置,所以棵数比间隔数多 1。
错在哪?错在把「间隔数」当成了「棵数」2。 而且要注意:0 米那个位置也有一棵树——第 01 章讲的「不要忘记 0」在这里第一次收账。
同一道题换一件外 衣,程序员天天见: 内存里排着 100 个数据, 从第 1 个开始编号 0、1、2……最后一个的编号是几? 99,不是 1003。
原书说了一句很扎心的话: 这种题很少有人答错; 可到了实际编程的时候,面对同样的问题却有很多人出错4。
2. 数数到底是什么动作
这一节回答:既然会错,那就得先看清「数数」是在干什么。
数一叠牌的时候,你其实在做这件事5:
挑一张还没数过的 → 说「1」
挑一张还没数过的 → 说「2」
挑一张还没数过的 → 说 「3」 …… 直到没有牌为止
说白了:把要数的东西和整数一个一个对上,最后报出的那个数就是答案。 只要对得没毛病,数出来的结果就是对的6。
于是出错的方式也只有两种7:
| 病 | 什么意思 |
|---|---|
| 漏 | 明明还有没数到的,却以为数过了 |
| 重 | 已经数过的,又多数了一次 |
这两个词在第 02 章出现过——那里管的是规则切分,这里管的是数数。 是同一件事的两副面孔:一一对应不能有缝,也不能有重叠。
但手指头只够数几十张牌。 东西一多,就得改成 先找出「对应规则」,再靠规则去算——而规则要从对象本身的性质里读出来8。 原书把这件事叫作认清计数对象的性质9, 它是这一章和第 10 章反复出现的那句话。
上一节那道植树题的收尾正是这个: 与其数树,不如把它抽象成 「n 米的路,要 n + 1 棵树」——这样换成 10 000 米也一样算得出10。
3. 主走查开始:一副扑克牌,四条法则
从这一节起,四条法则全部落在同一副扑克牌上。
全章的主走查:一副 52 张的扑克牌(不含王牌)
─────────────────────────────────────────────────────────
§4 红桃一共几张? 10 + 3 = 13 加法法则
§5 这 13 张里能点亮灯泡的? 6 + 4 − 2 = 8 容斥原理
§6 整副牌一共几张? 4 × 13 = 52 乘法法则
§7 32 个灯泡有几种亮灭花样? 2×2×…×2 = 42.9 亿 连乘
─────────────────────────────────────────────────────────
图说:四步是一条线:先把两堆加起来,发现有重复就减掉,
再把「每类分别有几个」乘起来,最后把同一件事重复 32 次连乘。
4. 第一条:加法法则(红桃 13 张)
一副牌里的红桃有 10 张数字牌(A 到 10)和 3 张花牌(J、Q、K),一共几张?
13 张。10 + 311。这是主走查的第一步。
这就是加法法则:两堆东西合起来的个数,等于两堆各自的个数相加12。 简单到不用讲——但它有一个前提,而前提才是要讲的:
加法法则只在「两堆没有重复的东西」时才成立13。
数字牌和花牌没有任何一张是重叠的,所以 10 + 3 才对。 下一节就是前提不成立的情形。
5. 第二条:容斥原理(能点亮灯泡的 8 张)
这一节回答:两堆有重叠时怎么办。
原书设了一个装置:放进一张牌,按牌的级别(A 算 1,J、Q、K 算 11、12、13)决定灯亮不亮14:
- 是 2 的倍数 → 亮;
- 是 3 的倍数 → 也亮;
- 两个都不是 → 灭。
把 13 张红桃一张张放进去,能点亮的有几张?
先按加法法则试试15:
1 到 13 里,2 的倍数:2、4、6、8、10、12 …… 6 个
1 到 13 里,3 的倍数:3、6、9、12 …… 4 个
6 + 4 = 10 ?
不对。6 和 12 在两行里各出现了一次,被数了两遍。
┌──── 2 的倍数 ────┐
│ 2 4 8 10 │ 6 12 │ 3 9 │
│ └──────────┼──────────┘
└──────────────────┘ ↑ 两边共有 └ 3 的倍数 ┘
图说:中间那两个(6 和 12)同时是 2 的倍数和 3 的倍数,
也就是 6 的倍数。加法法则把它们数了两次,得减回去。
所以答案是 6 + 4 − 2 = 8 张16。这是主走查的第二步。
这条「先加起来、再把重复的减掉」的法则,叫容斥原理17。 它就是考虑了重复的加法法则:
两堆合起来的个数 = 第一堆 + 第二堆 − 两堆共有的
用它的时候,难点从来不在减法,在「共有的到底有几个」18—— 这道题里共有的是「6 的倍数」,你得先看出这一层。这又是「认清对象的性质」。
6. 第三条:乘法法则(整副 52 张)
一副牌有红桃、黑桃、方片、梅花四种花色,每种花色都有 13 个级别。一共几张?
52 张。4 × 1319。这是主走查的第三步。
为什么是乘不是加?把牌摆成长方 形就看明白了20:
A 2 3 4 5 6 7 8 9 10 J Q K ← 13 列
红桃 ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
黑桃 ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
方片 ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
梅花 ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
↑ 4 行
图说:每一张牌都是「一个花色 + 一个级别」的一次配对。
4 行 × 13 列 = 52 个格子,一个不多一个不少。
这就是乘法法则:两堆东西两两配对,配出来的总数是两堆个数相乘21。
认出它的信号词是「分别」: 「4 种花色分别有 13 张」—— 一见到「每一类分别有几个」,往往就是乘法22。
再看一个同类的:三个骰子并排摆成一个三位数,能摆出多少个? 第一个骰子 6 种,对每一种第二个又有 6 种,对每一种第三个还有 6 种, 所以 6 × 6 × 6 = 216 个23。
7. 第四条:一样东西重复 n 次,就连乘 n 个
这一节是主走查的最后一步,也是全书一条重要伏笔的起点。
32 个灯泡排成一排,每个都能亮或灭。一共有多少种亮灭花样?24
一个灯泡 2 种;两个灯泡 2 × 2 = 4 种;三个灯泡 2 × 2 × 2 = 8 种…… 32 个灯泡就是 32 个 2 连乘:
2 × 2 × … × 2 = 2³² = 4 294 967 296 ≈ 42.9 亿种
└─── 32 个 ───┘
42.9 亿种25。这是主走查的第四步,走完了。
这个数值得停一下:32 个灯泡,每个只有两种状态, 合起来的花样有 42.9 亿种——把全世界的人都叫来一人认领一种, 还得两个人合领一种才够分(世界人口约 81 亿。 这个对照是我们加的,书里只给了 42.9 亿这个数;人口是来自通用知识的约数)。
原书还点出了一件程序员该认出来的事: 32 个灯泡的亮灭花样数,和 32 位二进制能表示的数的总数是同一个数26—— 因为每一位不是 0 就是 1,正好是一个灯泡。 通常 n 位二进制能表示 2ⁿ 个数,这是程序员应掌握的基本知识27。
伏笔在这里:从 1 个灯泡到 32 个灯泡,数量从 2 涨到 42.9 亿。 每多一个灯泡,花样就翻一倍。 这条性质在第 13 章会变成全书最要紧的一条界。
8. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 植树问题答 11 棵 | 给了图,并点明 10 是间隔数不是棵数 |
| 加法法则要求两堆不重 | 给了反例(灯泡那道题),不是空口约定 |
| 容斥原理 | 给了完整走查(6 + 4 − 2 = 8)+ 一张分区图 |
| 乘法法则 | 给了长方形排列图,让「为什么是乘」看得见 |
| 「计数方法就是为了避免逐一计数而存在的」 | 是作者的总结,原文用的就是这个说法 |
判断(我们的,不是书里的):这一章最容易被跳过,却是错得最贵的一章。 数错一次的代价,在纸上是重算一遍,在代码里是一个越界、一次少发一条消息、 一份对不上的账。 值得记的不是四条法则本身(每一条都只有一行),是每条法则的前提: 加法要不重、容斥要先找出共有的、乘法要「分别有」。 如果错,会错在: 这些法则在实际业务里的难点往往不在算,在于 「这两堆到底有没有重叠」这个业务问题本身没人说得清。 判据是:你能不能一句话说出「共有的那部分是什么」。
这一章的边界:
- 只讲了两堆的容斥;三堆以上的容斥(加加减减再加回来)原书没讲;
- 没有讲 「怎么确认自己没漏没重」的系统方法,靠的是「认清性质」这条经验;
- 组合与排列不在这一章(第 10 章讲);
- 没有讲概率——这一章数的是「有多少种」,不是「有多大可能」;
- 32 位那个数只是顺带一提,原书没有展开讲整数的表示范围与溢出。
9. 可带走的
- 10 米路每隔 1 米种树是 11 棵——10 是间隔数,不是棵数;别忘了 0 那个位置;
- 同一道题的另一件外衣:100 个数据从 0 编号,最后一个是 99;
- 数数 = 把要数的东西和整数一一对上;出错方式只有漏和重两种;
- 东西一多就别用手数,改找「对应规则」——而规则要从对象的性质里读出来;
- 加法法则:两堆合起来 = 各自相加,前提是两堆不重;
- 容斥原理:有重叠时,先加起来再减掉共有的(6 + 4 − 2 = 8);难点在「共有的是什么」;
- 乘法法则:见到「每一类分别有几个」,就是乘(4 × 13 = 52);
- 同一件事重复 n 次,就是 n 个数连乘:32 个灯泡是 2³² = 42.9 亿种;
- n 位二进制能表示 2ⁿ 个数——它和 n 个灯泡的亮灭花样是同一个数。
10. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 植树问题 | 第5章 排列组合 | text/10-ch05.txt:70(搜「因此，需要 11 棵树」) · :85(搜「而是「树与树的间隔数」」) |
| 从 0 开始编号 | 第5章 排列组合 | text/10-ch05.txt:105(搜「最后的数据为 n − 1 号」) · :106(搜「很少有人答错」) |
| 数数是什么、漏与重 | 第5章 排列组合 | text/10-ch05.txt:115(搜「将计数对象与整数对」) · :48(搜「计数时必须要注意的是」) · :56(搜「对应规则」) |
| 认清计数对象的性质 | 第5章 排列组合 | text/10-ch05.txt:116(搜「认清计数对象的性质」) · :128(搜「使用变量 n 将问题抽象出来」) |
| 加法法则 | 第5章 排列组合 | text/10-ch05.txt:160(搜「数字牌 10 张，加上花牌 3 张」) · :164(搜「加法法则就是将无」) · :178(搜「加法法则只在集合中没有重复元素的条件下成立」) |
| 容斥原理 | 第5章 排列组合 | text/10-ch05.txt:200(搜「2 的倍数有 2, 4, 6, 8, 10, 12」) · :204(搜「亮灯的牌数为 6 + 4 − 2 = 8」) · :223(搜「就是容斥原理」) |
| 乘法法则 | 第5章 排列组合 | text/10-ch05.txt:247(搜「4 × 13 = 52」) · :266(搜「遇到这种「分别有」的情况」) · :268(搜「这里所用的是乘法法则」) |
| 三个骰子、32 个灯泡 | 第5章 排列组合 | text/10-ch05.txt:310(搜「6 × 6 × 6 = 216」) · :326(搜「4 294 967 296」) · :335(搜「n 位 2 进制数可以表示的数的总数」) |