《递推关系的建立及其求解方法》由会员分享，可在线阅读，更多相关《递推关系的建立及其求解方法（23页珍藏版）》请在金锄头文库上搜索。
1、第三讲递推式的建立及其求解方法一、递推式的建立1、Hanoi塔问题问题: 三柱问题问题：四柱问题问题：m柱问题2、平面分割问题问题：封闭曲线分割平面问题：Z分割平面问题：M分割平面3、Catalan数问题一：凸n边形的三角形剖分问题二：二叉树数目问题三：出栈序列4、第二类Stirling数 问题一：放置小球问题二：集合划分问题5、其他问题一：集合取数问题问题二：整数划分问题二、递推式的求解方法：1 递归函数用数组实现求递推式的通项表达式：31、迭加法32、待定系数法33、特征方程法34、生成函数法一、递推式的建立1、Hanoi塔问题问题的提出：Hanoi塔由n个大小不同的圆盘和m根木柱1,2,
2、3.m 组成。开始时，这n个圆盘由大到小依次套在1柱上，如图所示。现在要求把1柱上n个圆盘按下述规则移到m柱上： (1) 一次只能移一个圆盘； (2) 圆盘只能在m个柱上存放； (3) 在移动过程中，不允许大盘压小盘。求将这n个盘子从1柱移动到m柱上所需要移动盘子的最少次数 。问题:三柱问题设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。 当n=1时，f(1)=1。 当n=2时，f(2)=3。以此类推，当1柱上有n(n2)个盘子时，我们可以利用下列步骤： 第一步：先借助3柱把1柱上面的n1个盘子移动到2柱上，所需的移 动次数为f(n1)。 第二步：然后再把1柱最下面的一个盘子移动到3柱
3、上，只需要1次 盘子。 第三步：再借助1柱把2柱上的n1个盘子移动到3上，所需的移动次数为f(n1)。由以上3步得出总共移动盘子的次数为：f(n1)+1+ f(n1)。所以：f(n)=2 f(n1)+1 f(n)= 2n-1问题：四柱问题【问题分析】：令fi表示四个柱子时，把i个盘子从原柱移动到目标柱所需的最少移动次数。 j第一步：先把1柱上的前j个盘子移动到另外其中一个非目标柱（2或3柱均可，假 设移到2柱）上，此时3和4柱可以作为中间柱。移动次数为：fj。 第二步：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、4）之间移动，最后 移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据
4、三柱问题可知， 移动次数为：2(i-j)-1。第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。 i通过以上步骤我们可以初步得出： fi = 2*fj+2(ij)1j可取的范围是11,m1) 边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(kn)。5 、其他： ）集合取数问题设f(n,k)是从集合1，2，。，n中能够选择的没有两个连续 整数的k个元素子集的数目，求递归式f(n,k)。【问题分析】： N有两种情况： 当n在子集时，则n1一定不在子集中，即在1，2，。，n2中选k 1个元素，数目为f(n2,k1)。 当n不在子集中时，则在1，2，。，n1中选k个元素，数目为f(n 1,k)。 所以：f(n,k)= f(n2,k1) +f(n1,k) 边界条件：F(n,1)=n, f(n,k)=0 ( n=2，可以先那出j个1分到 每一份，然后再把剩下的I-j分成j份即可，分法有：f(I-j,j).第二类 : j份中至少有一份为1的分法，可以先那出一个1作为单独的1份， 剩下的I-1再分成j-1份即可，分法有：f(I-1,j-1). 所以：f(I,j)= f(I-j,j)+ f(I-1,j-1) 边界条件：f（i，1）=1， f（i，j）=0， （Ij）
