《高级计数PPT课件》由会员分享，可在线阅读，更多相关《高级计数PPT课件（64页珍藏版）》请在金锄头文库上搜索。
1、高级计数,离散数学,2,递归（推）关系,本章将对递归关系进行介绍。 递归关系可用于解决一些特定的计数问题。 递归关系是序列中第n个元素与它前若干个元素之间的关系。 由于递归关系和递归算法密切相关，因此递归关系可以很自然地用于递归算法分析。,建立序列中第n项与其前趋元素间的关系 递归算法的分析,3,4.1 递推关系基础,以5开始 给定了某一项，+3得到下一项,5 8 11 14 17 20 23,a1 =5 an = an-1 +3 n 2 a2 = a1 +3 = 5+3=8 a3 = a2 +3 = 8+3=11 递推关系是由数列第n项前的若干项确定第n项，并由此确定数列。,4,定义,关于序
2、列an的递推关系是一个等式， 将an用序列中前一项或多项，即由a0 , a1, . . . ， an-1中的一些或全部确定an的等式。如果一个序列的项满足递推关系，这个序列就叫做递推关系的解。 数列a0 , a1, . . .的初始条件是对数列的有限个元素给定的确定值。,例,令an是一个序列，它满足递推关系an=an-1-an-2, n=2,3,4且a0=3,a1=5, 求a2,a3 a2=a1-a0=5-3=2 a3=a2-a1=2-5=-3,5,例,确定an是否为递推关系an=2an-1-an-2, n=2,3,4，的解，其中an=3n,n是非负整数。 解：2an-1-an-2=2*3(n
3、-1)-3(n-2)=3n=an 若an=2n 2an-1-an-2=2*2n-1-2n-2=2n-2n-2an 若an=5，2an-1-an-2=2*5-5=5=an,6,4.1.3 用递推关系构造模型,7,投资$1000, 利息12% An 第n年底的总金额， An An = An-1 + (0.12) An-1 = 1.12An-1 n 1 A0=1000 A3 = 1.12A2 = 1.12*1.12A1 = 1.12*1.12 *1.12 A0 = 1.12 3 (1000) An = 1.12An-1 = 1.12 n (1000) 通项公式,8,例,投资$1000, 利息12%
4、An 第n年底的总金额， An An = An-1 + (0.12) An-1 = 1.12An-1 n 1 A0=1000 A3 = 1.12A2 = 1.12*1.12A1 = 1.12*1.12 *1.12 A0 = 1.12 3 (1000) An = 1.12An-1 = 1.12 n (1000) 通项公式,9,例 兔子与斐波那契数,一对刚出生的兔子放在岛上。每对兔子出生后两个月才开始繁衍后代。假设在出生后两个月后 ，每对兔子每个月都将繁衍一对新兔子。 Fibonacci级数递推关系fn = fn-1 + fn-2 n 3 初始条件 f1 =1 f2 =2,10,通项公式,递推关系
5、、递归算法、数学归纳法 三者的共同点是 ：将处理当前情况时的先验示例看做是已知的。递归关系利用序列中的先验值计算当前项的值；递归算法利用当前输入的较小示例来处理当前的输入；用数学归纳法证明命题的归纳步，总先假设命题的先验示例成立，进而证明当前命题成立。,11,算法,Input: n Output:第n年底的总金额 procedure interest(n) if n =0 then return (1000) return(1.12 * interest(n-1) end interest,12,Hanoi塔问题,令Hn表示解n个圆盘的汉诺塔问题所需要移动的次数。建立关于Hn 的递推关系 Hn
6、=2 Hn-1+1 H1=1 Hn=2n-1,13,Hanoi C1 = 1 Cn = 2Cn-1 +1 n 2 Cn = 2Cn-1 +1 = 2(2Cn-2 +1)+1 = 22 Cn-2 +2+1 = 23 Cn-3 + 22 +2+1 . . . = 2n-1 C1 + 2n-2 + 2n-3 + . . . + 22 +2+1 = 2n-1 + 2n-2 + 2n-3 + . . . + 22 +2+1 = 2n -1,例：对于不含2个连续0的n位二进位串的个数找出递推关系和初始条件。有多少个这样的5位二进制串？ 以1结尾的n位二进位串（不含2个连续0） 以0 结尾的n位二进位串（不
7、含2个连续0）,14,n-1位二进位串（不含2个连续0）,n-2位二进位串（不含2个连续0）,解： an=an-1+an-2 a1=2，a2=3,15,例：编码字的枚举 一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个0，就是有效的。例如 1 230 407 869有效，而120 987 045 608无效的。设an是有效的n位编码字的个数。找出一个关于an的递推关系。,16,an-1,an,n-1位无效编码字：10n-1-an-1,9an-1,解 an=9an-1+(10n-1-an-1) =8an-1+10n-1,17,18,4.2求解线性递推关系,数列a0 , a1, .
8、 . .的通项公式an 代入法 定义：一个k阶常系数 线性齐次递推关系： an=c1an-1+c2an-2 +ckan-k其中c1,c2,ck是实数，ck0 例： cn=1.12 cn-1是一阶线性齐次递推关系 fn=fn-1+fn-2是二阶线性齐次递推关系 an=2an-5是5阶线性齐次递推关系 an=an-1+an-12不是线性的； Hn=2 Hn-1+1 不是齐次的。,19,例,以下各项不是常系数线性齐次递推关系 an=an-1+an-12不是线性的； Hn=2 Hn-1+1 不是齐次的。 an = 3an-1 an-2 an - an-1 = 2n an = 3n an-1,20,4.
9、2.2 求解常系数线性齐次递推关系,写出an用a0 , a1, . . . , an-1的表示形式， 并不断用递推关系替代an-1 . . . ，最后得到一个与n有关，与a0 , a1, . . . , an-1无关的公式。,求解的基本方法：找形如an=rn的解 其中r 是常数 代入法,21,例,a1 = 2 an = an-1 +3 n 2 an = an-1 +3 an-1 = an-2 +3 an = an-1 +3= an-2 +3 +3= an-2 + 2*3 an-2 = an-3 +3 an = an-2 + 2*3 = an-3 +3 + 2*3 = an-3 +3 *3 an
10、 = an-k + k*3 (let k=n-1) an = a1 + (n-1)*3=2 + (n-1)*3,22,Sn = 2Sn-1 S0 = 1 Sn = 2Sn-1 = 2(2Sn-2 )= . . . =2n S0 =2n,23,一般方法,求解基本方法：找形如an=rn的解，其中r 是常数。 an=rn是递推关系an=c1an-1+c2an-2 +ckan-k的解，当且仅当 rn=c1rn-1+c2rn-2 +ckrn-k 即： rk-c1rk-1-c2rk-2 -ck=0 递推关系的特征方程 方程的解为特征根,24,定理1,设an = c1an-1 + c2 an-2是2阶常系数
11、线性齐次递推关系 设c1 ,c2 是实数, r1 ， r2是特征方程r2 - c1 *r - c2 = 0的两个不同的根,则存在b,d 使得an = b r1 n+ d r2 n, 序列an是递推关系的解。,求递推关系的显示表达式 an = an-1 +2an-2, 其中a0 = 2， a1 =7， 解：递推关系的特征方程是： r2-r-2=0 r1=2, r2=-1 因此an = b2n+d(-1)n 根据初始条件可得： b+d=2 2b-d=7 得出b=3,d=-1 因此an = 32n-(-1)n,25,26,an = 5an-1 - 6an-2 其中a0 = 7 a1 = 16,解：
12、递推关系的特征方程为： t2 - 5 t + 6 = 0 t=2, t=3 a n = b2n +d3n 是解 根据初始条件： 7 = a 0 = b20 +d30 =b+d 16 = a 1 = b21 +d 31 =2b+3d b=5, d= 2 因此：a n = 5*2n +2*3n,27,例,鹿群 n=0 :200 n=1 : 220 从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。,解：设dn为时间n时数目 d0=200， d1=220 dn - dn - 1 =2 (dn-1 - dn - 2 ) 递推关系：dn = 3dn - 1 - 2 dn
13、- 2 t2 - 3 t + 2 = 0r1 = 1， r2 = 2 dn = b r1 n+ d r2 n = b 1 n+ d 2n 200 = d0= b + d 220= d1= b + 2d b=180, d=20,dn = 180 + 20* 2n,28,例,求Fibonacci数列的通项公式 fn = fn-1 + fn-2 n3 f1 = 1, f2 = 1,29,Answer,t2 - t -1 = 0 fn = b t1 n+ d t2 n f1 = 1=b t1 + d t2, f2 = 1= b t1 2+ d t2 2 得b和d,30,定理 2,若r1 = r2 设a
14、n = c1an-1 + c2 an-2是2阶常系数线性齐次递推关系 a0 =c0, a1 =c1 r1 = r2 = r是t2 - c1 *t - c2 = 0的(同)根, 则存在b,d 使得an = b r n+ d n r n , n=0, 1, 2, . . .,31,例,dn = 4(dn - 1 - dn - 2 ) d0 = d1 =1,解：t2 - 4t +4 = 0 r1 = r2 = r=2 dn = b 2 n+ d n 2 n d0 = d1 =1 d0 =1= b 2 0+ d 0 2 0 = b d1 =1= b 2 1+ d 1 2 1 = 2 b + 2 d =
15、1 b =1， d = - dn = 2 n- n 2 n-1,例， an = 6an-1 -11 an-2 +6 an-3,其中a0=2,a1=5,a2=15 解：特征方程： r3-6r2+11r-6=0 特征根为：r1=1, r2=2, r3=3 则an = b*1n+d*2n+e*3n 根据初始条件： 2=b+d+e 5=b+2d+3e 15=b+4d+9e 得出b=1, d=-1, e=2 故而 an = 1-2n+2*3n,32,定理3,33,设 c1，c2，,ck是实数,特征方程 rk-c1rk-1-c2rk-2 -ck=0 有k个不同的根 r1,r2, rk 那么 an=b1r1
16、n+b2r2n,+bkrkn,4.2.3 常系数线性非齐次递推关系,34,形如：an=c1an-1+c2an-2 +ckan-k+F(n) 设 c1，c2，,ck是实数，F(n)是只依赖于n的函数 相伴的齐次递推关系,35,例： 非齐次递推关系 an=an-1+2n an=an-1+an-2 +n2+n+1 an=3an-1+n3n 相伴的线性齐次递推关系 an=an-1 an=an-1+an-2 an=3an-1,定理5,如果an(p)是常系数非齐次线性递推关系 an=c1an-1+c2an-2 +ckan-k+F(n)的一个特解， 那么每个解都是形如an(p)+an(h)的形式， 其中an(h)是相伴的齐次递推关系 an=c1an-1+c2an-2 +ckan-k 的解,36,例：求递推关系an=3an-1+2n的所有解。具有a1=3的解？ 解：相伴的齐次线性方程是an=3an-1, 它的解是an(h)=b*3n 找一个特解,37,38,4.3 分治算法和递推关系,递归算法将一
