递推算法典型例题一、教学目标1、由浅入深，了解递推算法2、掌握递推算法的经典例题二、重点难点分析1、重点：递推关系的建立2、难点：如何将所求问题转化为数学模型三、教具或课件微机四、主要教学过程(一)引入新课客观世界中的各个事物之间或者一个事物的内部各元素之间，往往存在(隐藏)着很多本质上的关联。
我们设计程序前．应该要通过细心的观察、丰富的联想、不断的尝试推理．尽可能先归纳总结出其内在规律，然后再把这种规律性的东西抽象成数学模型，最后再去编程实现。
递推关系和递归关系都是一种简洁高效的常见数学模型，我们今天先来深入研究一下递推算法如何实现。
(二)教学过程设计递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，这样的问题可以采用递推法来解决。
从已知条件出发，逐步推出要解决的问题，叫顺推；从问题出发逐步推到已知条件，此种方法叫逆推。
无论顺推还是逆推，其关键是要找到递推式。
这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。
递推算法避开了通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。
一般说来可以将递推算法看成是一种特殊的迭代算法。
（在解题时往往还把递推问题表现为迭代形式，用循环处理。
所谓“迭代”，就是在程序中用同一个变量来存放每一次推算出来的值，每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，这种方法称为迭代。
）1．递推关系的定义和求解递推关系的方法有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成如下简捷的递推关系式：f n=g(f n-1)或者f n-1=g'(f n)这样就在数的序列中，建立起后项和前项之间的关系。
然后从初始条件(或最终结果)入手，一步步地按递推关系式递推，直至求出最终结果(或初始值)。
很多程序就是按这样的方法逐步求解的。
如果对一个试题，我们要是能找到后一项数与前一项数的关系并清楚其起始条件(或最终结果)，问题就比较容易解决，让计算机一步步计算就是了。
让高速的计算机从事这种重复运算，可真正起到“物尽其用”的效果。
递推分倒推法和顺推法两种形式。
一般分析思路：If 求解初始条件f1then begin {倒推}由题意(或递推关系)确定最终结果fn；求出倒推关系式f i-1=g'(f i)；for i←n downto 2 do f i-1←g(f i)；{从最终结果fn出发进行倒推}输出倒推结果fl；end{then}else begin {顺推}由题意(或递推关系)确定初始值f1(边界条件)；求出顺推关系式f i=g(f i-1)：for i←2 to n do f i←g(f i-1)；{由边界条件f1出发进行顺推}输出顺推结果fn；end；{else}由此可见，递推算法的时间复杂度一般为W(n)。
我们之所以将递推法划入归纳策略，是因为初始条件(或最终结果)除试题已明确给定外，都是通过对问题的整理与化简而确定的，其递推式也是对实际问题的分析与归纳而得到的，因此递推本质上属于归纳。
2．递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给出的递推关系有何性质，以及如何求解递推关系。
其中核心问题是如何建立递推关系。
建立递推关系的关键在于寻找第n项与前面(或后面)几项的关系式，以及初始项的值(或最终结果值)。
它不是一种抽象的概念，而是针对某一具体题目或一类题目而言的。
3、问题举例【例 1】有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。
例如n=3时，为2×3方格。
此时用一个1×2的骨牌铺满方格，共有3种铺法：编写一个程序，试对给出的任意一个n(n>0), 输出铺法总数。
【问题分析】（1）面对上述问题，如果思考方法不恰当，要想获得问题的解答是相当困难的。
可以用递推方法归纳出问题解的一般规律。
（2）当n=1时，只能是一种铺法如左图，铺法总数表示为X1=1；（3）当N=2时：骨牌可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所示，因此，铺法总数表示为X2=2；（4）当N=3时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要在方格中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必须在方格中排列一个竖排骨牌。
如题图，再无其他排列方法，因此铺法总数表示为x3=3. 由此可以看出，当n=3时的排列骨牌的方法数是n=1和n=2排列方法数的和。
（5）推出一般规律：对一般的n，要求X n可以这样来考虑，若第一个骨牌是竖排列放置，剩下有n-1个骨牌需要排列，这时排列方法数为X n -1；若第一个骨牌是横排列，整个方格至少有2个骨牌是横排列（1*2骨牌），因此剩下n-2个骨牌需要排列，这是骨牌排列方法数为X n -2。
从第一骨牌排列方法考虑，只有这两种可能，所以有：X n=X n -1+X n -2（N>2）X1=1X2=2以上就是问题求解的递推公式。
任给N都可以从中获得解答。
例如 N=5，X3=X2+X1=3X4=X3+X2=5X5=X4+X3=8下面是输入 N，输出X1 ~ X n的Pascal程序：program p12_20;var x,y,z:longint;i,n:integer;beginwrite('Input n:');read(n);x:=0;y:=1;for i:=1 to n dobeginz:=y+x;writeln('x[',i:2,']=',z);x:=y;y:=z;end;end.下面是运行程序输入 n=30，输出的结果：input n:30x[1]=1x[2]=2x[3]=3x[4]=5x[5]=8 ...............................x[28]=514229x[29]=832040x[30]=1346269问题的结果就是有名的斐波那契（Fibonacci）数列问题，F(1)=0，F(2)=1，在n>2时有：F(n)=F(n-1)+F(n-2)。
【例2】用迭代方法求Y=X1/3的值。
X由键盘输入。
利用下列迭代公式计算：y n + 1=2/3y n+x/(3y2n),初始值y0=x,误差要求ε=10-4。
【问题分析】（1）迭代法即反复代入法。
在上式中，将Y n代入公式的右端，可以计算出Y n + 1，然后将Y n + 1作为新的Y n代入右端，以计算出新的Y n + 1，如此重复直到|Y n + 1-Y n|<ε为止。
初始值Y0=X，意味着么一次代入公式右端的Y n的取值为X。
（2）本题算法特点：循环，变量迭代，直到前后两次的计算误差小于10-4结束并输出结果。
程序如下：program p12_21;const e=0.0001;var x,y0,y1,y2:real;beginwrite('Input x:');read(x);writeln;y1:=x;y2:=x;repeaty1:=y2;y2:=2/3*y1+x/(3*y1*y1);until abs(y2-y1)<e;writeln(x,':3x=',y2);end.当X=8则输出结果：8：3X=2.000000011E+00当X=27 则输出结果：27：3X=3.0000000018E+00【例3】过河卒(NOIP2002初中组第四题)【问题描述】棋盘上A点有一个过河卒，需要走到目标B点。
卒行走的规则：可以向下、或者向右。
同时在棋盘上的任一点有一个对方的马(如C点)．该马所在的点和所有跳跃一步可达的点称为对方马的拄制点(如下图中的c点和P1，P2，…，P8)。
卒不能通过对方马的控制点．棋盘用坐标表示，A点(0，0)、B点(n，m)(n，m为不超过20的整数)．同样马的位置坐标是需要给出的C(x,y)．C≠A C≠B。
现在从键盘输入n,m．,要你计算出卒从A点能够到达B点的路径的条数。
【问题分析】跳马一般是在学习回溯或搜索等算法的时候．很多书上也有类似的题目，一些比赛中也经常出现这一问题的变形(如NOIPl997初中组第三题)。
有些同学一看到这种类型的题目就去盲目搜索，但事实证明：当n，m=15就会超时。
其实，对本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来(我们称之为左点)或是从上面过来(我们称之为上点)。
根据加法原理．到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和．因此我们可以使用逐列(或逐行)递推的方法来求出起点到终点的路径数目。
障碍点(马的控制点)也完全适用，只要将到达该点的路径数目设置为0即可。
假设用F[i,j]表示到达点(i,j)的路径数目，用g[i,j]表示点(i,j)是否是对方马的控制点g[i,j]=0表示不是对方马的控制点,g[i,j]=1表示是对方马的控制点。
则,我们可以得到如下的递推关系式：F[0,0]=1F[i,j]=0 {g[x,y]=1]F[i,0]=F[i-1,0] {i>0，g[x,y]=0}F[0,j]=F[0,j-1] {j>0,g[x,y]=0}F[i,j]=F[i-1,j]+F[i,j-1] {i>0，j>0．G[x,y]=0}上述递推关系式的边界为：F[0,0]=l。
考虑到最大情况下；n=20,m=20．路径条数可能会超出长整数范围，所以要使用int64类型计数或高精度运算。
【参考程序】program p2_1(input,output);constdx: array[1..8] of Shortint=(-2, -1, 1, 2, 2, 1, -1, -2);dy: array[1..8] of Shortint=(1, 2, 2, 1, -1, -2, -2, -1);varn, m, x, y, i, j: Byte;g: array[0..20, 0..20] of Byte;f: array[0..20, 0..20] of int64;beginReadln(n, m, x, y);Fillchar(g, Sizeof(g), 0);g[x,y]:=1;for i:=1 to 8 doif (x+dx[i]>=0)and(x+dx[i]<=n)and(y+dy[i]>=0)and(y+dy[i]<=m)theng[x+dx[i],y+dy[i]]:=1;f[0,0]:=1;for i:=1 to n doif g[i,0]=0 then f[i,0]:=f[i-1,0];for i:=1 to m doif g[0,i]=0 then f[0,i]:=f[0, i-1];for i:=1 to n dofor j:=1 to m doif g[i,j]=0 then f[i,j]:=f[i-1,j] + f[i,j-1];writeln(f[n,m])end.解决递推类型问题有三个重点：一是如何建立正确的递推关系式．二是递推关系有何性质，三是递推关系式如何求解。