组合数学幻灯片51..ppt

§5.1 递归关系的建立 第五章 递 归 关 系 递归关系是组合数学的一个重要课题它不仅在几乎所有的数学分支中占有重要的地位，而且在计算机科学，特别是算法分析中有着广泛的应用。 在这一节，我们首先给出递归关系的定义然后用几个例子来说明是怎样建立递归关系的。 例如 第三章§3.3节中的错排数 Dn=(n-1)(Dn-1+Dn-2)(n=3,4,…)和关系式 都是递归关系。 设(a0,a1,…,ar,…)是一个序列，把该序列中的ar和它前面的几个ai(0≤ir)关联起来的方程称做一个递归关系 如果递归关系式(5.1)给出了初值D1=0,D2=1, 那么递归关系式(5.1)连同初值一起就唯一地确定了错排数序列 (D1,D2,D3,…)=(0,1,2,9,44,265,…)。 同样，对于递归关系式(5.2)，若给出初始值 a1=3，我们就能确定唯一的序列 (3,32,…,3r,…)。 由上面递归关系的例子可见，递归关系是计算序列中各项的有效工具。但如何建立递归关系呢?下面用几个实例来加以说明。 为方便起见，把式(5.1)和(5.2)连同它们的初值一起统一写成如下形式： 称这种形式为带初值的递归关系。 解：要求解这个问题，首先必须建立递归关系，然后求解递归关系即可。 在一个平面上有一个圆和n条直线，这些直线中的每一条在圆内都同其他的直线相交。如果没有三条的直线相交于一点，试问这些直线将圆分成多少个区域?  设这n条直线将圆分成的区域数为an， 如果有n-1条直线在圆内将圆分成an-1个区域，那么，再加入第n条直线与在圆内的其他n-1条直线相交。 显然，这条直线被n-1条直线在圆内分成n条线段，而每线段又将第n条直线在圆内经过的区域分成两个区域。 这样，加入第n条直线后，圆内就增加了n个区域。而对于n=0，显然有a0=1。于是对于每个整数n，可以建立如下带初值的递归关系： 求解递归关系式(5.3)(求解方法将在后几节中介绍)得 an=(n2+n+2)/2 这就是问题的解答。 (5.3) “Hanoi塔”问题是指：n个大小不 一的圆盘依半径的大小，从下而上的套在柱子A上。如图5-1所示。图见书83页 现要求将所有的圆盘从柱子A上全部转移 到柱子C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上， 且在转移过程中不允许出现大圆盘放在小圆盘上。 试问要转移多少次才能将柱子A上的n个圆盘全部转移到柱子C上去? 当n≥3时，要将柱子A上的n个圆盘全部转移到柱子C上，可以这样设想: 先把柱子A上的n-1个圆盘转移到柱子B上，这需要转移an-1次， 然后把柱子A上的最后一个大圆盘转移到柱子C上，显然这需要转移一次， 最后再把柱子B上的n-1个圆盘转移到柱子C上，这也需要转移an-1次。 解：设an表示从一根柱子上的n个圆盘全部转移到另一根柱子上的转移次数。 显然，a1=1,a2=3。 经过这些步骤后，所有A上的n个圆盘就全部转移到柱子C上。 由加法规则，这一共转移了2an-1+1次。于是可以建立如下带初值的递归关系： (5.4) 求解递归关系式(5.4)得 an=2n-1 这就是我们所需要的结果。 “Fibonacci兔子问题”也是组合数学中著名问题之一。 这个问题是指：从某一年开始时，把雌雄各一的一对兔子放入养殖场中，雌兔每月产雌雄各一的一对新兔。 从第二个月开始每对新兔也是每月产一对雌雄各一的兔子。 试问第n个月后养殖场中共有多少对兔子? 解：设第n个月开始时，养殖场中兔子的对数为Fn。并定义F0=1，显然有F1=1。 求解式(5.5)就得到我们所需要的答案。 (5.5) 这是因为，在第n-2个月开始就已经有的每对兔子在第n-1个月里都应生一对新的兔子。因此可以建立如下带初值的递归关系： 由于在第n个月开始时，除了有第n-1个月开始时养殖场中的全部兔子Fn-1外，还应该有Fn-2对兔子 利用式(5.5)可以推得(F0,F1,…,Fn,…)=(1,1,2,3,5,8,13,21,34,55,89,144,233,377,…) 常称Fn为Fibonacci数， (F0,F1,…,Fn，…)为Fibonacci序列。 Fibonacci序列在数学中是一个奇特而又常见的序列，它在算法分析中起着重要的作用。 可以证明，Fibonacci数具有以下性质： 1. 2. 3. 4. 在一个平面中，有