




如果您无法下载资料,请参考说明:
1、部分资料下载需要金币,请确保您的账户上有足够的金币
2、已购买过的文档,再次下载不重复扣费
3、资料包下载后请先用软件解压,在使用对应软件打开
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,n3 和初始条件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思考:关于这个难题有一个古老的传说,在汉诺有一

ys****39
实名认证
内容提供者


最近下载