您所在位置: 网站首页 / 离散数学课件-第3章-4.ppt / 文档详情
离散数学课件-第3章-4.ppt 立即下载
2024-08-16
约1.7万字
约136页
0
1.3MB
举报 版权申诉
预览加载中,请您耐心等待几秒...

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

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

预览

免费试读已结束,剩余 131 页请下载文档后查看

10 金币

下载文档

如果您无法下载资料,请参考说明:

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,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思考:关于这个难题有一个古老的传说,在汉诺有一
查看更多
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

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

文档大小:1.3MB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
全场最划算
12个月
199.0
¥360.0
限时特惠
3个月
69.9
¥90.0
新人专享
1个月
19.9
¥30.0
24个月
398.0
¥720.0
6个月会员
139.9
¥180.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用