集合的概念与表示法.ppt

*例2汉诺塔(Hanoi)问题有三根立柱A、B、C以及n个大小不同的圆盘套在立柱A上，大的圆盘在下面，小的圆盘在上面，构成一个塔形。现在要把这n个圆盘移到立柱B上。可以利用这三根立柱，每次只能移动一个圆盘，但不允许将它放在较小的圆盘上，问最少需移动多少次？解令Hn为完成这样的一次移动至少必须移动圆盘的次数。为了把n个圆盘从立柱A移到立柱B，可先将n－1个圆盘从立柱A移到立柱C，留下最大的圆盘，移动的次数为Hn－1；然后再将最大的圆盘移动到立柱B，移动1次；最后将n－1个圆盘从立柱C移到立柱B，移动次数为Hn－1。第64页,共82页，星期六，2024年，5月*于是有Hn＝2Hn－1＋1，n≥2，其中H1＝1。以上的例子有一个共同的特点，即从我们在计数问题所得出的数列中，它的一般项可用它自身数列中的前面若干项来表达。这样，从给定的初始值出发，利用所建立的关系式可以依次算出数列中的每一项。我们称这些关系式为递推关系。下面我们介绍递推关系的几种解法。第65页,共82页，星期六，2024年，5月*1.递推关系的生成函数解法设{a0，a1，…，an，…}为一个无穷数列，我们称f(t)＝a0＋a1t＋…＋antn＋…为该数列的生成函数。例3数列{1，1，…，1，…}的生成函数为＝1＋t＋…＋tn＋…。将递推关系代入数列的生成函数的系数中去，通过计算可以得到生成函数的显式，然后再将它展开成幂级数就可求得数列的通项。例4斐波那契数列问题解设F(x)＝为斐波那契数列的生成函数，则有第66页,共82页，星期六，2024年，5月*F(x)＝F0＋F1x＋＝1＋x＋＝1＋x＋x＋xn＝1＋x＋x(F(x)－1)＋x2F(x)从上面关系式可以解出F(x)＝＝＝＝比较等式两边xn的系数，得到Fn＝。第67页,共82页，星期六，2024年，5月*2.常系数线性齐次递推关系的解法我们把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(其中H(n)、H(n－1)、…、H(n－k)是n的函数)的递推关系式称为常系数线性齐次递推关系，并称xk＋b1xk－1＋b2xk－2＋…＋bk＝0为其特征方程，它的根称为其特征根。在使用特征根方法求解递推关系时要用到下面三个定理，其证明参见相关文献。定理3.22设q为非零的实数或复数，则H(n)＝qn是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解当且仅当q是它的一个特征根。第68页,共82页，星期六，2024年，5月*定理3.23设q1、q2、…、qk为非零的实数或复数，则H(n)＝C1q1n＋C2q2n＋…＋Ckqkn(C1、C2、…、Ck是确定的常数)是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解当且仅当q1、q2、…、qk是它的k个不同的特征根。定理3.24设q1、q2、…、qk为非零的实数或复数，它们是递推关系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的特征方程的t(t≤k)个不同的特征根，各有e1、e2、…、et重。则递推关系式的一般解是H(n)＝H1(n)＋H2(n)＋…＋Ht(n)，其中Hi(n)＝C1qin＋C2nqin＋…＋qin(i＝1，2，…，t；C1，C2，…，为确定的常数)。例6斐波那契数列问题第69页,共82页，星期六，2024年，5月*解递推关系Fn＝Fn－1＋Fn－2的特征方程为x2―x―1＝0，其解为：x1＝，x2＝。于是递推关系的通解为Fn＝C1＋C2。将F0＝1，F1＝1代入得C1＋C2＝1C1＋C2＝1解上述式子得：C1＝，C2＝－。于是Fn＝。第70页,共82页，星期六，2024年，5月*3.常系数线性非齐次递推关系的解法我们把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝f(n)(其中H(n)、H(n－1)、…、H(n－k)是n的函数，f(n)是n的多项式或an)的递推关系式称为常系数线性非齐次递推关系。这类递推关系的求解可通过将非齐次递推关系归约为齐次递推关系的方法来求解。下面我们通过一个例子来说明。例7