F3[n]为Hanoi塔中3根柱子n个盘子的最少移动次数.ppt

递推法,在繁杂的世界变化中，许多现象的变化是有规律的，这种规律往往呈现出前因后果的关系。即某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。这一道理就体现了递推的思想。 有类试题，每相邻两项数之间的变化有一定规律性。通过分析考察，建立后项和前项之间的关系。然后从初始条件入手，一步步地按递推关系式递推，直至求出最终结果。如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件，问题就比较容易解决，让计算机一步步计算就可以了。,一、递推式的建立 1、Hanoi塔问题 问题: 三柱问题 问题：四柱问题 问题：m柱问题 2、平面分割问题 问题：封闭曲线分割平面 问题：Z分割平面 问题：M分割平面 3、Catalan数 问题一：凸n边形的三角形剖分 问题二：二叉树数目 问题三：出栈序列 4、第二类Stirling数 问题一：放置小球 问题二：集合划分问题 5、其他 问题一：集合取数问题 问题二：整数划分问题,二、递推式的求解方法： 1 递归函数 用数组实现 求递推式的通项表达式： 31、迭加法 32、待定系数法 33、特征方程法 34、生成函数法 思考题： 昆虫繁殖 青蛙过河,一、递推式的建立 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(n2)个盘子时，我们可以利用下列步骤： 第一步：先借助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)=2 f(n-1)+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柱不能作为中间柱子使用，根据三柱问题可知，移动次数为：2(i-j)-1。,第三步：最后把非目标柱2柱上的j个盘子移动到目标柱上，次数为：fj。,i,通过以上步骤我们可以初步得出： fi = 2*fj+2(i-j)-1,j可取的范围是1=jI，所以对于不同的j，得到的fi可能是不同的，本题要求最少的移动次数,fi = min2*fj+2(i-j)-1，其中1=jI,const MaxNum = 1000; var n : integer; F3, F4 : array1MaxNum of double; procedure Init; var i : integer; begin fillChar(F3,sizeOf(F3),0); fillChar(F4,sizeOf(F4),0); readln(n); F31 := 1; F41 := 1; *F3n 为Hanoi塔中3根柱子，n个盘子的最少移动次数 F3n = 2n -1; F4n 为Hanoi塔中4根柱子，n个盘子的最少移动次数* for i :=2 to n do F3i := 2*F3i-1 + 1; end;,procedure Run; var i, j : integer; minF4i,temp : double; begin for i := 2 to n do begin minF4i :=1e+100; for j := 1 to i-1 do begin temp := 2*F4j + F3i-j; if (temp minF4i) then minF4i := temp; end; *F4i = min(2*F4j + F3i-j);( 1= j =i-1) * F4i :=minF4i; end; writeln(F4n:0:0); end; begin Init; Run; end.,问题：m柱问题,【问题分析】： 设F(m,n)为m根柱子,n个盘子时移动的最少次数：,1、先把1柱上的前j个盘子移动到另外其中一个除m柱以外的非目标柱上，移 动次数为：fm, j；,2、再把原1柱上剩下的n-j个盘子在m-1根柱子之间移动，最后移动到目标柱m上，移动次数为：fm-1, n-j；,3、最后把非目标柱上的j个盘子移动到目标柱没柱上，移动次数为：fm, j。,F(m,n) = min2*F(m, j)+F(m-1,n-j) (1= j n),j,例4：杨辉三角,分析,组合公式的证明：,2、平面分割问题 问题 问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，求这些封闭曲线把平面分割成的区域个数。,【问题分析】： 设f(n)为n条封闭曲线把平面分割成的区域个数。 由图4很容易得出：f(1)=2；f(2)=4。,2,假设当前平面上已有的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-1个z共有3（n-1）条边，第n个z和他们共有3*(3*(n-1)个交点, 即第n个z被分成3*(3*(n-1) +1部分，所以增加3*(3*(n-1) +1个区域,由以上得出： f（n）=f（n-1）+ 3*(3*(n-1) +1 即：f（n）=f（n-1）+9n-8 初始条件：f（1）=2,问题：M分割平面 问题二的扩展：在问题二的基础上进一步考虑：如果z图形扩展为m边的下列图形：看一下问题的解。,通过上面的分析我们很容易知道：n个上述图形可以将平面划分的区域的递推关系： f（n）=f（n-1）+m（m（n-1）+1=f(n-1)+m2(n-1)+1 初始条件：f（1）=2,3、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)=1,F(n)=,4、第二类Stirling数 问题一：放置小球,n个有不同的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数 ，求S(n,m)。,设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以下两种：,1）bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为,S(n-1,m-1),2）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),问题二：集合划分问题。 设S是一个包含n个元素的集合，S=b1,b2,b3,bn,现需要将S集合划分为m个满足如下条件的集合S1,S2, Sm。 Si; SiSj=; S1S2Sm=S; (1=I ,j=m) 则称S1,S2, ,Sm是S的一个划分。 编程：输入n和m的值，输出不同的划分方案数。 要求：输入数据有一行，第一个数是n,第二个数m。 样例： 输入：4 3 输出：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) (n1,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在子集时，则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 (6n=200，2=k=6) 输出：一个整数，即不同的分法。 样例 输入： 7 3 输出：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， （Ij）,二、递推式的求解方法： 1 递归函数 用数组实现 求递推式的通项表达式： 31、迭加法 32、待定系数法 33、特征方程法 34、生成函数法,1、递归函数 用递归函数来实现递推式是初学选手们采用最多的求解方法，只要设置正确的边界条件，相对来说比较容易实现。 如：集合取数问题 f(n,k)= f(n-2,k-1) +f(n-1,k) 边界条件：F(n,1)=n, f(n,k)=0 ( n=k) function f(n,k:integer):integer; begin if k=1 then f:=n else if n=k then f:=0 else f:=f(n-2,k-1)+f(n-1,k); end;,2、用数组实现,放置小球: S(n,m)=m*S(n-1,m)+S(n-1,m-1) 边界条件：S(n,1)=1；S(i,i)=1；S(n,m)=0 (mn)。,var s:array1100,1100 of longint; n,m,i,j:integer; begin read(n,m); fillchar(s,sizeof(s),0); for i:=1 to n do si,1:=1; for i:=1 to m do si,i:=1; for i:=2 to m do for j:=i+1 to n do sj,i:=i*sj-1,i+sj-1,i-1; writeln(sn,m); end.,3求递推式的通项表达式,31、迭加法 一般符合下列形式的递推式可以使用迭代法。 F(n)=f(n-1)+g(n) 其中：g(n)是关于n的线性表达式。,F(2)=f(1)+9*2-8 F(3)=f(2)+9*3-8 F(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）=2,32、待定系数法,适合下列格式的递推式： F(n)=a*f(n-1)+g(n) a1,例1：Hanoi塔三柱问题： f(n)=2 f(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)+12n-1(f(1)+1)=2n 所以：f(n)2n1,例2： 求F(n)=3f(n-1)+n2+n+2的通项。F(1)=1;,令: f(n)+An2+Bn+c=3(f(n-1)+A(n-1)2+B(n-1)+c) A，B，C为待定系数。 由于上述恒等成立，得： 2A=1 2B-6A=0 3+3B+2C=0 求出：A,B,C后，从而得出f(n)的通项,33、特征方程法 如果a1, ,ak是常数，且ak=0,nk，则递推关系 F(n)= a1f(n-1)+a2f(n-2)+akf(n-k) 称为k阶常系数线性齐次递推关系。 它的特征方程是： Xk- a1Xk-1- a2Xk-2-ak=0 只要求出特征方程的根，再由初始条件表达式中的待定系数，便可以得到原递推关系的解。 如果特征方程有k个互不相同的解X1,X2,Xk，则通解为： F(n)=c1X1n+c2X2n+.+ckXkn c1 ,c2ck待定。,例：Fibonacci数列 F(n)=f(n-2)+f(n-1); f(1)=1;f(2)=1,解： 特征方程：X2-X-1=0,解得：x1=,x2=,则：f(n)=C1*X1n+C2*X2n,又因为：f(1)=1 f(2)=1 所以：C1*X1+C2*X21 C1*X12+C2*X221 得出：C1= C2=-,34、生成函数法 这种方法的基本思想原理： 已知数列：a0,a1,a2an 构造函数：g（x）=a0+a1x+a2x2+aixi+anxn. g(x)称为数列a0,a1,a2an的生成函数。 因此，我们要想求系数an，只要求出g(x)，然后把g(x)展开成幂级数。 f(x)=f(x0)+f1(x0)(x-x0)+ f2(x0)(x-x0)2/2!+f(n)(x0)(x-x0)n/n!+ 展开式中xn的系数就是an的表达式。： anf(n)(x0)/n! 如：g(x)=(1+x)n= a0+a1x+a2x2+aixi+anxn. 展开成幂级数：(1+x)n=Cn0+Cn1X+Cn2X2+CniXi+.+CnnXn 比较系数得：ai=Cni,现在的问题是 1、由已有的递推关系怎样构造求出g(x)。 2、把g(x) 展开成幂级数,例：二叉树数目 F(n)= f（0）=1；f(1)=1 求f(n),昆虫繁殖,科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？x=1,y=1,z=x 输入：x,y,z的数值 输出：成虫对数 示例： 输入：x=1 y=2 z=8 输出：37,分析,首先我们来看样例：每隔1个月产2对卵，求过8月（即第8+1=9月）的成虫个数,分析,设数组Ai表示第i月新增的成虫个数。 由于新成虫每过x个月产y对卵，则可对每个Ai作如下操作: Ai+k*x+2:=Ai+k*x+2+Ai*y (1=k,i+k*x+2=z+1） 因为A i的求得只与A1Ai-1有关，即可用递推求法。 则总共的成虫个数为：,例6：实数数列,一个实数数列共有N项，已知 ai=(ai-1-ai+1)/2+d，(1IN) (N60) 键盘输入N，d，a1，an，m，输出am。 输入数据均不需判错。,分析,根据公式ai=(ai-1-ai+1)/2+d 变形得，ai+1=ai-1-2ai+2d，因此该数列的通项公式为：ai=ai-2-2ai-1+2d，已知a1，如果能求出a2，这样就可以根据公式递推求出am ai=ai-2-2ai-1+2d (1) =ai-2-2（ai-3-2ai-2+2d）+2d =-2ai-3+5（ai-4-2ai-3+2d）-2d =5ai-4-12ai-3+8d 一直迭代下去，直到最后，可以建立ai和a1与a2的关系式。,分析,设ai=Pia2+Qid+Ria1，我们来寻求Pi,Qi,Ri的变化规律。 ai=ai-2-2ai-1+2d ai=Pi-2a2+Qi-2d+Ri-2a1-2（Pi-1a2+Qi-1d+Ri-1a1）+2d =(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1 Pi=Pi-2-2Pi-1 Qi=Qi-2-2Qi-1+2 Ri=Ri-2-2Ri-1 显然，P1=0 Q1=0 R1=1 （i=1） P2=1 Q2=0 R2=0 （i=2） 将初值P1Q1R1和P2Q2R2代入可以求出PnQnRn an=Pna2+Qnd+Rna1 a2=(an-Qnd+Rna1)/Pn 然后根据公式递推求出am，问题解决。,改进算法,但仔细分析，上述算法有一个明显的缺陷：在求由于在求a2要运用除法，因此会存在实数误差，这个误差在以后递推求am的过程又不断的扩大。在实际中，当m超过30时，求出的am就明显偏离正确值。显然，这种算法虽简单但不可靠。 为了减少误差，我们可设计如下算法： ai=Pia2+Qid+Ria1 =Pi-1a3+Qi-1d+Ri-1a2 =Pi-2a4+Qi-2d+Ri-2a3 =Pi-2+kak+Qi-2+kd+Ri-2+kak-1 an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1 ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2 根据公式，可以顺推a2、a3、aM。虽然仍然存在实数误差，但由于Pn-k+2递减，因此最后得出的am要比直接利用公式精确得多。,问题讨论:青蛙过河(Frog ),大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1Ym)和几个石墩(分别记为S1Sn)。图示如下：,试题描述,青蛙的站队和移动方法规则如下： 每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）； 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点； 青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上； 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动； 青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回； 假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。 荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。 每一步只能移动一只青蛙，并且移动后需要满足站队规则； 在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。,试题描述,青蛙希望最终能够全部移动到D上，并完成站队。 设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。 输入文件 文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0=n=25），第二行为荷叶数m（0=m=25）。 输出文件 文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的