离散数学课件-第3章-4.ppt

1第三章计数技术
学习内容Introduction
Example一群细菌的数目每小时增加一倍。如果开始有5个细菌，在n小时末将有多少个细菌？
为了解决这个问题，令an是n小时末的细菌数。
因为细菌每一小时增加一倍，满足关系式
an=2an-1
这与初始条件a0=5一起唯一决定了an。
利用这一有用信息找出关于an的公式。递推与分治
RecurrenceandDivide-and-Conquer递推与分治
RecurrenceandDivide-and-Conquer递推关系
（RecurrenceRelations）Example1令{an}是一个序列，它满足递推关系an=an-1-an-2,n=2,3,4,…,且a0=3,a1=5,那么a2和a3是什么？

Solution：
从递推关系可以看出，a2=a1-a0=2且a3=a2-a1=2-5=-3Example2确定序列{an}是否为递推关系，an=2an-1-an-2,n=2,3,4,…,的解
。这里an=3n,n为非负整数。对an=2n和an=5也回答同一个问题。
序列的初始条件说明了在递推关系起作用的首项之前的那些项。
一个递推关系和初始条件一起提供了一个序列的递归定义，所以可唯一的确定这个序列。
只要使用足够多次，序列的任何一项都可以从初始条件开始通过递推关系求出。我们可以使用递推关系构造各种问题的模型。
Forexample

计算复利
计数岛上的兔子
确定汉诺塔难题的移动次数
计数具有确定性质的二进位串Example3复利假设一个人在银行的储蓄账户上存了10000美元，年复利是11%。那么在30年后账户上将有多少钱？当代入初始条件P0=10000，就得到公式
Pn=(1.11)n10000
我们可以使用数学归纳法验证它的正确性。
公式对n=0是正确的，这是初始条件的直接结果。
假定Pn=(1.11)n10000,那么由递推关系和归纳假设，
Pn+1=(1.11)Pn=(1.11)(1.11)n10000=(1.11)n+110000
这证明了对Pn的显式公式是正确的。
将n=30代入公式Pn=(1.11)n10000就证明了在30年后账上包含
P30=(1.11)3010000=228922.97美元。Example4兔子和斐波那契数考虑下面的问题，一对刚出生的
兔子（一公一母）被放到岛上。每对兔子出生后两个月才开始繁
殖后代。如图示，在出生两个月以后，每对兔子在每个月都将繁
殖一对新的兔子。假定兔子不会死去，找出n个月后关于岛上兔
子对数的递推关系。Solution：
用fn表示n个月后的兔子对数。我们将证明fn，n=1,2,3,…是斐波那契序列
的项。可以用递推关系建立兔子数的模型。
在第1个月末，岛上的兔子对数是f1=1.由于这对兔子在第2个月没有繁殖，
因此f2=1.
为找到n个月后的兔子对数，要把前一个月岛上的对数fn-1加上新生的对数
，而这个数等于fn-2,因为每对两个月大的兔子都生出一对新兔子。
因此，序列{fn}满足递推关系
F=fn-1+fn-2,n3
和初始条件f1=1和f2=1.
由于这个递推关系和初始条件唯一地确定了这个序列，因此n个月后岛上
的兔子对数由第n个斐波那契数给出。Example5汉诺塔19世纪后期由法国数学家埃德沃德.卢卡斯发明的一个流行的游戏叫做汉诺塔，它由安装在一个板上的3根柱子和若干大小不同的盘子构成。开始时，这些盘子按照大小的次序放在第一根柱子上，使得大盘子在底下。游戏的规则是：每一次把1个盘子从一根柱子移动到另一根柱子，但是不允许这个盘子放在比它小的盘子上面。游戏的目标是把所有的盘子按照大小的次序都放到第二根柱子上，并且将最大的盘子放在最底部。令Hn表示解n个盘子的汉诺塔问题所需的移动次数。建立一个关于序列{Hn}的递推关系。
Solution:
开始n个盘子在柱1.按照游戏规则我们可以用Hn-1次移动
将上边的n-1个盘子移到柱3.在这些移动中保留最大的盘子不
动。如下图所示。
然后我们用一次移动将最大的盘子移到第二根柱子上，我们可以再使
用Hn-1次移动将柱3上的n-1个盘子移动到柱2，把它们放到最大的盘子上
面，这个最大的盘子一直放在柱2的底部。
容易看出，使用更少的是不可能求解这个难题的。这就证明了
Hn=2Hn-1+1
初始条件是H1=1，因为依照规则一个盘子可以用1次移动从柱1移到柱2.
我们可以使用迭代方法求解这个递推关系。
Hn=2Hn-1+1
=2(2Hn-2+1)+1=22Hn-2+2+1
=22(2Hn-3+1)+2+1=23Hn-3+22+2+1
…
=2n-1H1+2n-2+2n-3+…+2+1
=2n-1+2n-2+…+2+1=2n-1思考：关于这个难题有一个古老的传说，在汉诺有一