递推关系的建立及其求解方法课件

一、递推式的建立

1、Hanoi塔问题问题Ⅰ:三柱问题问题Ⅱ：四柱问题问题Ⅲ：m柱问题

2、平面分割问题问题Ⅰ：封闭曲线分割平面问题Ⅱ：‘Z’分割平面问题Ⅲ：‘M’分割平面

3、Catalan数问题一：凸n边形的三角形剖分问题二：二叉树数目问题三：出栈序列

4、第二类Stirling数问题一：放置小球问题二：集合划分问题

5、其他问题一：集合取数问题问题二：整数划分问题二、递推式的求解方法：

1．递归函数２．用数组实现３．求递推式的通项表达式：3．1、迭加法3．2、待定系数法

3．3、特征方程法3．4、生成函数法一、递推式的建立

1、Hanoi塔问题

问题的提出：Hanoi塔由n个大小不同的圆盘和m根木柱1,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(n>2)个盘子时，我们可以利用下列步骤：第一步：先借助3柱把1柱上面的n-1个盘子移动到2柱上，所需的移

动次数为f(n-1)。第二步：然后再把1柱最下面的一个盘子移动到3柱上，只需要1次

盘子。第三步：再借助1柱把2柱上的n-1个盘子移动到3上，所需的移动次

数为f(n-1)。由以上3步得出总共移动盘子的次数为：f(n-1)+1+f(n-1)。

所以：f(n)=2f(n-1)+1f(n)=2n-1问题Ⅱ：四柱问题【问题分析】：

令f[i]表示四个柱子时，把i个盘子从原柱移动到目标柱所需的最少移动次数。

j第一步：先把1柱上的前j个盘子移动到另外其中一个非目标柱（2或3柱均可，假设移到2柱）上，此时3和4柱可以作为中间柱。移动次数为：f[j]。第二步：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、4）之间移动，最后移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：2^(i-j)-1。第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：f[j]。通过以上步骤我们可以初步得出：f[i]=2*f[j]+2^(i-j)-1j可取的范围是1<=j<I，所以对于不同的j，得到的f[i]可能是不同的，本题要求最少的移动次数f[i]=min{2*f[j]+2^(i-j)-1}，其中1<=j<IconstMaxNum=1000;varn:integer;F3,F4:array[1..MaxNum]ofdouble;procedureInit;vari:integer;beginfillChar(F3,sizeOf(F3),0);fillChar(F4,sizeOf(F4),0);readln(n);F3[1]:=1;F4[1]:=1;{*F3[n]为Hanoi塔中3根柱子，n个盘子的最少移动次数F3[n]=2^n-1;F4[n]为Hanoi塔中4根柱子，n个盘子的最少移动次数*}

fori:=2tondoF3[i]:=2*F3[i-1]+1;end;

procedureRun;vari,j:integer;minF4i,temp:double;beginfori:=2tondobeginminF4i:=1e+100;forj:=1toi-1dobegintemp:=2*F4[j]+F3[i-j];if(temp<minF4i)thenminF4i:=temp;end;{*F4[i]=min(2*F4[j]+F3[i-j]);(1=<j<=i-1)*}F4[i]:=minF4i;end;writeln(F4[n]:0:0);end;beginInit;Run;end.问题Ⅲ：m柱问题【问题分析】：设F(m,n)为m根柱子,n个盘子时移动的最少次数：1、先把1柱上的前j个盘子移动到另外其中一个除m柱以外的非目标柱上，移动次数为：f[m,j]；2、再把原1柱上剩下的n-j个盘子在m-1根柱子之间移动，最后移动到目标柱m上，移动次数为：f[m-1,n-j]；3、最后把非目标柱上的j个盘子移动到目标柱没柱上，移动次数为：f[m,j]。F(m,n)=min{2*F(m,j)+F(m-1,n-j)}

(1<=j<n)j2、平面分割问题问题Ⅰ问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，求这些封闭曲线把平面分割成的区域个数。【问题分析】：设f(n)为n条封闭曲线把平面分割成的区域个数。由图4很容易得出：f(1)=2；f(2)=4。假设当前平面上已有的n-1条曲线将平面分割成f(n-1)­个区域，现在加入第n条封闭曲线。第n条曲线每与已有的n-1条曲线相交共有2(n-1)个交点，也就是说第n条曲线被前n-1条曲线分割成2(n-1)段弧线，而每一条弧线就会把原来的区域一分为二，即增加一个区域，所以共增加2(n-1)个区域F（n）=f（n-1）+2(n-1)问题Ⅱ问题的提出：一个‘z’形曲线可以把一个平面分割成2部分。如图所示。求n个‘z’形曲线最多能把平面分割成多少部分。写出递推式f(n)。【问题分析】：根据上图容易得出：f（1）=2；f（2）=12。假设平面上已有n-1个‘z’图形把平面分成了f（n-1）个区域。加入第n个‘z’后，单独考虑第n个‘z’的3条边，每一条边和前面的n-1个‘z’共有3（n-1）个交点，即这条边被分成3（n-1）+1部分，所以增加3（n-1）+1个区域，3条边共增加3（3（n-1）+1）个区域。但是第n个‘z’本身有2个交点，故少了2个区域，所以实际增加了3（3（n-1）+1）-2个区域。由以上得出：f（n）=f（n-1）+3（3（n-1）+1）-2

即：f（n）=f（n-1）+9n-8

初始条件：f（1）=2问题Ⅲ：‘M’分割平面问题二的扩展：在问题二的基础上进一步考虑：如果‘z’图形扩展为m边的下列图形：看一下问题的解。通过上面的分析我们很容易知道：n个上述图形可以将平面划分的区域的递推关系：f（n）=f（n-1）+m（m（n-1）+1）-（m-1）初始条件：f（1）=23、Catalan数问题一：凸n边形的三角形剖分在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用f(n)表之，f(n)即为Catalan数。例如五边形有如下五种拆分方案，故f(5)=5。求对于一个任意的凸n边形相应的f(n)。区域①是一个凸k边形，区域②是一个凸n-k+1边形，区域①的拆分方案总数是f(k)区域②的拆分方案数为f(n-k+1)，故包含△P1PkPn的n边形的拆分方案数为f(k)*f(n-k+1)种F(n)=问题二：二叉树数目问题描述：求n个结点能构成不同二叉数的数目。【问题分析】：设F(n)为n个结点组成二叉树的数目。容易知道：f(1)=1;f(2)=2,f(3)=5选定1个结点为根，左子树结点的个数为i，二叉树数目f（i）种；右子树结点数目为n-i-1，二叉树数目f（n-i-1）种，I的可取范围[0，n-1]。所以有：F(n)=

为了计算的方便：约定f（0）=1问题三：出栈序列问题描述：N个不同元素按一定的顺序入栈，求不同的出栈序列数目。【问题分析】：设f（n）为n个元素的不同出栈序列数目。容易得出：f（1）=1；f（2）=2。第n个元素可以第i（1<=i<=n）个出栈，前面已出栈有i-1个元素，出栈方法：f（i-1）；后面出栈n-I个元素，出栈方法为：f（n-i）。所以有：F(n)=约定：F(0)=1F(n)=4、第二类Stirling数问题一：放置小球n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数

设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S(n-1,m-1)bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS(n-1,m)S(n,m)=mS(n-1,m)+S(n-1,m-1)(n>1,m1)问题二：集合划分问题。设S是一个包含n个元素的集合，S={b1,b2,b3,…,bn},现需要将S集合划分为m个满足如下条件的集合S1,S2,…Sm。Si≠∮;Si∩Sj=∮;

