且各不对应，就有-2]种方法 (2)不把它放到位置，这时，对于这-1封信，放到剩余的n-1个信封且各不对应， 有n-1]种方法。 由于(1)与(2)是同一步骤的两种不同情况，所以第二步放法总数即为(1)与(2) 这同一步骤的两种情况放法之和，即为：-2+n-l 归纳： 由以上分析可知，由于整个过程是由上述第一步、第二步两个步骤实现，因此封信 放到个信封全部放错的方法就是上述第一步与第二步放法之积，即： 推关系式：a]-(a-)*(n-1]tf[a-21)2 :f[1]=0,f2]=1 由此可以很容易得到如下的程序： #include<stdio.h> #define N 50 int main() int i.n: 1ong1 ong int f[N+1】: fr11=0: E【2]=1: canf ("d",sn) for(i=3;icn;i++) f[i]=(n-1)*(f[i-1]+f[i-2]): printf("811d\n",f(n]); 14.2.5马踏过河卒 【例14.7】马路过河卒 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下或者向右 同时在棋盘上的任一点有一个对方的马（图14.5中的C点），该马所在的点和所有跳跃 步可达的点称为对方马的控制点（如图14.5中的C点和P1,P2,·,P8)。卒不能通过对 方马的控制点。棋盘用坐标表示，A点(0,0)、B点,m),m为不超过20的整数)，同样 马的位置坐标是需要给出的，C≠A且C≠B。现在从键盘输入n、m,要计算出卒从A点 能够到达B点的路径的条数。 回
11 且各不对应，就有 f[n–2]种方法。 （2）不把它放到位置 n，这时，对于这 n–1 封信，放到剩余的 n–1 个信封且各不对应， 有 f[n–1]种方法。 由于（1）与（2）是同一步骤的两种不同情况，所以第二步放法总数即为（1）与（2） 这同一步骤的两种情况放法之和，即为：f[n-2]+f[n-1] 归纳： 由以上分析可知，由于整个过程是由上述第一步、第二步两个步骤实现，因此 n 封信 放到 n 个信封全部放错的方法就是上述第一步与第二步放法之积，即： 递推关系式 ：f[n]=(n-1)*(f[n-1]+f[n-2]) （n>2） 递推边界 ：f[1]=0,f[2]=1 由此可以很容易得到如下的程序： #include<stdio.h> #define N 50 int main() { int i,n; long long int f[N+1]; f[1]=0; f[2]=1; scanf("%d",&n); for(i=3;i<n;i++) { f[i]=(n-1)*(f[i-1]+f[i-2]); } printf("%lld\n",f[n]); } 14.2.5 马踏过河卒 【例 14.7】 马踏过河卒 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下或者向右。 同时在棋盘上的任一点有一个对方的马（图 14.5 中的 C 点），该马所在的点和所有跳跃一 步可达的点称为对方马的控制点（如图 14.5 中的 C 点和 P1，P2，.，P8）。卒不能通过对 方马的控制点。棋盘用坐标表示，A 点(0, 0)、B 点(n, m) (n, m 为不超过 20 的整数)，同样 马的位置坐标是需要给出的，C≠A 且 C≠B。现在从键盘输入 n、m，要计算出卒从 A 点 能够到达 B 点的路径的条数
P46 4.8 图14.5马踏过河卒棋盘示意图 分析 马谐过可卒是一道很老的题目，程序设计比赛中也经常出现这一问题的变形。一一看到 这种类型的题目容易让人想到用搜索来解决，但盲目的搜索仅当、m=15就会超时。可以 试着用递推来进行求解。 其实，如果对题目稍加分析就会发现，根据卒行走的规则，过河卒要到达棋盘上的一 个点，只能有两种可能：从左边过来（我们称之为左点）或是从上面过来（我们称之为上 点)，所以根据加法原理，过河卒到达某一点的路径数目，就等于其到达其相邻的上点和左 点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起点到终点的 路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。 归纳： 假设用二维数组元素表示到达点(i,j)的路径数目，用g[表示点(i,j)是 否是对方马的控制点，g0表示不是对方马的控制点，g[=1表示是对方马的控制 点。则我们可以得到如下的递推关系式： ,f[11[1]=0 当g[i]【1]==1时 当i>0,g[i]5]=0时 当1>0 9 i[j1=0时 f[i][f[i-1][j]+f[i][j-1] 当i>0,1>0,9[151-0时 上述递推关系式的边界为：00]=1。考虑到最大情况下：n=20,m=20,路径条数 可能会超出长整数范围，所以要使用long long int类型(VC+下用_int64类型)计数或高精 度运算。 为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马的初始位 置可以横向移动的位移与纵向移动的位移。有了递推关系式后，可以给出如下的程序： #include<stdio.h> int main() 1ntdx[91={0,-2,-1,1,2,2,1,-1,-21: 12
12 图 14.5 马踏过河卒棋盘示意图 分析： 马踏过河卒是一道很老的题目，程序设计比赛中也经常出现这一问题的变形。一看到 这种类型的题目容易让人想到用搜索来解决，但盲目的搜索仅当 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] 当 i>0,j>0, g[i][j]==0 时 上述递推关系式的边界为：f[0][0] = 1。考虑到最大情况下：n=20，m=20，路径条数 可能会超出长整数范围,所以要使用 long long int 类型（VC++下用_int64 类型）计数或高精 度运算。 为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马的初始位 置可以横向移动的位移与纵向移动的位移。有了递推关系式后，可以给出如下的程序： #include<stdio.h> int main() { int dx[9]={0,-2,-1,1,2,2,1,-1,-2}; 卒A
int dy[91={0,1,2,2,1,-1,-2,-2,-1i int n,m,x,y,j long long nt [201[201=(0 g[x][y]=1: for(i=1:i<=8:i++) if(x+dx[i]>=0)&(x+dx【i]<=n)&(y+dy[i]>=0)&(y+dy[i]<m) g[x+dx[i]][y+dy[i]]=1; for (i=1;i<=n;it+) f(g[i][0]=1) fi][01=1 else for(:i<=n:i+】 f[i1[0]=0 for(j=1;j<=m;j++) if(af01【111=1) E[01[j1=1: fox(:j<=m:jt+ [0][51=0 for(i=1;i<=n;i++) for（i=1:j<=m:j++) if(g[i】[]==1 else f[i][]=f[i-1][1+f[i][j-1]: printf("Sd\n",f[n][m]); return 0; 14.3递归 递归做为一种算法在程序设计中泛应用，是指函数在运行过程中直接或间接周用自 身而产生的重入现象。递归是计算机科学的一个重要概念，递归的方法是程序设计中有效 的方法，采用递归编写程序能使程序变得简洁和清晰。 3
13 int dy[9]={0,1,2,2,1,-1,-2,-2,-1}; int n,m,x,y,i,j; long long int f[20][20]={0}; int g[20][20]={0}; scanf("%d%d%d%d",&n,&m,&x,&y); g[x][y]= 1; for(i=1;i<=8;i++) if ((x+dx[i]>=0)&&(x+dx[i]<=n)&&(y+dy[i]>=0)&&(y+dy[i]<=m)) g[x+dx[i]][y+dy[i]]=1; for (i=1;i<=n;i++) { if(g[i][0]!=1) f[i][0]=1; else for(;i<=n;i++) f[i][0]=0; } for(j=1;j<=m;j++) { if(g[0][j]!=1) f[0][j]=1; else for(;j<=m;j++) f[0][j]=0; } for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if (g[i][j]==1) f[i][j]=0; else f[i][j]=f[i-1][j]+f[i][j-1]; } } printf("%d\n",f[n][m]); return 0; } 14.3 递归 递归做为一种算法在程序设计中广泛应用，是指函数在运行过程中直接或间接调用自 身而产生的重入现象。递归是计算机科学的一个重要概念，递归的方法是程序设计中有效 的方法，采用递归编写程序能使程序变得简洁和清晰
14.3.1递归的定义 递归是指在函数执行讨程中出现对自身的调用的综程方法。 一个函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复 杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程 序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力 在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段 和递归返回段。当边界条件不满足时，递归前进：当边界条件满足时，递归返回。 注意： (1)在函数中必须有直接或间接调用自身的语句。 (2)在使用递归策略时，必须有一个明确的递归结来条件，称为递归出口。 14.3.2递归的思想 递归是从问题的目标状态出发，通过自身的递归关系，层层递进，不断把问题的规模 缩小，最终达到问题的边界条件（已知的初始状态）的解题方法。也就是想要求fb()就 要先求fib(n-1)和fib(-2),而想要求fib(n-1)就要先求fib(n-2)和fib(n-3),.,想要求fib(3) 就要先求fb(2)和fb(1),而fb(2)和fb(1)是已知的。 递归的优点是程序结构清晰，不仅可以用来计数，还可以用来枚举（如汉诺塔问题）。 但在有的问题中通过直接的递归过程和函数实现起来，效率会变得很差，另外在递归调用 的过程中，系统为每一层的返回点、局部量等开辟栈来存储，递归次数过多容易造成栈溢 出。 所以，递归更多的是一种思想、一种分析问题的手法，有时需要做很多优化和改进工 作，甚至还是要转化为递推、动态规划方法去做。 递归算法一般适用在三个场合： (1)数据的定义形式是递归的，如求Fibonacci数列问题。 (2)数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。 (3)某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操 作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种 问题使用递归思想来求解比其他方法更简单。 14.4递归设计实例 14.4.1青蛙过河问题 汉诺塔问题是之前在函数一章讨论过的问题，因为它是最典型的递归问题之一，所以 在介绍其它递归问题之前，对汉诺塔问题再做一些回顾与分析。 【例14.8】汉诺(Hanoi)塔问题 14
14 14.3.1 递归的定义 递归是指在函数执行过程中出现对自身的调用的编程方法。 一个函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复 杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程 序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力 在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段 和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。 注意： （1）在函数中必须有直接或间接调用自身的语句。 （2）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 14.3.2 递归的思想 递归是从问题的目标状态出发，通过自身的递归关系，层层递进，不断把问题的规模 缩小，最终达到问题的边界条件（已知的初始状态）的解题方法。也就是想要求 fib(n)就 要先求 fib(n–1)和 fib(n–2)，而想要求 fib(n–1)就要先求 fib(n–2)和 fib(n–3),.，想要求 fib(3) 就要先求 fib(2)和 fib(1)，而 fib(2)和 fib(1)是已知的。 递归的优点是程序结构清晰，不仅可以用来计数，还可以用来枚举（如汉诺塔问题）。 但在有的问题中通过直接的递归过程和函数实现起来，效率会变得很差，另外在递归调用 的过程中，系统为每一层的返回点、局部量等开辟栈来存储，递归次数过多容易造成栈溢 出。 所以，递归更多的是一种思想、一种分析问题的手法，有时需要做很多优化和改进工 作，甚至还是要转化为递推、动态规划方法去做。 递归算法一般适用在三个场合： （1）数据的定义形式是递归的，如求 Fibonacci 数列问题。 （2）数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作。 （3）某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操 作，只是问题规模由大化小，直至某个原操作（基本操作）就结束，如汉诺塔问题，这种 问题使用递归思想来求解比其他方法更简单。 14.4 递归设计实例 14.4.1 青蛙过河问题 汉诺塔问题是之前在函数一章讨论过的问题，因为它是最典型的递归问题之一，所以 在介绍其它递归问题之前，对汉诺塔问题再做一些回顾与分析。 【例 14.8】 汉诺（Hanoi）塔问题