第二讲--递归与递推剖析课件

20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例1巧数 一个合数的的各位数字之和等于它所有质因数的各数字之和称为巧数。例如合数483的各位数字相加（4+8+3）=15，如果将483分解成质因数相乘：483=3*7*23，把这些质因数各位数字相加（3+7+2+3），其和也为15，483就是巧数。统计n(1 do if x mod xx=0 then begin tt:=0;sub1(xx,tt);t:=t+tt;x:=x div xx end else inc(xx)end;子程序复习子程序复习子程序复习子程序复习20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学procedure sub3(x:integer;var yy:boolean);过程：判断x是否为素数 var k,m:integer;begin k:=trunc(sqrt(x);for m:=2 to k do if x mod m=0 then yy:=false;end;子程序复习子程序复习子程序复习子程序复习20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学begin 主程序主程序 for n:=1 to 500 do begin t1:=0;t2:=0;yes:=true;sub3(n,yes);调用过程求素数调用过程求素数 if not yes then 如果非素数就如果非素数就 begin sub1(n,t1);调用过程求调用过程求n n的各位数字之和的各位数字之和 sub2(n,t2);调用过程求调用过程求n n的各质因数的数字之和的各质因数的数字之和 if t1=t2 then total:=total+1 打印合格的合数打印合格的合数 end end;wtiteln(total);readlnend.子程序复习子程序复习子程序复习子程序复习20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学 从前有座山，山里有个老和尚，从前有座山，山里有个老和尚，老和尚对小和尚讲：从前有座山，老和尚对小和尚讲：从前有座山，山里有个老和尚，老和尚对小和山里有个老和尚，老和尚对小和尚讲：从前有座山，山里有个老尚讲：从前有座山，山里有个老和尚，老和尚对小和尚讲和尚，老和尚对小和尚讲递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学观察下面的函数观察下面的函数function fac2(x:integer):longint;begin if x=1 then fac2:=1 else fac2:=fac2(x-1)*x;end;function fac1(x:integer):longint;var i:integer;p:longint;begin p:=1;for i:=1 to x do p:=p*i;fac1:=p;end;递归递归递归递归函数自己调用自己函数自己调用自己函数自己调用自己函数自己调用自己20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递归的概念递归的概念递归递归 函数或过程自己直接或间接调用自己！函数或过程自己直接或间接调用自己！facfac函数被称为递归函数（递归公式），为了函数被称为递归函数（递归公式），为了求求fac(nfac(n)，我们必须先求，我们必须先求fac(n-1)fac(n-1)，为了求，为了求fac(n-1),fac(n-1),又必须去求又必须去求fac(n-2)fac(n-2)，为了求，为了求fac(2),fac(2),必须先求必须先求fac(1),fac(1),而而fac(1)fac(1)是已知的。这是已知的。这种定义函数的方式称为递归定义。种定义函数的方式称为递归定义。递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学直接或间接地调用自身的算法称为直接或间接地调用自身的算法称为递归算法递归算法用函数自身给出定义的函数称为用函数自身给出定义的函数称为递归函数递归函数用过程自身给出定义的过程称为用过程自身给出定义的过程称为递归过程递归过程其中直接调用自己的过程称为其中直接调用自己的过程称为直接递归直接递归而将而将A调用调用B，B又调用又调用A的递归叫做的递归叫做间接递归间接递归递递 归归 定定 义义20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学观察与思考观察与思考递归定义里的参数是如何变化?边界条件若没有，会如何？function fac2(x:integer):longint;begin if x=1 then fac2:=1 else fac2:=fac2(x-1)*x;end;递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学S:=Fac(5)function fac2(x:integer):longint;begin if x=1 then fac2:=1 else fac2:=fac2(x-1)*x;end;递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递归递归 描述递归定义的函数或求解描述递归定义的函数或求解递归问题的过程称为递归算法。递归问题的过程称为递归算法。两个条件：两个条件：1.1.递归式（递归关系）；递归式（递归关系）；2.2.递归终止条件。递归终止条件。递归表达式递归表达式是解题的关键！是解题的关键！递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例1：求和：sum=1+2+3+100例题例题1 1递归关系式递归关系式如何求？如何求？运用函数的前驱值来计算函数当前值的关系式用递归算法 例例2：菲波拉契数列菲波拉契数列 1,1,2,3,5,8递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例例3、用递归方法求两个正整数、用递归方法求两个正整数m和和n的最大公的最大公约数。约数。分析：求两个数的最大公约数可以用辗转相分析：求两个数的最大公约数可以用辗转相除法，即求除法，即求m m与与n n的最大公约数等价于求（的最大公约数等价于求（m mod m mod n n）的值与）的值与n n的最大公约数，此时的的最大公约数，此时的n n可以当作新可以当作新的的m m，而（，而（m mod nm mod n）的值当作新的）的值当作新的n n，所以原，所以原问题的求解又变成求新的问题的求解又变成求新的m m与与n n的最大公约数问题，的最大公约数问题，继续下去，直至继续下去，直至(m mod n)(m mod n)为为0 0，最大公约数就是，最大公约数就是最终存放在最终存放在n n中的值。中的值。M=20 N=8递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学function gcd(m,n：longint)：longint；begin if then gcd:=n else ；end；递归公式：递归公式：gcd(m,n)=n m mod n=0gcd(n,m mod n)m mod n0递归调用递归调用m mod n=0gcd:=gcd(n,m mod n)递归递归递归递归20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递归过程例析递归过程例析例例4、汉汉诺诺塔塔（tower of Hanoi）问问题题。有有n个个大大小小不不等等的的中中空空圆圆盘盘，按按照照从从小小到到大大的的顺顺序序迭迭套套在在立立柱柱A上上，另另有有两两根根立立柱柱B和和C。现现要要求求把把全全部部圆圆盘盘从从A柱柱移移到到C柱柱的的过过程程，移移动动过过程程中中可可借借助助B柱柱（中间柱）。移动时有如下的要求：（中间柱）。移动时有如下的要求：一次只移动一个盘；一次只移动一个盘；不允许把大盘放在小盘上边；不允许把大盘放在小盘上边；可使用任意一根立柱暂存圆盘可使用任意一根立柱暂存圆盘20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学案例：案例：汉诺塔汉诺塔ACB1:(n-1,A,B,C)2:A C3:(n-1,B,C,A)(n,A,C,B)缩小数缩小数据规模据规模/递归递归直接求解直接求解递归过程例析递归过程例析20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学先以三个盘的移动为例，看一下移动过程。先以三个盘的移动为例，看一下移动过程。递归过程例析递归过程例析20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学分析分析1、当、当n=1时，只需要移动一次时，只需要移动一次A-C；2、当、当n=2时，需要移动三次；时，需要移动三次；A-1-B；A-2-C；B-1-C；3、当、当n=3时，先将前时，先将前n-1个盘子以个盘子以C为为中介移到中介移到B柱子；再将第柱子；再将第n个盘子移到个盘子移到C柱子；最后将柱子；最后将n-1个盘子以个盘子以A为中介从为中介从B柱移到柱移到C柱。柱。递归过程例析递归过程例析20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学主要程序段主要程序段 procedure move(n:integer;z1,z2,z3：char)；beginif n=1 then writeln(z1，z3)else begin move(n-1，z1，z3，z2)；writeln(z1，z3)；move(n-1，z2，z1，z3)end end；move(total，A，B，C)递归过程例析递归过程例析20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例例5、由、由m个个A，n个个B组成若干个排列。从某个排列组成若干个排列。从某个排列的位置的位置1开始数，数到任意位置时都能保证开始数，数到任意位置时都能保证A的个数的个数不少于不少于B的个数，则称该排列为合理排列。例如：的个数，则称该排列为合理排列。例如：当当m=2，n=2时排列有时排列有 A A B B(合理合理)A B A B(合合理理)A B B A(不合理不合理)B B A A(不合理不合理)合理排列数有合理排列数有2种种输入：只有一行两个整数输入：只有一行两个整数m,n（1nm12）（用）（用 空格分隔）空格分隔）输出：一个整数（所有的合理排列数）输出：一个整数（所有的合理排列数）【样例样例】输入输入 输出输出 3 2 520082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学分析：模拟排队的情况，从第分析：模拟排队的情况，从第1个人开始，第个人开始，第1 人只能人只能是是A，第，第2个可以是个可以是A也可以是也可以是B，再其后的人要保证任，再其后的人要保证任意位置时都能保证意位置时都能保证A的个数不少于的个数不少于B的个数，递归生成的个数，递归生成整个排列。整个排列。Var m,n,t:LongInt;Procedure pd(i,j:LongInt);Begin If(i=m)And(j=n)Then t:=t+1已生成一种排列已生成一种排列 Else Begin If im Then _增加增加1个个A If(jn)And(ji)Then_ End;增加增加1个个BEnd;Begin t:=0;Read(m,n);pd(1,0);Writeln(t);End.pd(i+1,j);pd(i,j+1);20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学1、数据的定义形式是递归的，如求Fibonacci数列问题。2、某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种问题使用递归思想来求解比其它方法更简单。3、数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。总结递归算法一般适用在三个场合：20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递归的缺点递归的缺点 冗余计算冗余计算造成程序的效率很低。你试过造成程序的效率很低。你试过用直接递归的函数计算用直接递归的函数计算FibonacciFibonacci数列的第数列的第5050项吗？项吗？边界条件设置不当的情况下，经常造成边界条件设置不当的情况下，经常造成死循环或者死循环或者内存内存(系统栈系统栈)溢出溢出的窘境，导的窘境，导致致递归深度有限递归深度有限。所以，一般递归子程序。所以，一般递归子程序中不要定义局部数组。中不要定义局部数组。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学直接将递归转化成递推直接将递归转化成递推直接将递归转化成递推直接将递归转化成递推 当当当当递递递递归归归归关关关关系系系系有有有有明明明明确确确确的的的的定定定定义义义义时时时时，一一一一般般般般来来来来说说说说，相相相相邻邻邻邻的的的的两两两两个个个个数数数数之之之之间间间间有有有有着着着着规规规规律律律律性性性性的的的的变变变变化化化化，我我我我们们们们常常常常常常常常可可可可以以以以利利利利用用用用这这这这种种种种规规规规律律律律性性性性的的的的变变变变化化化化，一一一一步步步步一一一一步步步步递递递递推推推推出出出出结结结结果果果果，而而而而将将将将递递递递归归归归结结结结束束束束条条条条件件件件作作作作为为为为递递递递推推推推的的的的初初初初始始始始条条条条件件件件。实实实实现现现现这这这这种种种种递递递递推推推推通通通通常常常常使使使使用用用用循循循循环环环环迭迭迭迭代代代代的的的的方方方方法法法法，如如如如循循循循环环环环累累累累乘乘乘乘、计计计计算算算算斐斐斐斐波波波波那切数据项等。那切数据项等。那切数据项等。那切数据项等。当当当当递递递递归归归归关关关关系系系系没没没没有有有有明明明明确确确确的的的的递递递递归归归归式式式式时时时时，也也也也可可可可以以以以转转转转化化化化成成成成递递递递推推推推来来来来完完完完成成成成，这这这这就就就就需需需需要要要要不不不不断断断断的的的的缩缩缩缩小小小小问问问问题题题题的的的的规规规规模模模模，找出规律性的变化。找出规律性的变化。找出规律性的变化。找出规律性的变化。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递推算法引入递推算法引入1、求、求1+2+3+n的和的和2、求、求n！3、Fibonacci数列数列20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递推定义递推定义对于一个有规律的数列，我们可以借助已对于一个有规律的数列，我们可以借助已知的项，利用特定的关系逐项推算出它的知的项，利用特定的关系逐项推算出它的后继项的值，后继项的值，如此反复，直到找到，如此反复，直到找到所需的那一项为止，这样的方法称为所需的那一项为止，这样的方法称为递推递推算法。算法。递推算法递推算法的首要问题是得到相邻的数据项的首要问题是得到相邻的数据项间的关系（即递推关系）。间的关系（即递推关系）。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学“递推关系递推关系递推关系递推关系”是一种简洁高效的数学模型，比如是一种简洁高效的数学模型，比如是一种简洁高效的数学模型，比如是一种简洁高效的数学模型，比如经典的经典的经典的经典的FibonacciFibonacciFibonacciFibonacci数列问题。数列问题。数列问题。数列问题。此类问题中，每个数据项都和它前面的若干个数此类问题中，每个数据项都和它前面的若干个数此类问题中，每个数据项都和它前面的若干个数此类问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，据项（或后面的若干个数据项）有一定的关联，据项（或后面的若干个数据项）有一定的关联，据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个这种关联一般是通过一个这种关联一般是通过一个这种关联一般是通过一个“递推关系式递推关系式递推关系式递推关系式”来表示来表示来表示来表示的。的。的。的。“递推法递推法递推法递推法”是指求解问题时，从初始的一个或若是指求解问题时，从初始的一个或若是指求解问题时，从初始的一个或若是指求解问题时，从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而干数据项出发，通过递推关系式逐步推进，从而干数据项出发，通过递推关系式逐步推进，从而干数据项出发，通过递推关系式逐步推进，从而得到最终结果。得到最终结果。得到最终结果。得到最终结果。初始的若干数据项称为初始的若干数据项称为初始的若干数据项称为初始的若干数据项称为“递推边界递推边界递推边界递推边界”。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学解决递推问题有三个重点解决递推问题有三个重点 一是推导、建立正确的递推关系式；一是推导、建立正确的递推关系式；二是进一步探讨递推关系式的性质；二是进一步探讨递推关系式的性质；三是如何根据递推关系式编程求解。三是如何根据递推关系式编程求解。递推按照我们推导问题的方向，常分为递推按照我们推导问题的方向，常分为递推按照我们推导问题的方向，常分为递推按照我们推导问题的方向，常分为顺顺顺顺推法推法推法推法和和和和倒推法。倒推法。倒推法。倒推法。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学顺推法顺推法 从已知条件出发，逐步推算出要解决的问题的方从已知条件出发，逐步推算出要解决的问题的方从已知条件出发，逐步推算出要解决的问题的方从已知条件出发，逐步推算出要解决的问题的方法叫顺推。法叫顺推。法叫顺推。法叫顺推。例：例：例：例：Fibonacci Fibonacci数列大家都非常熟悉，来源于中世纪数数列大家都非常熟悉，来源于中世纪数数列大家都非常熟悉，来源于中世纪数数列大家都非常熟悉，来源于中世纪数学家学家学家学家FibonacciFibonacci提出的一个问题：一对刚出生的兔子提出的一个问题：一对刚出生的兔子提出的一个问题：一对刚出生的兔子提出的一个问题：一对刚出生的兔子过两个月后过两个月后过两个月后过两个月后,可以繁殖一对新兔子可以繁殖一对新兔子可以繁殖一对新兔子可以繁殖一对新兔子,问原有雌雄各一问原有雌雄各一问原有雌雄各一问原有雌雄各一只兔子，经过十一个月后，能繁殖多少只兔子。只兔子，经过十一个月后，能繁殖多少只兔子。只兔子，经过十一个月后，能繁殖多少只兔子。只兔子，经过十一个月后，能繁殖多少只兔子。f(0)=1;f(1)=1;f(3)=2f(0)=1;f(1)=1;f(3)=2f(nf(n)=f(n-2)+f(n-1)=f(n-2)+f(n-1)20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学 猴子吃桃第一天，x个桃第二天，吃一半多一个第三天，再吃剩下的一半多一个第十天，发现只剩下一个问第一天x是多少？倒倒倒倒推法推法推法推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学VarVar S,I:longIntS,I:longInt;BeginBegin S:=1;S:=1;第第1010天只有一个桃子天只有一个桃子 For I:=9 For I:=9 DownToDownTo 1 Do 1 Do S:=(S+1)*2;S:=(S+1)*2;第第1010天依次求前一天的桃天依次求前一天的桃 Writeln(SWriteln(S););子数子数 End.End.20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递推的三种模型递推的三种模型模型模型1 1：前一项前一项推出当前项推出当前项 Ai-1 Ai模型模型2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai模型模型3 3：前所有项前所有项推出当前项推出当前项 A1 A2 Ai-1 Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学模型模型1 1：前一项前一项推出当前项推出当前项 Ai-1 Ai如：如：求求1+2+3+n的和的和 如：如：求求n！s(1):=0;s(1):=0;for i:=1 to n do for i:=1 to n do s(is(i):=s(i-1)+i;):=s(i-1)+i;t(1):=1;t(1):=1;For i:=1 to n do For i:=1 to n do t(it(i):=t(i-1)*i;):=t(i-1)*i;20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai 例例：一只蜜蜂在下图所示的数字蜂房上一只蜜蜂在下图所示的数字蜂房上爬动爬动,已知它只能从标号小的蜂房爬到标已知它只能从标号小的蜂房爬到标号大的相邻蜂房号大的相邻蜂房,现在问你：蜜蜂从蜂房现在问你：蜜蜂从蜂房M开始爬到蜂房开始爬到蜂房N，MN=10000，有多，有多少种爬行路线？少种爬行路线？20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例例2、打印杨晖三角形的前、打印杨晖三角形的前10行。杨晖三角形的前行。杨晖三角形的前5行如左下图所示。行如左下图所示。问题分析：我们观察左上图不太容易找到规律，问题分析：我们观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。形其实就是一个二维表（数组）的下三角部分。模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例例3设有一个共有设有一个共有n级的楼梯，某人每步可走级的楼梯，某人每步可走1级，级，也可走也可走2级，也可走级，也可走3级，给出某人从底层开始走级，给出某人从底层开始走完全部楼梯的走法。完全部楼梯的走法。例如：当例如：当n=3时，共有时，共有4种走法，即种走法，即1+1+1,1+2,2+1,3。模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai分析：分析：用递推公式给出的某人从底层开始走完全部楼梯的用递推公式给出的某人从底层开始走完全部楼梯的走法为走法为(用用F(N)记录不同案数：记录不同案数：F(1)=1F(2)=2F(3)=4F(n)=F(n-3)+F(n-2)+F(n-1)(n4)20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学设有一个设有一个n级的楼梯级的楼梯(1=n=12),编号从下到上依次为编号从下到上依次为1至至n,其中有其中有1级为坏的。有一个人上楼梯时一步可走级为坏的。有一个人上楼梯时一步可走1级、级、或或2级、或级、或3级级(坏级只能跨过不能踏上坏级只能跨过不能踏上,但级数照算但级数照算)。问问:这个人从楼下走到第这个人从楼下走到第n级级,共有多少种不同的走法共有多少种不同的走法?例如例如:当当n=1时时(无坏级情况下无坏级情况下),仅有仅有1种走法种走法 n=2时时(无坏级情况下无坏级情况下),有有:1级级+1级级 或或 2级级 共共2种走法种走法 n=3时时(第二级为坏级情况下第二级为坏级情况下),有有:1级级+2级级,直接直接3级级,共共2种走种走法法拓展拓展1：模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学var x,i,n,f1,f2,f3,f4:longint;s:set of 0.30;begin readln(n);readln(x);x:坏级坏级 If x=1 then f1:=0 else f1:=1;If x=2 then f2:=0 else f2:=_ If x=3 then f3:=0 else f3:=1+f1+f2;f1+1;f1+1;f1+1;f1+1;模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学 if n=1 then f4:=f1 else if n=2 then f4:=f2 else if n=3 then f4:=f3 else begin for i:=4 to n do begin if x=i then f4:=0 else f4:=_ f1:=f2;f2:=f3;f3:=f4;end;end;writeln(f4);readln;end.f1+f2+f3;f1+f2+f3;f1+f2+f3;f1+f2+f3;模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学 设有一个设有一个n级的楼梯级的楼梯(1=n=12),编号从下到上编号从下到上依次为依次为1至至n,其中有其中有若干级为坏若干级为坏的。有一个人上楼梯的。有一个人上楼梯时一步可走时一步可走1级、或级、或2级、或级、或3级级(坏级只能跨过不能踏坏级只能跨过不能踏上上,但级数照算但级数照算)。问。问:这个人从楼下走到第这个人从楼下走到第n级级,共有共有多少种不同的走法多少种不同的走法?例如例如:当当n=1时时(无坏级情况下无坏级情况下),仅有仅有1种走法种走法 n=2时时(无坏级情况下无坏级情况下),有有:1级级+1级级 或或 2级级 共共2种走法种走法 n=3时时(第二级为坏级情况下第二级为坏级情况下),有有:1级级+2级级,直接直接3级级,共共2种种走法走法拓展拓展2：用集合记录坏级处理用集合记录坏级处理模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学例例例例2 2：母牛生小牛：母牛生小牛：母牛生小牛：母牛生小牛问题描述：农场主在年初买了一头刚生下的小母牛，问题描述：农场主在年初买了一头刚生下的小母牛，问题描述：农场主在年初买了一头刚生下的小母牛，问题描述：农场主在年初买了一头刚生下的小母牛，3 3年后的年后的年后的年后的年初，小母牛生下了一头小母牛。假设以后每年年初，那年初，小母牛生下了一头小母牛。假设以后每年年初，那年初，小母牛生下了一头小母牛。假设以后每年年初，那年初，小母牛生下了一头小母牛。假设以后每年年初，那头母牛都生下一头小母牛，而所有小母牛也会在头母牛都生下一头小母牛，而所有小母牛也会在头母牛都生下一头小母牛，而所有小母牛也会在头母牛都生下一头小母牛，而所有小母牛也会在3 3年后的年年后的年年后的年年后的年初生下一头小母牛，且以后每年年初同样会生下一头小母初生下一头小母牛，且以后每年年初同样会生下一头小母初生下一头小母牛，且以后每年年初同样会生下一头小母初生下一头小母牛，且以后每年年初同样会生下一头小母牛。问牛。问牛。问牛。问N N（3=N=100)3=N=100)年后农场主有多少头母牛年后农场主有多少头母牛年后农场主有多少头母牛年后农场主有多少头母牛(假设没有假设没有假设没有假设没有一头死亡一头死亡一头死亡一头死亡)？输入输入输入输入一行，经过的一行，经过的一行，经过的一行，经过的N N年年年年输出输出输出输出一行，经过一行，经过一行，经过一行，经过N N年后的母牛的头数年后的母牛的头数年后的母牛的头数年后的母牛的头数输入样例输入样例输入样例输入样例8 8输出样例输出样例输出样例输出样例1313模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学分析分析 若若x0,x1,x2,x3分别为刚生下的母牛、满分别为刚生下的母牛、满1周岁周岁的母牛、满的母牛、满2周岁的母牛以及可生小母牛的母牛周岁的母牛以及可生小母牛的母牛（育龄牛），由题意得：（育龄牛），由题意得：X0(0)=1;X1(0)=x2(0)=x3(0)=0X0(i)=x3(i)=x2(i-1)+x3(i-1)X1(i)=x0(i-1)X2(i)=x1(i-1)S=x0(n)+x1(n)+x2(n)+x3(n)模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学拓展拓展 农场主在年初买了一头刚生下的小母牛，农场主在年初买了一头刚生下的小母牛，3年后的年初，年后的年初，小母牛生下了一头小母牛，下一年生下了一头小公牛，假小母牛生下了一头小母牛，下一年生下了一头小公牛，假设以后奇数年年初，那头母牛都生下一头小母牛，偶数年设以后奇数年年初，那头母牛都生下一头小母牛，偶数年年初都生下一头小公牛，而所有小母牛也会在年初都生下一头小公牛，而所有小母牛也会在3年后的年初年后的年初生下一头小母牛，下一年生下一头小公牛，且以后每年年生下一头小母牛，下一年生下一头小公牛，且以后每年年初同样会生下一头小牛。问初同样会生下一头小牛。问N（3=N=100)年后农场主有年后农场主有多少头母牛多少头母牛(假设没有一头死亡假设没有一头死亡)？输入输入一行，经过的一行，经过的N年年输出输出一行，经过一行，经过N年后的母牛的头数年后的母牛的头数输入样例输入样例8输出样例输出样例7模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学解：令解：令x0,x1,x2,xj,xs分别为刚生下的母分别为刚生下的母牛、满牛、满1周岁的母牛、满周岁的母牛、满2周岁的母牛、奇周岁的母牛、奇育龄母牛和偶育龄母牛头数，由题意得：育龄母牛和偶育龄母牛头数，由题意得：X0(0)=1;X1(0)=x2(0)=xj(0)=xs(0)=0X0(i)=xj(i)=x2(i-1)+xs(i-1)X1(i)=x0(i-1)X2(i)=x1(i-1)Xs(i)=xj(i-1)S=x0(n)+x1(n)+x2(n)+xj(n)+xs(n)模型模型模型模型2 2 2 2：前几项前几项推出当前项推出当前项 Ai-1 Ai-2 Ai-m Ai20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学模型模型模型模型3 3 3 3：前所有项前所有项推出当前项推出当前项 A1 A2 Ai-1 Ai例：栈有两种最重要的操作，即栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和（从栈顶弹出一个元素）和push（将一（将一个元素进栈）。个元素进栈）。13一个操作数序列，从一个操作数序列，从1，2，一直到，一直到n（图示为（图示为1到到3的情况），栈的情况），栈A的深度大的深度大于于n。现在可以进行两种操作，现在可以进行两种操作，1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）操作）2.将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）操作）使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由所示为由1 2 3生成序列生成序列2 3 1的过程。（原始状态如上图所示）的过程。（原始状态如上图所示）20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学模型模型模型模型3 3 3 3：前所有项前所有项推出当前项推出当前项 A1 A2 Ai-1 Ai13 使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由下图所示为由1 2 3生成序列生成序列2 3 1的过程。（原始状态如上图所示）的过程。（原始状态如上图所示）你的程序将对给定的你的程序将对给定的你的程序将对给定的你的程序将对给定的n n，计算并输出由操作数序列，计算并输出由操作数序列，计算并输出由操作数序列，计算并输出由操作数序列1 1，2 2，n n经过操作经过操作经过操作经过操作可能得到的输出序列的总数。可能得到的输出序列的总数。可能得到的输出序列的总数。可能得到的输出序列的总数。【输入格式输入格式输入格式输入格式】输入文件只含一个整数输入文件只含一个整数输入文件只含一个整数输入文件只含一个整数n n（1n181n18）【输出格式输出格式输出格式输出格式】输出文件只有一行，即可能输出序列的总数目输出文件只有一行，即可能输出序列的总数目输出文件只有一行，即可能输出序列的总数目输出文件只有一行，即可能输出序列的总数目20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学分析分析(1)(1)模拟小数据，准确理解题意。模拟小数据，准确理解题意。模拟小数据，准确理解题意。模拟小数据，准确理解题意。当当当当n n很小时，模拟入栈、出栈操作：很小时，模拟入栈、出栈操作：很小时，模拟入栈、出栈操作：很小时，模拟入栈、出栈操作：f(1)=1;f(2)=2;f(3)=5f(1)=1;f(2)=2;f(3)=5(2)(2)扩大数据规模进一步分析：扩大数据规模进一步分析：扩大数据规模进一步分析：扩大数据规模进一步分析：N=4N=4时时时时 I.I.若若若若“1”1”最先出栈，总数与最先出栈，总数与最先出栈，总数与最先出栈，总数与f(3)f(3)一样一样一样一样II.II.若若若若“1”1”第二个出栈，则第二个出栈，则第二个出栈，则第二个出栈，则“2”2”在在在在“1”1”之前出栈，之前出栈，之前出栈，之前出栈，“34”34”在在在在“1”1”之后，可以看成之后，可以看成之后，可以看成之后，可以看成N=1N=1和和和和N=2N=2的两种情况，用乘法原理，的两种情况，用乘法原理，的两种情况，用乘法原理，的两种情况，用乘法原理，f(1)*f(2)f(1)*f(2)III.III.若若若若“1”1”第三个出栈，则第三个出栈，则第三个出栈，则第三个出栈，则“1”1”前面为前面为前面为前面为“23”23”，后面，后面，后面，后面“4”4”，输出，输出，输出，输出为为为为f(2)*f(1)f(2)*f(1)IIII.IIII.若若若若“1”1”第四个出栈，则与第四个出栈，则与第四个出栈，则与第四个出栈，则与I I一样，为一样，为一样，为一样，为f(3)f(3)由此得到：由此得到：由此得到：由此得到：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3)f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3)若设若设若设若设f(0)=1f(0)=1，则有，则有，则有，则有:f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0):f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)(3)(3)由特殊到一般：经过移动后，原首项处在第由特殊到一般：经过移动后，原首项处在第由特殊到一般：经过移动后，原首项处在第由特殊到一般：经过移动后，原首项处在第i+1i+1位，其前面有位，其前面有位，其前面有位，其前面有i i位，后面有位，后面有位，后面有位，后面有n-i-1n-i-1位位位位有：有：有：有：f(nf(n)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*(f(n-3)+f(n-1)*f(0)=f(0)*f(n-1)+f(1)*f(n-2)+f(2)*(f(n-3)+f(n-1)*f(0)这个数叫这个数叫这个数叫这个数叫catalancatalan，公式为，公式为，公式为，公式为:20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学归纳推理：由特殊到一般的推理。（1）通过观察个别情况发现某些相同性质；（2）从已知的相同性质中推出一个明确表达的一般性命题（猜想）演绎推理：演绎推理是由一般到特殊的推理；类比推理的一般步骤是：（1）找出两类事物之间的相似性或一致性；（2）用一类事物的性质去推测另一类事物的性质，得出一个明确的命题（猜想）20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递推公式递归思想应用小到大找规律,猜想与验证基础扎实！基础扎实！真正理解、学会！真正理解、学会！做题后分析、比较并归类做题后分析、比较并归类20082008年冬令营年冬令营年冬令营年冬令营 江江 苏苏 省省 青青 少少 年年 信信 息息 学学 奥奥 林林 匹匹 克克 夏夏 令令 营营 C 层层 次次 教教 学学递推与递归的比较递推与递归的比较共同点：共同点：1、数据元素可以用抽象的公式表示、数据元素可以用抽象的公式表示2、具有边界条件、具有边界条件不同点：不同点：1、递推从边界出发求其结果、递推从边界出发求其结果2、递归从问题自身出发达到边界、递归从问题自身出发达到边界