程序员的数学3


CHAPTER 6 第 6 章 递 归 ——自己定义自己 142 程序员的数学 课前对话◎◎ 学生: GNU是什么的缩写? 老师:是“GNU is Not UNIX”的缩写。 学生:啊?那第1 个单词 GNU 是什么的缩写呢? 老师:那也是“GNU is Not UNIX”的缩写。 即“GNU is Not UNIX”is Not UNIX。 学生:“我想问的是这句话的第1 个单词 GNU 是什么的缩写……” 老师:那还是“GNU is Not UNIX”的缩写。 “‘GNU is Not UNIX’is Not UNIX”is Not UNIX。 学生:没有个头啊…… 老师:其实GNU 就包含了全部。 本章学习内容 本章我们学习递归。递归是一种奇妙的思考方法,它“使用自己来定义自己”。无论是 数学还是编程都经常使用递归。 首先,通过汉诺塔谜题让大家对递归有一个初步印象。然后,以阶乘、斐波那契数列 (Fibonacci Sequence)、帕斯卡三角形(Pascal’sTriangle) a 为例,学习递归和递推公式。最 后介绍以递归形式描画递归图形的分形图(fractale)。 本章,我们练习从复杂逻辑中找出递归结构。 汉诺塔 “汉诺塔”是一个由数学家爱德华·卢卡斯(Edouard Lucas) 于 1883 发明的游戏。该 游戏非常著名,或许您已有所了解。 思考题(汉诺塔) 有三根细柱(A、B、C)。A 柱上套着 6 个圆盘。这些圆盘大小各异,按从大到小的顺 ① 又称杨辉三角形、贾宪三角形。——译者注 143第 6 章 递归——自己定义自己 序自下而上摆放(图 6-1)。 ABC 图6-1◎ ◎汉诺塔 现在要把套在 A 柱上的 6 个圆盘全部移到 B 柱上。并且在移动圆盘时须遵守下述规则。 一次只能移动柱子最上端的一个圆盘。·· 小圆盘上不能放大圆盘。·· 将 1 个圆盘从一根柱子移到另一根柱子,算移动“1 次”。那么,将 6 个圆盘全部从 A 移到 B 最少需要移动几次呢? 提示:先从小汉诺塔着手 一开始就考虑 6 个圆盘的话头脑会混乱,所以我们先缩小问题的规模,从 3 个圆盘开 始思考。即暂不考虑 6 个圆盘的“6 层汉诺塔”,而是先找出“3 层汉诺塔”的解法(图 6-2)。 图6-2◎ ◎3层汉诺塔(3个圆盘的汉诺塔) ABC 经过多次尝试我们能找到图 6-3 所示的解法,移动 7 次可解决问题。 144 程序员的数学 图6-3◎ ◎3层汉诺塔的解法(移动7次) A A BC BC C AC B AB AB ① ② ③ ④ ⑤ ⑥ ⑦ 145第 6 章 递归——自己定义自己 仔细思考“3 层汉诺塔”的解法应该就能找到解决“6 层汉诺塔”问题的方法了。如果 不明白的话,请再思考一下“4 层汉诺塔”和“5 层汉诺塔”。 在来回移动圆盘的过程中,你一定会觉得“在重复做相似的事情”。之所以会产生这种 感觉是因为我们有“发现规律的能力”。这种感觉很重要。 例如,请比较图 6-4 中的①②③和⑤⑥⑦(图 6-4)。 ①②③中,移动 3 次将 2 个圆盘从 A 柱移到了 C 柱。·· ⑤⑥⑦中,移动 3 次将 2 个圆盘从 C 柱移到了 B 柱。·· 图6-4◎ ◎发现移动2个圆盘的规律 CA BA B C 从A到C移动3次 2层汉诺塔 从C到B移动3次 2层汉诺塔 ①②③ ④ ⑤⑥⑦ 虽然移动的目的地不同,但这 2 个动作是非常相似的。而且这种“移动 2 个圆盘”的 动作就是“2 层汉诺塔”的解法。以上就是提示内容,现在你能求出“6 层汉诺塔”的移动 次数了吗? 146 程序员的数学 思考题答案 “6 层汉诺塔”可以通过以下步骤求出。 (1)首先,将 5 个圆盘从 A 柱移到 C 柱(解出 5 层汉诺塔) (2)然后,将 6 个之中最大的圆盘从 A 柱移到 B 柱 (3)最后,将 5 个圆盘从 C 柱移到 B 柱(解出 5 层汉诺塔) 图6-5◎ ◎汉诺塔的解法 AC(1) 解出5层汉诺塔 AB(2) 移动最大的圆盘 BC(3) 解出5层汉诺塔 (1)和(3)所做的无非就是“5 层汉诺塔”的解法。为了解出“6 层汉诺塔”,需要 147第 6 章 递归——自己定义自己 用到“5 层汉诺塔”的解法。只要解出“5 层汉诺塔”,“6 层汉诺塔”就能迎刃而解。而且 这是移动次数最少的解法。为什么这么说呢?因为要把最大的圆盘从 A 柱移到 B 柱,就必 须将上面的 5 个圆盘都先移到 C 柱。 用同样的思路也可以解决“5 层汉诺塔”。例如,将 5 个圆盘从 A 柱移到 B 柱的步骤 如下: (1)首先,将 4 个圆盘从 A 柱移到 C 柱(解出 4 层汉诺塔) (2)然后,将(5 个之中)最大的圆盘从 A 柱移到 B 柱 (3)最后,将 4 个圆盘从 C 柱移到 B 柱(解出 4 层汉诺塔) “4 层汉诺塔”、“3 层汉诺塔”……也是同样的解法。 “1 层汉诺塔”只要移动 1 次圆盘 就完成了。 通过这种思考方式,我们可以总结出“n 层汉诺塔”的解法。 以下,我们不使用 A、B、C 这三根柱子的具体名称,而将其设为 x、y、z。因为 x、y、 z 在不同情况会不固定地对应 A、B、C 中的某一个。x 为起点柱、y 为目标柱,z 为中转柱。 “解出 n 层汉诺塔”的步骤,即“利用 z 柱将 n 个圆盘从 x 柱转移至 y 柱”具体如下。 将 n 个圆盘从 x 柱,经由 z 柱中转,移到 y 柱(解出 n 层汉诺塔)时:   当 n = 0 时,     不用做任何动作。   当 n > 0 时, 首先,将·· n-1 个圆盘从 x 柱,经由 y 柱中转,移到 z 柱(解出 n-1 层汉诺塔)。 然后,将 1 个圆盘从·· x 柱移到 y 柱。 最后,将·· n-1 个圆盘从 z 柱,经过 x 柱中转,移到 y 柱(解出 n-1 层汉诺塔)。 从以上步骤可知,为了解出 n 层汉诺塔,要使用“n-1 层汉诺塔”的解法。 那么,我们就将解出“n 层汉诺塔”所需的最少移动次数表示为 H(n) 例如,移动 0 个圆盘的次数为 0,那么 H(0) = 0 148 程序员的数学 而移动 1 个圆盘的次数为 1,那么 H(1) = 1 根据解 n 层汉诺塔所用的步骤,可以将移动次数 H(n) 的式子写成 0H(n)= (n=0时) 按照下述方式,思考 n = 1,2,3…时的式子可能更容易理解。 H(n) H(n-1) H(n-1)1= ++ 解出n层汉诺塔的移动次数 解出n-1层汉诺塔的移动次数 解出n-1层汉诺塔的移动次数移动最大的圆盘的次数 我们将这种 H(n) 和 H(n-1) 的关系式称为递推公式(recursion relation, recurrence)。 H(0) 是已知的,由 H(n-1) 构成 H(n) 的方法也是已知的,因此只要依次计算就能求出 “6 层汉诺塔所需移动次数”,即 H(6)。 H (0) = 0 H (1) = H (0)+1+H (0) = H (2) = H (1)+1+H (1) = 0+1+0 1+1+1 H (3) = H (2)+1+H (2) = 3+1+3 H (4) = H (3)+1+H (3) = 7+1+7 H (5) = H (4)+1+H (4) =15+1+15 =1 =0 =3 =7 =15 =31 =63H (6) = H (5)+1+H (5) =31+1+31 答案:63 次。 求出解析式 从上面的 H(0),H(1),…,H(6) 的结果,可以抽象出 H(n)。即可以只使用 n 来表示 H(n)。 也就是找出生成以下数列的算式,   0,1,3,7,15,31,63,… 直觉敏锐的人或许已经找到了下述规律 149第 6 章 递归——自己定义自己 0 = 1 - 1 1 = 2 - 1 3 = 4 - 1 7 = 8 - 1 15 = 16 - 1 31 = 32 - 1 63 = 64 - 1 即可以用下式表达 H(n) = 2n - 1 这种只使用n表示H(n)的式子叫做解析式,可以用数学归纳法来证明该解析式的正确性。 解出汉诺塔的程序 前面所示的“解出 n 层汉诺塔”的步骤,已经相当于程序的伪代码了。整理至此,用 C 语言编写汉诺塔解法的程序也就相当简单了。 代码清单6-1  汉诺塔解法的程序 #include #include void hanoi(int n, char x, char y, char z); void hanoi(int n, char x, char y, char z) { if (n ==0) { /* 什么也不做 */ } else { hanoi(n-1, x, z, y); printf("%c->%c, ", x, y); hanoi(n-1, z, y, x); } } 150 程序员的数学 int main(void) { hanoi(6, 'A’, 'B', 'C'); return EXIT_SUCCESS; } _______________________________________________________________________________ 该程序会输出 “6 层汉诺塔”的解决步骤,具体如下。 A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B, C->B, C->A, B->A, C->B, A->C, A->B, C->B, A->C, B->A, B->C, A->C, B->A, C->B, C->A, B->A, B->C, A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B, C->B, C->A, B->A, C->B, A->C, A->B, C->B, C->A, B->A, B->C, A->C, B->A, C->B, C->A, B->A, C->B, A->C, A->B, C->B, A->C, B->A, B->C, A->C, A->B, C->B, C->A, B->A, C->B, A->C, A->B, C->B, 数一下,确实是 63 次。 找出递归结构 在此,我们梳理一下汉诺塔的解题思路。 我们在解“6 层汉诺塔”时,先试着解出了稍为简单的 3 个圆盘的 “3 层汉诺塔”。然后, 为了找出更具有普遍性的解决办法,又使用了以下方法。 【使用递归来表示】找出借助 “n-1 层汉诺塔”来解“n 层汉诺塔”的步骤。 【递推公式】使用“n-1 层汉诺塔”的移动次数来表示“n 层汉诺塔”的移动次数。 综上所述,我们以 使用 n-1 层汉诺塔,来表示 n 层汉诺塔 151第 6 章 递归——自己定义自己 的观点来考虑问题。 那么,下面的内容非常重要,请仔细阅读。 假设现在碰到了一个难题。我们十分清楚“简单问题易解,复杂问题难解”的道理。 所以这时,我们要联想到汉诺塔,进行如下思考。 “能将复杂问题转换为较为简单的同类问题吗?” 这就是递归的思维方式。 对于汉诺塔来说,就是将 n 层汉诺塔转换为 n-1 层汉诺塔的问题,即在问题中找出递 归结构。虽然暂未解决给定的问题,但是要找出同类的简单问题,并将它当做“已知条件” 来运用。 n层汉诺塔 n-1层汉诺塔 n-1层汉诺塔 1层汉诺塔 发现递归结构 如果找到了这种递归结构,接下来就根据递归结构建立递推公式。 找出递归结构并建立递推公式,是相当重要的一环。如果能够总结出解析式自然最为 便捷,不过若找不到解析式,只建立递推公式也是非常有用的。因为它是得出具体数字的 线索,同时也能帮我们把握问题的本质。 汉诺塔的问题就聊到这里,我们带着“找出递归结构”的思路,进入下一节内容。 再谈阶乘 我们在第 5 章中介绍过阶乘。本节,我们再来谈谈阶乘的递归定义。 152 程序员的数学 阶乘的递归定义 在第 5 章中,我们将 n 的阶乘 n !定义如下: n! = n×(n-1)×(n-2)×…×2×1 但按照这个定义,“0 的阶乘”意义不明确。因此,另外定义了 0! = 1。 本章,我们要如下递归地定义阶乘。这可称为阶乘的递推公式。这样的定义既能明晰 0! 的值,又能省略上面式子中的“…”部分。 n×(n-1)! 1 n!= (n=0时) 之所以将它称作递归定义是因为“它使用了阶乘 (n-1)! 来定义阶乘 n!”。你能发现定义 中出现的下述递归结构吗? n! (n-1)!n 发现递归结构 × 该式虽然使用阶乘自身来进行定义,但却不会循环无解。对于 0 以上的任一整数,n! 的定义都很明确,因为使用了比 n! 低一层的(n-1)! 来定义 n! 例如,从阶乘的递归定义出发来看一下 3 !。通过定义可知 3! = 3×2 ! 再根据递归定义展开右边的 2 !可得 2! = 2×1 ! 继续根据递归定义展开 1 !可得 1! = 1×0 ! 最后根据“n=0 时”的定义可得 0! = 1 将以上结果全部结合起来,如下所示 153第 6 章 递归——自己定义自己    -13!=3×2×1× 0!的展开结果 1!的展开结果 2!的展开结果 至此,大家理解为什么将 0! 定义为 1 了吧。若 0! 不是 1,就无法顺利进行上述递归定义。 另外,大家是否发现阶乘的递归定义和第 4 章学过的数学归纳法比较类似? n=0 时相 当于数学归纳法的步骤 1(基底),n ≥ 1 时相当于步骤 2(归纳)。若用多米诺骨牌来打比方, “正确地定义 0!”就相当于“确保推倒第 1 张多米诺骨牌”。 思考题(和的定义) ◆思考题 假设 n 为 0 以上的整数,请用递归方式定义从 0 到 n 的整数之和。 ◆思考题答案 若将从 0 到 n 的整数之和写作 S(n),则 S(n) 可定义如下。 0 n+S(n-1)S(n)= (n=0时) (n=1,2,3, 时) ●解析式 其实 S(n) 的解析式,我们在讲解高斯的断言时已经做过介绍。 2S(n)= n×(n+1) 递归和归纳① 上 a一节我们提到阶乘的递归定义和数学归纳法相似。实际上,递归(recursion)和归纳 (induction) 的本质上是相同的,都是“将复杂问题简化”。例如,第 4 章中我们用代码清单 4-1 的 C 语言表示了数学归纳法的证明,其实也可以像代码清单 6-2 那样以递归的方式来写 ① 本节内容,参考Paul Hudak的The Haskell School of Expression (11.1 Induction and Recursion)。 154 程序员的数学 prove 函数。 代码清单6-2  以递归方式使用prove函数来证明数学归纳法 void prove(int n) { if (n == 0) { printf(" 根据步骤 1, 得出 P(%d) 成立。\n", n); } else { prove(n - 1); printf(" 根据步骤 2,可以说“若 P(%d) 成立,则 P(%d) 也成立”。\n", n-1, n); printf(" 因此,可以说“P(%d) 是成立的”。\n", n); } } 递归和归纳,只是方向不同。“从一般性前提推出个别性结论”的是递归(recursive) 的思想。而“从个别性前提推出一般性结论”的是归纳(inductive)的思想。 斐波那契数列 在阶乘的递归定义中,使用(n-1)!来定义 n!。在汉诺塔问题中,则利用“n-1 层汉 诺塔”来解出“n 层汉诺塔”。大家已经基本掌握 “递归”了吧?那么,接下来我们就来思 考一下更为复杂的递归。 思考题(不断繁殖的动物) ◆思考题 有一种动物,它出生 2 天后就开始以每天 1 只的速度繁殖后代。假设第 1 天,有 1 只这样的动物(该动物刚出生,从第 3 天起繁殖后代)。 到第 11 天,共有多少只? 155第 6 章 递归——自己定义自己 ◆提示 按顺序思考,找出规律。 【第 1 天】只有 1 只动物。 【第 2 天】有 1 只动物,还没繁殖后代。合计 1 只。 【第 3 天】第 1 天的 1 只动物,繁殖 1 个后代。合计 2 只。 【第 4 天】第 1 天的 1 只动物,又繁殖 1 个后代。      第 3 天出生的那只动物还没繁殖后代。合计 3 只。 【第 5 天】第 1 天和第 3 天出生的 2 只动物又各繁殖 1 个后代。      第 4 天出生的 1 只动物还没繁殖后代。合计 5 只。 我们将目前为止的思考结果画成图(图 6-6)。 图6-6◎ ◎第1天至第5天的生物数 第1天 第2天 第3天 第4天 第5天 1只 1只 2只 3只 5只 进行归纳时,不用直接想“第 n 天共有几只”,可如下思考: 第·· n-1 天出生的动物,在第 n 天还活着。 并且,第·· n-2 天以前出生的动物,在第 n 天会繁殖 1 个后代。 这样就能总结出递推公式。 156 程序员的数学 ◆思考题答案 在第 n 天时,“昨天,即第 n-1 天以前繁殖的动物”都活着。而且,“前天,即 第 n-2 天以前出生的动物”会繁殖 1 个后代。因此,若设第 n 天的动物总数为 F(n),则 F(n)=F(n-1)+F(n-2) (n 为 3,4,…) F(n) F(n-1) F(n-2) 第n天的动物数 第n-1天前的动物数 第n-2天前出生的动物数 =+ 在这里,为了让 F(2) = F(1)+ F(0) 成立(即让 n=2 时,以上递推公式成立),定义 F(0)=0。 此外,将第 1 天的 1 只动物用 F(1)=1 表示。整理可得以下递推公式 0 1F(n)= F(n-1)+F(n-2) (n=0时) (n=1时) (n=2,3,4, 时) 总结出了递推公式之后,我们就可以从 n=0 开始计算 F(n) 的值了。 F(0) F(1) F(2)=F(1)+F(0)= 1+ 0 F(3)=F(2)+F(1)= F(4)=F(3)+F(2)= F(5)=F(4)+F(3)= F(6)=F(5)+F(4)= F(7)=F(6)+F(5)= F(8)=F(7)+F(6)= F(9)=F(8)+F(7)= F(10)=F(9)+F(8)= F(11)=F(10)+F(9)= 1+ 1 2+ 1 3 =1 =0 =1 =2 =3 =5 =8 =34 =55 =21 =13 =89 + 2 5+ 3 8+ 5 13+ 8 21+13 34+21 55+34 F(0) F(1) F(2)=F(1)+F(0)= 1+ 0 F(3)=F(2)+F(1)= F(4)=F(3)+F(2)= F(5)=F(4)+F(3)= F(6)=F(5)+F(4)= F(7)=F(6)+F(5)= F(8)=F(7)+F(6)= F(9)=F(8)+F(7)= F(10)=F(9)+F(8)= F(11)=F(10)+F(9)= 1+ 1 2+ 1 3 =1 =0 =1 =2 =3 =5 =8 =34 =55 =21 =13 =89 + 2 5+ 3 8+ 5 13+ 8 21+13 34+21 55+34 答案:89 只。 157第 6 章 递归——自己定义自己 到第 11 天为止的繁殖状况如图 6-7 所示,其中 表示动物( 表示后代)。这个图有种不 可思议的美感!从中也可看出动物数量呈爆发式增长。 图6-7◎ ◎第11天为止的繁殖状况 第1天 第2天 第3天 第4天 第5天 第6天 第7天 第8天 第9天 第10天 第11天 从图 6-7 中找得到“递归结构”了吗?如下图所示,图本身还包含了一个更小的图。 不过,它和汉诺塔有所不同,要注意在 n 层中,既包含 n-1 层又包含 n-2 层。 n层 n-1层 n-2层 发现递归结构 斐波那契数列 问题中出现的数列 0,1,1,2,3,5,8,13,21,34,55,89,… 是在 13 世纪由数学家斐波那契(Leonardo Fibonacci, 1170 — 1250)发现的,因此被命名为 斐波那契数列。a ① 也常以1开头,如1,1,2,3,5,… 158 程序员的数学 斐波那契数列会出现在各种问题中。下面举几个例子。 ●摆砖头 现要将 1×2 大小的砖头摆放成长方形阵列。并规定该长方形的纵长必须为 2。假设长 方形的横长为 n,运用斐波那契数列则砖头的摆法为 F(n+1) 种。 图6-8◎ ◎用1×2大小的砖头摆放成纵长为2,横长为n的长方形阵列 1 2 3 4 5 n=0 1种 1种 1种 3种 5种 8种 图6-9◎ ◎找出砖头摆法的规律 之后的砖头摆法和上1种情况相同 之后的砖头摆法和上2种情况相同 原因很简单。如图 6-9 所示,横长为 n 的摆法就是以下两项相加之和。 左边竖立放置 1 块砖头时 , 右边砖头·· ((n-1) 块 ) 的摆法情况数。 左边横叠放置 2 块砖头时 , 右边砖头·· ((n-2) 块 ) 的摆法情况数。 159第 6 章 递归——自己定义自己 这个加法计算,正好就是斐波那契数列的递推公式。 请注意,为了让递推公式成立,将 1 块砖头都没有的摆法(n=0)算作“1 种”情况。 ●创作旋律 假设现在要用4分音符和2分音符打拍子来创作节奏。2分音符的时值等于2个4分音符。 即 4 分音符打 2 拍的时间只能打 1 拍 2 分音符。 若将4分音符打n拍的时间,用4分音符和2分音符来填充,则可以打出F(n+1)种节奏。 原因和前面摆砖头相同。n 拍时的情况数,是以下 2 项情况数相加的结果(图 6-10) 先打 4 分音符,剩余部分为·· n-1 拍时的情况数。 先打 2 分音符,剩余部分为·· n-2 拍时的情况数。 除此以外,在鹦鹉螺的内壁间隔、葵花种子的排法、植物枝叶的长法、以及“一次走 1 阶或 2 阶,爬 n 层阶梯的方法”等问题中,都能看到斐波那契数列的身影。 1 2 3 4 5 0n= 1种 1种 2种 3种 5种 8种 图6-10◎ ◎用4分音符和2分音符打拍子来创作节奏 帕斯卡三角形 什么是帕斯卡三角形 请见图 6-11。这个图形就叫帕斯卡三角形 a。 ① 又称杨辉三角形。——编者注 160 程序员的数学 1 11 1 1 1 1 2 3 4 3 6 10 4 10 20 1 1 1 5 156 1 1 1 5 615 图6-11◎ ◎帕斯卡三角形 在帕斯卡三角形中,每个数字都是上方与它相邻的两数之和。图 6-12 中,用箭头表示 出两数的相加方向。 图6-12◎ ◎帕斯卡三角形(用箭头表示两数的相加方向) a a c c b b+ca+b 请动手画一下帕斯卡三角形,这样会有助于你理解“相邻两数之和”的意义。在三角 形的两端,加数只有 1 个(因此三角形左右两边全都是 1)。 帕斯卡三角形看似只是简单的加法计算练习,而实际上,这里出现的数字全都是第 5 章中提到的“组合数”。请见图 6-13。这里将帕斯卡三角形用 Ck n(从 n 个元素中选出 k 个的 组合总数)的形式来表示。 161第 6 章 递归——自己定义自己 图6-13◎ ◎用组合总数Ck n 的形式来表示帕斯卡三角形 C 0 0 C 0 1 C 0 2 C 0 3 C 0 4 C 5 5 C 5 6 C 1 1 C 2 2 C 2 3 C 2 4 C 2 5 C 2 6 C 3 3 C 3 4 C 3 5 C 3 6 C 4 4 C 4 5 C 4 6 C 5 5 C 5 6 C 6 6 C 1 2 C 1 3 C 1 4 C 1 5 C 1 6 将 Ck n 写成算式就是 n! (n-k)!k! ,其中出现了很多阶乘。而这可以仅通过反复计算“相邻 两数之和”来得出,着实让人大吃一惊吧! ●帕斯卡三角形中出现组合数的原因 那么,我们来探究一下,为什么帕斯卡三角形中会出现组合数呢? 我们先把帕斯卡三角形抛在一边,思考一下下面格子状的路线从起点到终点共有多少 种方法可走? 起点 终点 我们在起点开始的各个分叉点上标出“从起点开始到本分叉点有几条路线”。 162 程序员的数学 1 2 3 4 1 1 1 1 3 6 10 1 起点 终点 这个计算和画帕斯卡三角形时“上面两数相加”的计算是一样的。因为到达某分叉点 的情况数,就是到达它上面的 2 个分叉点的情况数之和(这是加法法则)。 那么,接着看下图。 R R R L L 起点 终点 从起点到终点,或左或右走下来的路线有多少条呢?到达终点前,要进行 5 次往右(R) 走,还是往左(L)走的判断。在 5 次判断中,必须不多不少地选择 3 次往右才能到达终点。 即路线的选法等于 5 中选 3 的组合。 C35 = =105! (5-3)!3! 这样就通过两种方法算出从起点到终点的路线数了。一种方法与帕斯卡三角形的原理 相同,即“相邻两数相加”。另一种是计算“n 中选 k 的组合数”方法。因为 2 种方法的计 算对象相同,所以结果应该也相同。由此可知,相邻两数相加得到的帕斯卡三角形,可以 用组合数来表示。 递归定义组合数 请看下面的式子。这是什么呢? 163第 6 章 递归——自己定义自己 Ckn C=+k-1 n-1 Ck n-1 这就是用 Ck n 表示帕斯卡三角形(图 6-13)。像下面那样画图描述可能更容易理解。相 邻两数相加,得出下一行的数。 Ckn Ck-1 n-1 Ck n-1 在上式中,又出现了 n 和 k 两个变量,看上去比较繁琐。不过从本章主题“递归”的 角度再看一下这个式子,有没有什么新的发现? 左边出现的是变量 n、k,而右边出现的是变量减 1, 如 n-1、k-1。这与汉诺塔和阶乘中 出现的递归定义模式非常相似。只要补上相当于基底的定义,就能构成“组合数的递归定 义”。我们来看一下。 设 n 和 k 都是整数,并且 0 ≤ k ≤ n。将 Ck n 定义如下,这就是组合数的递归定义。 Ckn= +C k-1 n-1 Ck n-1 1 (n=0或n=k时) (0
还剩28页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享pdf获得金币 ] 1 人已下载

下载pdf

pdf贡献者

martinLu

贡献于2018-06-20

下载需要 10 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf