递推关系的建立及其求解方法.ppt

《递推关系的建立及其求解方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三讲递推式的建立及其求解方法一、递推式的建立1、Hanoi塔问题问题Ⅰ:三柱问题问题Ⅱ：四柱问题问题Ⅲ：m柱问题2、平面分割问题问题Ⅰ：封闭曲线分割平面问题Ⅱ：‘Z’分割平面问题Ⅲ：‘M’分割平面3、Catalan数问题一：凸n边形的三角形剖分问题二：二叉树数目问题三：出栈序列4、第二类Stirling数问题一：放置小球问题二：集合划分问题5、其他问题一：集合取数问题问题二：整数划分问题二、递推式的求解方法：1．递归函数２．用数组实现３．求递推式的通项表达式：3．1、迭加法3．2、待定系数法3．3、特征方程法3．4、生成函数法一、递推式的建立1、Hanoi塔

2、问题问题的提出：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个盘子移动

3、到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]。第二步

4、：再把原1柱上剩下的i-j个盘子在3根柱子（1、3、4）之间移动，最后移动到目标柱4上，因为此时2柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：2^(i-j)-1。第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：f[j]。i通过以上步骤我们可以初步得出：f[i]=2*f[j]+2^(i-j)-1j可取的范围是1<=j

5、[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:do

6、uble;beginfori:=2tondobeginminF4i:=1e+100;forj:=1toi-1dobegintemp:=2*F4[j]+F3[i-j];if(temp

7、除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

8、易得出：f(1)=2；f(2)=4。2