离散第7讲 递归关系.ppt

第7讲 递归关系 回顾 定义3.5：集合{1，2，3，…，n}的全排列，使得每个数i都不在第i位上，称这样的排列为{1，2，3，…，n}的一个错置。 定理3.15：集合{1，2，3，…，n}的错置的总数(记为 Dn)是 约定D0 =1 。 定理3.16 回顾 (1) Dn = (n-1)(Dn-2+Dn-1) (2) Dn = nDn-1+(-1)n a1=i ai=1 证.(1) 设{1，2，3，…，n}的一个错置是a1a2…ak…an ，因为a1≠1，所以a1有n-1种取法。设a1=i (2≤i≤n)，分两种情况讨论： (1.1) ai=1 。这时取决于其余n-2个数的错置，这些错置的数目是Dn-2 。 (1.2) ai≠1 。这时取决于其余n-1个数的错置：“1不可放置在第i位，其它各数j不可放置在第j位”，这些错置的数目是Dn-1 。 因此，由加法原理和乘法原理Dn=(n-1)(Dn-2+Dn-1) 递归关系 Textbook Page 44 to 54 内容提要 递归关系 递归关系的定义和实例 用递归关系构造模型 用递归关系为实际问题建模 递归关系的迭代求解 常系数线性齐次递归关系的求解 什么是常系数线性齐次递归关系 常系数线性齐次递归关系的特征根求解方法 前言 有多少个n位二进制串不包含两个连续的0？ 递归关系(recurrence relation) 定义1：关于序列{an}的递归关系是一个等式，它把an用序列中排在an前面的一项或多项来表示。如果一个序列的项满足某个递归关系，这个序列就叫做该递归关系的解(或通项,通项公式)。 递归关系举例 确定序列{an}是否为递归关系an = 2an-1–an-2 (n=2,3,4,…)的解，这里an =3n，n是非负整数。若an =2n或an =5呢？ 说明 序列的初始条件说明了在递归关系起作用的首项之前的那些项 递归关系和初始条件唯一地确定一个序列，这是因为一个递归关系和初始条件一起提供了这个序列的递归定义 只要使用足够多次，序列的任意一项都可以从初始条件开始通过递归关系求出 但对于某些特定类型的序列，可以有更好的办法通过它的递归关系和初始条件来计算它的通项 用递归关系构造模型 例3.14 平面上n条直线两两相交，且没有任何三条直线交于一点，求共有多少个交点？ 用递归关系构造模型 复合利息。假设一个人在银行的账户上存了10000美元，复合年利息是11%。那么30年后账上将有多少钱？ 用递归关系构造模型 例3.15汉诺塔：游戏由3根柱子和64个大小不等的金盘组成。开始时，盘子按照大小次序放在第一根柱子上，大盘在下，小盘在上。游戏的规则是，每次把一个盘子从一根柱子移动到另一根柱子上，并且不允许放在比它小的盘子上。游戏的目标是把所有盘子按照大小次序原样搬到第二根柱子上，最大的盘子放在最下面。 用递归关系构造模型 用递归关系构造模型 兔子和费波那契（Fibonacci）数。一对（一公一母）刚出生的小兔子放到岛上，每对兔子出生两个月后开始繁殖后代，每对兔子每个月可以繁殖一对新的小兔子。假定兔子不会死去，n个月后岛上共有多少对兔子？ 递归关系的求解 在前面的几个问题中，除费波那契数之外的其它问题都可以在求出初始值和递归关系式后迭代求解，找出数列的通项公式。方法是： 首先利用递归关系式对关系式右边的表达式进行迭代，并推测解的公式 然后用数学归纳法证明得到的公式 费波那契数列不易迭代求解，但它有一种更系统的求解方法 常系数线性齐次递归关系 定义2（定义3.7）：形如H(n)=c1H(n-1)+c2H(n-2)+…+ckH(n-k) 的递归关系式叫做常系数线性齐次递归关系式。其中c1, c2,…, ck为常数， ck ≠0，k≤n 常系数——系数c1, c2,…, ck为不依赖于n的常数 线性——等式右边为序列项的倍数之和 齐次——所出现的各项都是H(i)的倍数 特征方程 递归关系式H(n)=c1H(n-1)+c2H(n-2)+…+ckH(n-k) 求解的基本方法是寻找形如an=rn的解，其中r是常数 得到 rn - c1rn-1 - c2rn-2 - … - ckrn-k = 0 rk - c1rk-1 - c2rk-2 - … - ck = 0 定义3 （P48） ：xk? c1xk-1 ? c2xk-2 ?… ? ck = 0称为递归关系式H(n)=c1H(n-1)+c2H(n-2)+…+ckH(n-k) 的特征方程，其根为该递归关系式的特征根 an=rn是递归关系的解，当且仅当r是其特征方程的根 常系数线性齐次递归关系的求解