斐波那契、帕斯卡与分形 — 同一把钥匙开的三把锁
这一章讲三件事: 一个要往回看两层的递推式长什么样; 帕斯卡三角形里那些数为什么正好是组合数; 以及递归不只能算数,还能画图。
它在全书链条里的位置: 第 11 章给了一把钥匙(找出小一号的自己)。 这一章拿它连开三把锁,是为了让你相信这不是汉诺塔专用的技巧。 顺便,这一章那串数会自己长得飞快——第 13 章要讲的正是这件事。 需要的基础: 第 11 章的递推公式;第 10 章的组合数。
1. 先看现象:一种动物,第 11 天有几只
有一种动物,出生 2 天之后就开始每天生 1 只后代。 第 1 天只有 1 只(刚出生,从第 3 天起才开始生)。第 11 天一共有多少只?1
正面的想法是跟踪每一只:谁哪天出生、谁哪天开始生……几天之后就乱了。
全章的主走查:第 11 天有几只
─────────────────────────────────────────────
§2 先数前五天 1、1、2、3、5
§3 看出结构 今天 = 昨天全活 + 前天那批各生一只
§4 写成递推式,算到 F(11) = 89
─────────────────────────────────────────────
图说:和第 11 章一样,先缩小规模、再找结构、再写递推式。
换的只有一处:这次要往回看两层,不是一层。
2. 先数前五天
这一节走主走查的第一步:老老实实数五天2。
| 第几天 | 发生了什么 | 合计 |
|---|---|---|
| 1 | 只有 1 只(刚出生) | 1 |
| 2 | 那 1 只还没到生育期 | 1 |
| 3 | 第 1 天那只生了 1 只 | 2 |
| 4 | 第 1 天那只又生 1 只;第 3 天出生的还没到生育期 | 3 |
| 5 | 第 1 天和第 3 天出生的各生 1 只 | 5 |
1、1、2、3、5。再往下数会越来越容易乱——这正是要找结构的信号。
3. 看出结构:今天 = 昨天全活着 + 前天那批各生一只
这一节是这一章的核心动作。
原书给 的思路是:别想「第 n 天一共几只」,想这两句3:
① 第 n−1 天(昨天)那些动物,今天都还活着 → 贡献 F(n−1) 只
② 第 n−2 天(前天)以前出生的那些,今天各生 1 只 → 贡献 F(n−2) 只
于是:F(n) = F(n−1) + F(n−2)
这是主走查的第二步。
为什么第二条是「前天」而不是「昨天」? 因为出生两天后才开始生—— 昨天新出生的那些还没到生育期,而前天以前就在的都到了。
和汉诺塔比一比,差别只有一处: 汉诺塔的 n 层只用到 n−1 层, 而这里的 n 层同时用到 n−1 层和 n−2 层4。 要往回看两层,所以落脚点也要给两个:F(0) 和 F(1)。
4. 定好落脚点,算到 89
这一节走完主走查。
F(1) = 1(第 1 天有 1 只)。那 F(0) 呢?第 0 天根本不存在。
原书的处理很值得看:为了让 F(2) = F(1) + F(0) 这条式子在 n = 2 时也成立, 就把 F(0) 定义成 05。
又是「值是被定义出来的」——准绳还是那条:让规则不分叉。 (第 01 章定义 10⁰、第 10 章定义 0!,用的都是这一条。)
于是可以一行行算上来6:
| n | 算式 | 结果 |
|---|---|---|
| 0 | —— | 0 |
| 1 | —— | 1 |
| 2 | 1 + 0 | 1 |
| 3 | 1 + 1 | 2 |
| 4 | 2 + 1 | 3 |
| 5 | 3 + 2 | 5 ← 和第 2 节手工数的一致 |
| 6 | 5 + 3 | 8 |
| 7 | 8 + 5 | 13 |
| 8 | 13 + 8 | 21 |
| 9 | 21 + 13 | 34 |
| 10 | 34 + 21 | 55 |
| 11 | 55 + 34 | 89 |
89 只。主走查走完了7。
这串数 0、1、1、2、3、5、8、13、21、34、55、89…… 叫斐波那契数列, 是 13 世纪的数学家斐波那契发现的8。
顺带看一眼它涨得多快:第 5 天 5 只,第 11 天 89 只——六天涨到近 18 倍。 原书的说法是:从图上也看得出动物数量呈爆发式增长9。(这条线通向第 13 章。)
5. 同一串数,在三个不相干的地方冒出来
这一节回答:这串数是这道繁殖题独有的吗。
不是。原书给了两个完全不相干的例子,答案都是同一串数10:
① 摆砖头。 用 1×2 的砖头摆一个高 2、长 n 的长方形,有几种摆法? 原因和繁殖题一模一样:最左边要么竖着放 1 块(右边还剩 n−1 的长度), 要么横着叠 2 块(右边还剩 n−2 的长度)——两种情况一加,正好是斐波那契的递推式11。
② 打拍子。 用四分音符(1 拍)和二分音符(2 拍)凑够 n 拍,有几种节奏? 同样的分法:先打一个四分音符,剩下 n−1 拍;先打一个二分音符,剩下 n−2 拍12。
原书还顺手列了一串:鹦鹉螺的内壁间隔、葵花种子的排法、植物枝叶的长法, 以及「一次走 1 阶或 2 阶,爬 n 层楼梯有几种走法」13。
共同点只有一个:每一步都只有两种选择,一种消耗 1、一种消耗 2。 认出这个形状,你就认出了斐波那契。
6. 第二把锁:帕斯卡三角形
这一节另起一处走查。
先看这个三角形14:
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
图说:每个数都是它上面相邻两个数之和(比如 6 = 3 + 3)。
两条边上的数都是 1,因为边上的位置只有一个数在它上面。
规则简单到不用记:上面相邻两数相加15。
但这些数不是随便的数——它们全都是第 10 章的组合数16。
| 第几行 | 那一行的数 | 对应的组合 |
|---|---|---|
| 第 5 行 | 1、5、10、10、5、1 | 5 选 0、5 选 1、5 选 2、5 选 3、5 选 4、5 选 5 |
第 10 章算过:五张牌取三张的组合是 10 种——它就在第 5 行第 4 个位置上。
这件事挺让人吃惊:组合数的公式里全是阶乘, 而这里只靠反复做「相邻两数相加」就得出来了17。
7. 为什么会是组合数:两条路算同一件事
这一节回答上一节留下的问题,而回答的办法很漂亮。
原书先把帕斯卡三角形放在一边,改问一道走格子的题: 从起点到终点,沿着格子往右下或左下走,有几条路?18
第一条算法:在每个岔路口标上「从起点到这里有几条路」。 到某个岔路口的路数 = 到它上面那两个岔路口的路数之和(第 09 章的加法法则)—— 这正是帕斯卡三角形的规则19。
第二条算法:走到终点要做 5 次「往右还是往左」的选择, 而其中必须不多不少地选 3 次往右。所以路数 = 5 选 3 的组合 = 1020。
两条算法,同一道题:
一路加上去 ────→ 10 条路
↑ 同一个数
5 选 3 的组合 ──→ 10 种
图说:因为算的是同一件事,所以结果必然相同。
于是「相邻两数相加」得到的那些数,就一定是组合数。
这是另起走查的落点:10 = 10,两条路对上了21。
8. 组合数也能写成递归定义
这一节把上一节的发现写成式子,并给出它的「意义」。
帕斯卡三角形的规则,用组合 数写出来是这样22:
从 n 个里选 k 个 = 从 n−1 个里选 k−1 个 + 从 n−1 个里选 k 个
左边是 n 和 k,右边是 n−1 和 k−1——这和汉诺塔、阶乘的形状一模一样23。 补上落脚点(k = 0 或 k = n 时结果是 1),这就是组合数的递归定义。
但式子看着还是抽象,所以原书接着问:这句话是什么意思? 代进 n = 5、k = 3,并且给五张牌起上名字 A 到 E24:
从 A、B、C、D、E 里选 3 张的取法
= 包含 A 的取法 + 不包含 A 的取法
= (A 已定,再从剩下 4 张里选 2 张) + (从剩下 4 张里选 3 张)
= 6 + 4 = 10
图说:盯住一张特定的牌 A,所有取法立刻被切成两堆:
含 A 的、不含 A 的。这两堆不重不漏,所以可以直接相加。
「盯住一样东西,把所有情况切成含它和不含它两堆」—— 这正是第 02 章那句「不重不漏地分两半」25。
而这也正是第 11 章那条找递归结构的动作:遮住一部分(那张 A), 看剩下的是不是小一号的同一道题26。是——只不过牌少了一张。
9. 第三把锁:递归还能画
这一节另起第二处走查。
递归不只能算数,还能画图。看一棵树27:
╲ ╱ 第 n 层的树枝:
╲ ╱ 向左伸一根、向右伸一根,
╲╱ 每根的末端再接第 n−1 层的树枝。
│
│ 第 0 层的树枝:什么也不画。
│
「第 n 层的树枝」的定义里用到了「第 n−1 层的树枝」—— 和汉诺塔一模一样,而落脚点同样是「什么也不做」28。
写成程序也是同一个形状:一个 if,上半是「什么也不画」,
下半是左转、画一根、递归画小一号的、退回来、右转、再来一遍29。
还有一个更漂亮的例子:谢 尔平斯基三角形—— 一个大三角形里套着三个小一号的自己,小的里面又套着更小的30。
而它和第 6 节那个帕斯卡三角形有一层意外的关系: 把帕斯卡三角形里的奇数和偶数涂成两种颜色,谢尔平斯基三角形就自己浮出来了31。 这类含有递归结构的图形,叫分形图32。
10. 作者的判断、我们的判断,以及这一章的边界
| 说法 | 书里给了什么 |
|---|---|
| 第 11 天 89 只 | 给了完整走查:五天手数 → 两句结构 → 递推式 → 逐行算到 89 |
| F(0) 定成 0 | 给了理由:为了让递推式在 n = 2 时也成立 |
| 摆砖头、打拍子也是这串数 | 给了理由(最左边两种放法),不是「巧合」 |
| 帕斯卡三角形里是组合数 | 给了证明:同一道走格子的题,两条算法必然同值 |
| 组合数递归式的「意义」 | 给了完整解释(含 A 的 + 不含 A 的),而不是只给式子 |
| 帕斯卡三角形涂色出谢尔平斯基三角形 | 只给了图和一句「非常有意思吧」,没有解释为什么 |
判断(我们的,不是书里的):这一章里最该学的是第 7 节那个动作—— 「同一件事换两条路算,结果必须相同」。 它不只是证明技巧:在工程里,同一个数用两条独立的路算一遍再对账, 是发现错误最有效的办法之一(对账、双写校验、灰度对比都是这一招)。 如果错,会错在: 两条路如果共用了同一个错误前提,对上了也不能说明对 ——这时「对账」只是把同一个错误算了两遍。 判据是:那两条路是不是真的互相独立。
这一章的边界:
- 没有讲斐波那契的解析式(它有一个带根号的封闭形式),原书刻意避开了;
- 没有讲用递归写斐波那契会有多慢(同一层被反复重算),这是实际编程里的大坑;
- 帕斯卡三角形涂色变成分形,原书只给了图,没有给理由;
- 分形只讲了「图形里含有小一号的自己」这一层,没有讲维数、自相似的严格定义;
- 海龟作图那一段依赖图形,转码后的文本里只剩下四个操作的名字。
11. 可带走的
- 别跟踪每一只,去找结构:今天 = 昨天全活着 + 前天那批各生一只;
- 这道题要往回看两层(n−1 和 n−2),所以落脚点要给两个;
- F(0) 定成 0,是为了让递推式在 n=2 时也成立——又一次「让规则不分叉」;
- 第 11 天 89 只;这串数叫斐波那契数列,13 世纪就有了;
- 认出它的形状:每一步只有两种选择,一种消耗 1、一种消耗 2; 摆砖头、打拍子、爬楼梯都是它;
- 帕斯卡三角形的规则只有一条:上面相邻两数之和;
- 里面的数就是组合数——证明办法是「同一道走格子的题,两条算法必然同值」;
- 组合数的递归定义读出来是:含某张特定牌的取法 + 不含它的取法;
- 递归也能画图:第 n 层的树枝末端接第 n−1 层的树枝,第 0 层什么也不画;
- 这类含递归结构的图形叫分形图;帕斯卡三角形按奇偶涂色就会浮出一个。
12. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 繁殖题与前五天 | 第6章 递归 | text/11-ch06.txt:415(搜「出生 2 天后就开始以每天 1 只的速度繁殖」) · :422(搜「【第 1 天】只有 1 只动物」) |
| 两句结构与递推式 | 第6章 递归 | text/11-ch06.txt:445(搜「第 n − 1 天出生的动物，在第 n 天还活着」) · :454(搜「F(n) = F(n − 1) + F(n − 2)」) |
| F(0) 的定法与逐行计算 | 第6章 递归 | text/11-ch06.txt:460(搜「定义」) · :477(搜「F(0)」) · :489(搜「答案：89 只」) |
| 斐波那契其人与爆发式增长 | 第6章 递归 | text/11-ch06.txt:522(搜「是在 13 世纪由数学家斐波那契」) · :491(搜「从中也可看出动物数量呈爆发式增长」) |
| 摆砖头与打拍子 | 第6章 递归 | text/11-ch06.txt:529(搜「运用斐波那契数列则砖头的摆法为」) · :550(搜「横长为 n 的摆法就是以下两项相加之和」) · :561(搜「则可以打出 F(n + 1) 种」) |
| 帕斯卡三角形 | 第6章 递归 | text/11-ch06.txt:588(搜「这个图形就叫帕斯卡三角形」) · :604(搜「每个数都是上方与它相邻的两数之和」) · :615(搜「这里出现的数全都是第 5 章」) |
| 走格子的两条算法 | 第6章 递归 | text/11-ch06.txt:657(搜「这个计算和画帕斯卡三角形时」) · :668(搜「必须不多不少地选择 3 次往右」) · :676(搜「这样就通过两种方法算出从起点到终点的路线数了」) |
| 组合数的递归定义与意义 | 第6章 递归 | text/11-ch06.txt:701(搜「这就是组合数的递归定义」) · :729(搜「包含 A 的组合数」) · :733(搜「通过是否包含 A 来兼顾完整性和排他性」) |
| 递归图形与分形 | 第6章 递归 | text/11-ch06.txt:787(搜「这个树枝有左右两个分叉」) · :845(搜「谢尔平斯基三角形」) · :858(搜「用颜色区分帕斯卡三角形中的奇数和偶数」) · :860(搜「称为分形图」) |