S1∪S2∪…∪Sm=S;(1<=I,j<=m)则称S1,S2,…,Sm是S的一个划分。编程：输入n和m的值，输出不同的划分方案数。要求：输入数据有一行，第一个数是n,第二个数m。样例：输入：43输出：6不同的方案数用S(n,m)表示从中取出bn，bn的放法有以下两种：１、bn独自占一个集合；那么剩下的数只能放在m-1个集合中，方案数为；２、bn与别的数共占一个集合；那么我们可以先将b1,b2,……bn-1这n-1个数划分为m个集合，然后再将bn可以任意放入其中一个集合中，方案数为综合以上两种情况可以得出：S(n-1,m-1)m*S(n-1,m)S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m1)边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。5、其他：１）‘集合取数问题设f(n,k)是从集合{1，2，。。。，n}中能够选择的没有两个连续整数的k个元素子集的数目，求递归式f(n,k)。【问题分析】：N有两种情况：①当n在子集时，则n-1一定不在子集中，即在{1，2，。。。，n-2}中选k-1个元素，数目为f(n-2,k-1)。②当n不在子集中时，则在{1，2，。。。，n-1}中选k个元素，数目为f(n-1,k)。所以：f(n,k)=f(n-2,k-1)+f(n-1,k)边界条件：F(n,1)=n,f(n,k)=0(n<=k)２）整数划分问题将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5;1，5，1;5，1，1;

问有多少种不同的分法。

输入：n，k(6<n<=200，2<=k<=6)

输出：一个整数，即不同的分法。样例

输入：73

输出：4{四种分法为：1，1，5;1，2，4;1，3，3;2，2，3;}【问题分析】：用f(I,j)表示将整数I分成j分的分法，可以划分为两类：第一类：j分中不包含1的分法，为保证每份都>=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，（I<j）

1．递归函数２．用数组实现３．求递推式的通项表达式：3．1、迭加法3．2、待定系数法3．3、特征方程法3．4、生成函数法递推式的求解方法：1、递归函数

用递归函数来实现递推式是初学选手们采用最多的求解方法，只要设置正确的边界条件，相对来说比较容易实现。如：集合取数问题f(n,k)=f(n-2,k-1)+f(n-1,k)边界条件：F(n,1)=n,f(n,k)=0(n<=k)functionf(n,k:integer):integer;beginifk=1thenf:=nelseifn<=kthenf:=0elsef:=f(n-2,k-1)+f(n-1,k);end;2用数组实现集合划分问题:S(n,m)=m*S(n-1,m)+S(n-1,m-1)(n>1,m1)边界条件：S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。vars:array[1..100,1..100]oflongint;n,m,i,j:integer;beginread(n,m);fillchar(s,sizeof(s),0);

fori:=1tondos[i,1]:=1;fori:=1tomdos[i,i]:=1;fori:=2tomdoforj:=itondos[j,i]:=i*s[j-1,i]+s[j-1,i-1];

writeln(s[n,m]);end.3求递推式的通项表达式3．1、迭加法一般符合下列形式的递推式可以使用迭代法。F(n)=f(n-1)+g(n)其中：g(n)是关于n的线性表达式。F(2)=f(1)+9*2-8F(3)=f(2)+9*3-8F(4)=f(3)+9*4-8┆┆F(n)=f(n-1)+9*n-8以上n-1个等式相加得到：f(n)=f(1)+9*(2+3+4+……+n)-8*(n-1)即：f(n)=9*n*n/2-7*n/2+1如：平面分割问题二:f（n）=f（n-1）+9n-8初始条件：f（1）=23．2、待定系数法适合下列格式的递推式：F(n)=a*f(n-1)+g(n)a>1例1：Hanoi塔三柱问题：f(n)=2f(n-1)+1，边界条件：f(1)=1令：f(n)+A=2(f(n-1)+A)A为待定系数求得A=1,即：f(n)+1=2(f(n-1)+1)由等比数列性质得出：f(n)+1＝2n-1(f(1)+1)=2n所以：f(n)＝2n－1例2：

求f(n)=3f(n-1)+n2+n+2的通项。令:f(n)+An2+Bn+c=3(f(n-1)+A(n-1)2+B(n-1)+c)A，B，C为待定系数。由于上述恒等成立，得：2A=12B-6A=03+3B+2C=0求出：A,B,C后，从而得出f(n)的通项3．3、特征方程法

如果a1,,……ak是常数，且ak<>=0,n>k，则递推关系

F(n)=a1f(n-1)+a2f(n-2)+……akf(n-k)称为k阶常系数线性齐次递推关系。它的特征方程是：Xk-a1Xk-1-a2Xk-2-……-ak=0只要求出特征方程的根，再由初始条件表达式中的待