递推及递归应用.doc

递推与递归应用 一、递推思想 递推关系是一种简洁高效的常见数学模型，比如我们熟悉的Fibonacci数列问题，F（1）=0，F（2）=1，在n2时有：F（n）= F（n-1）+F（n-2）。在这种类型的问题中，每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联，这种关联一般是通过一个递推关系式来表示的。求解问题时我们就从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而得到最终结果。这种求解问题的方法叫“递推法”。其中，初始的若干数据项称为“边界”。 解决递推类型问题有三个重点：一是如何建立正确的递推关系式，二是递推关系有何性质，三是递推关系式如何求解。其中第一点是基础，也最重要。 例1、过河卒 [问题描述] 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C点和P1，P2，……，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在从键盘输入n，m，要你计算出卒从A点能够到达B点的路径的条数。 [问题分析] 跳马是一道很老的题目，一些比赛中也经常出现过这一问题的变形（如NOIP1997初中组第三题）。有些同学一看到这种类型的题目就去盲目有哪些信誉好的足球投注网站，但事实证明：当n,m=15就会超时。 其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点）或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路径数目，就等于到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。 假设用F[i,j]表示到达点(i,j)的路径数目，用g[i,j]表示点(i, j)是否是对方马的控制点，g[i,j]=0表示不是对方马的控制点，g[i,j]=1表示是对方马的控制点。则，我们可以得到如下的递推关系式： F[i,j] = 0 { g[i,j] = 1 } F[i,0] = F[i-1,0] {i 0, g[i,j] = 0} F[0,j] = F[0,j-1] {j 0, g[i,j] = 0} F[i,j] = F[i-1,j] + F[i,j-1] {i0, j0, g[i,j] = 0} 上述递推关系式的边界为：F[0,0] = 1。考虑到最大情况下：n=20,m=20，路径条数可能会超出长整数范围,所以要使用int64类型计数或高精度运算。 [参考程序] program ex1(input,output); const dx: 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); var n, m, x, y, i, j: Byte; g: array[0 .. 20, 0 .. 20] of Byte; f: array[0 .. 20, 0 .. 20] of Comp; begin Readln(n, m, x, y); Fillchar(g, Sizeof(g), 0); g[x, y] := 1; for i := 1 to 8 do if (x + dx[i] = 0) and (x + dx[i] = n) and (y + dy[i] = 0) and (y + dy[i] = m) then g[x + dx[i], y + dy[i]] := 1; f[0, 0] := 1; for i := 1 to n do if g[i, 0] = 0 then f[i, 0] := f[i - 1, 0]; for i := 1 to m do if g[0, i] = 0 then f[0, i] := f[0, i - 1]; for i := 1 to n do for j := 1 to m do if g[i, j] = 0 then f[i, j] := f[i - 1, j] + f[i, j - 1]; Writeln(f[n, m]: 0: 0) end. 递推法按照推导问题的方向，