第五讲--递推与递归

1、第五讲第五讲 递推与递归递推与递归主要内容主要内容递推及其应用递推及其应用递归及其应用递归及其应用 第五讲第五讲 递推与递归递推与递归递推递推是通过数学推导，将复杂的运算化解为是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。重复处理的特点。递归是递归是将复杂的操作分解为简单操作的多次将复杂的操作分解为简单操作的多次重复，一般用函数调用完成重复，一般用函数调用完成。 11.1 递递 推推11.1 递递 推推11.1 递递 推推例如：例如：Fibonacci数列问题数列问题 已知：已知：F (1) = 0 ，F(2)

2、 = 1， 若：若： n2，则，则F(n)= F(n-1)+F(n-2)注意：注意： 1）每个数据项都和它前面的若干个数据项（或后面的若干每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联个数据项）有一定的关联-递推关系式。递推关系式。 2）从初始的一个或若干数据项出发，通过递推关系式逐步从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而得到最终结果。推进，从而得到最终结果。11.1 递递 推推注意：注意：3）递推必须有）递推必须有 “边界边界”。4）解决递推类型问题有三个重点：）解决递推类型问题有三个重点： 如何建立正确的递推关系式；如何建立正确的递推关系式； 递

3、推关系有何性质；递推关系有何性质； 递推关系式如何求解。递推关系式如何求解。基础，重点基础，重点11.1 递递 推推按照推导问题的方向，递推分为：按照推导问题的方向，递推分为：l 顺推法：顺推法：从初始数据开始推理。从初始数据开始推理。 例如：例如：n=0n=0时，时，n!=1n!=1； n1n1时，时，n!=nn!=n* *(n-1)!(n-1)!l 倒推法：倒推法：从结果数据开始推理。从结果数据开始推理。 例如：例如：n!=nn!=n* *(n-1)! (n-1)! ； 边界：边界：n=0n=0，n!=1n!=1例例1：猴子第猴子第1天摘下若干个桃子，当即吃了一半天摘下若干个桃子，当即吃了

4、一半又一个。第又一个。第2天又把剩下的桃吃了一半又一个，以天又把剩下的桃吃了一半又一个，以后每天都吃前一天剩下的桃子的一半又一个，到第后每天都吃前一天剩下的桃子的一半又一个，到第10天猴子想吃时，只剩下一个桃子。天猴子想吃时，只剩下一个桃子。问：问：猴子第猴子第1天一共摘了多少桃子天一共摘了多少桃子? 分析：分析：已知条件：已知条件：第第 10 天剩下天剩下 1 个桃子；个桃子；隐含条件：隐含条件：每一次前一天的桃子个数等于后一天每一次前一天的桃子个数等于后一天桃子的个数加桃子的个数加 1 的的 2 倍。倍。逆向思维：逆向思维：从后往前推，可用倒推法求解。从后往前推，可用倒推法求解。 #inc

5、lude void main( ) int i,a=1;for (i=9; i=1; i-) a=(a+1)*2;printf(a=%dn,a); 例例1：逆推法逆推法-求解猴子吃桃子求解猴子吃桃子例例2：猴子分食桃子：猴子分食桃子1) 五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。食。2) 半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。现还多一个，它吃掉这桃子，并拿走了其中一堆。3)第二只猴子醒来，又把桃子均分成五堆后，还是多了一第二只猴子醒来，

6、又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。第三只，第四只，第五只猴子都依次如此分食桃子。问：问：五只猴子采得一堆桃子五只猴子采得一堆桃子数最少应该有几个呢？数最少应该有几个呢？逆推法逆推法算法分析：算法分析： 先要找第先要找第N只猴子和其面前桃子数的关系。如只猴子和其面前桃子数的关系。如果从第果从第1只开始往第只开始往第5只找，不好找，但如果思路只找，不好找，但如果思路一变，从第一变，从第N到第到第1去，可得出下面的推导式：去，可得出下面的推导式： 第第N只猴只猴 第第N只猴前桃

7、子数目只猴前桃子数目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1通过递推，求出通过递推，求出s1即可即可例例2：猴子分食桃子：猴子分食桃子-逆推法逆推法注意：其中的注意：其中的s1、s2、s3、s4、s5必须是整数必须是整数/例例2：猴子分食桃子：猴子分食桃子-逆推法逆推法#include void main() int x,s,k,i;x=6; / 最少的初值最少的初值k=0; / 整除标志整除标志while ( k!=4)s=x;k=0;for ( i=4; i=1; i-) if ( s%4 = 0) k+; els

8、e break; s=s*5/4+1; x=x+5;printf(s=%dn,s);11.1.2 递推设计实例递推设计实例例例11.1：母牛的故事：母牛的故事 问题描述：问题描述：有一头母牛，它每年年初生一头小有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，母牛。每头小母牛从第四个年头开始，每年年每年年初也生一头小母牛。初也生一头小母牛。编程实现：编程实现：在第在第n年的时候，共有多少头母牛？年的时候，共有多少头母牛？例例11.1：母牛的故事：母牛的故事-顺推法顺推法 设数组设数组f(i)表示第表示第 i 年的母牛总数，则第年的母牛总数，则第 n 年的母牛总数为年的母牛总数为f

9、(n) 。 f(n) 与两个值有关与两个值有关 在本年之前就已经出生的母牛数目在本年之前就已经出生的母牛数目 在本年新出生的小母牛数目。在本年新出生的小母牛数目。1） 本年之前就已经出生的母牛数目，实际上就是前一年的母牛本年之前就已经出生的母牛数目，实际上就是前一年的母牛总数总数-f（n-1）。）。2） 由于每一头母牛每年只生育一头小母牛，所以在本年新出生由于每一头母牛每年只生育一头小母牛，所以在本年新出生的小母牛数目，实际上是到今年可以生育的母牛的数目。的小母牛数目，实际上是到今年可以生育的母牛的数目。3) 而每头小母牛从第四个年头才开始生育，所以今年可以生育的而每头小母牛从第四个年头才开始

10、生育，所以今年可以生育的母牛的数实际上就是三年前的母牛总数，即为母牛的数实际上就是三年前的母牛总数，即为f（n-3）。例例11.1：母牛的故事：母牛的故事-顺推法顺推法递推公式：递推公式： f(n)=f(n-1)+f(n-3) （n=4） f (1) =1； f (2) =2; f (3) =3；递推边界递推边界 若数组若数组f(i)表示第表示第 i 年的母牛总数，则第年的母牛总数，则第 n 年的母牛总年的母牛总数为数为f(n) 。 例例11.1：母牛的故事：母牛的故事-顺推法顺推法#include void main() _int64 f50; / _int64 - 定义大整数定义大整数 i

11、nt i,n; scanf(%d,&n); f1=1; f2=2; f3=3; for(i=4; i=n; i+) fi=fi-3+fi-1; printf(%I64dn,fi); / %I64d大整数输入大整数输入/输出格式输出格式 例例11.2 骨牌问题骨牌问题-顺推法顺推法例例11.2 骨牌问题骨牌问题-顺推法顺推法例例11.2 骨牌问题骨牌问题-顺推法顺推法 例例11.2 骨牌问题骨牌问题-顺推法顺推法因此，因此，n块骨牌的铺法块骨牌的铺法是是首块骨牌横铺方式的首块骨牌横铺方式的铺法与竖铺方式的铺法之和。铺法与竖铺方式的铺法之和。 即：即： f(n)=f(n-1)+f(n-2)边界：边

12、界： f(1)=1 ，f(2)=2例例11.2 骨牌问题骨牌问题-顺推法顺推法递推公式递推公式 #include int main() int i,n, f20; f0=1; f1=2; / 边界边界 scanf(%d,&n); for(i=2;in;i+) fi=fi-1+fi-2; / 递推递推 printf(%dn,fi); 例例11.2 骨牌问题骨牌问题#includevoid main() int i,n; _int64 f50; f0=1; f1=2; / 边界边界 scanf(%d,&n); for(i=2;in;i+) fi=fi-1+fi-2; / 递推递推 printf(%

13、I64dn,fn-1); 例例11.2 骨牌问题骨牌问题-顺推法顺推法问题描述：问题描述： 设有一个共有设有一个共有n级的楼梯，某人每步可走级的楼梯，某人每步可走1级，也可走级，也可走2级，也可走级，也可走3级。级。问：问：求从底层开始走完全部楼梯的有多少种走法。求从底层开始走完全部楼梯的有多少种走法。例如，当例如，当n=3时，走法如下：时，走法如下： 1+1+1 1+2 2+1 3思考：上楼问题思考：上楼问题n=3，共有，共有4种走法种走法n的值的值 走法走法f(n) 1 1 2 2 3 4 4 7从递推的思想出发从递推的思想出发，可以设想，从第，可以设想，从第4 4项项开始，每开始，每1

14、1项等于前面项等于前面3 3项的和。项的和。上楼问题上楼问题-算法分析算法分析 f(n)=f(n-1)+f(n-2)+f(n-3)-递推公式递推公式 f(1)=1 , f(2)=2 , f(3)=4 -递推边界递推边界 #include /上楼问题上楼问题 void main( ) int x,n,i,a,b,c;scanf(%d,&n);a=1; b=2; c=4; if (n=1) x=1;else if (n=2) x=2; else if (n=3) x=4; for (i=4; i=n; i+) x=a+b+c; a=b; b=c; c=x; printf(%d,x); 例例11.3

15、 错排信件错排信件问题描述：问题描述：某人写了某人写了n封信封信和和n个信封个信封，所所有的信都装错了信封。有的信都装错了信封。要求：若要求：若所有的信都装错信封，共有多少所有的信都装错信封，共有多少种不同情况？种不同情况？例例11.3 错排信件错排信件找规律：找规律：对对n封信封信以及以及n个信封个信封各自按照从各自按照从 1.n 进行进行编号；编号； f(n)-n个编号的信个编号的信放在放在n个编号的信封，个编号的信封，各各不对应的方法数；不对应的方法数；f(n-1)-n-1个编号的信放在个编号的信放在n-1个编号位置的个编号位置的信封，各不对应的方法数。信封，各不对应的方法数。例例11.

16、3 错排信件错排信件找规律：找规律： 第一步第一步: 把把第第n封信封信放在第放在第k个信封（个信封（kn），不对应的共有），不对应的共有n-1种方法；种方法； 第二步第二步: 放编号为放编号为 k 的信，有两种情况：的信，有两种情况： 1）放编号为放编号为 k 的信的信放到第放到第n个信封个信封，则对于剩下的，则对于剩下的n-2封信，封信，需要放到剩余的需要放到剩余的n-2个信封且各不对应，就有个信封且各不对应，就有f(n-2)种方法；种方法； 2）放编号为放编号为 k 的信的信不放到位置不放到位置n，对于这对于这n-1封信，放到剩余封信，放到剩余的的n-1个信封且各不对应，有个信封且各不对

17、应，有f(n-1)种方法；种方法； 结论：结论： f(n) = (n-1) * ( f (n-2) + f (n-1) ) 特例：特例：f（1）= 0， f（2）= 1 -边界边界例例11.3 错排信件错排信件 #include void main() int i,n, f20; f1=0;f2=1; scanf(%d,&n); for(i=3;i=n;i+) fi=(i-1)*(fi-2+fi-1); printf(%dn,fi); 例例11.4 马踏过河卒马踏过河卒-选讲选讲 棋盘上棋盘上A点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标B点。点。 卒行走的规则：可以向下、或者向右

18、。卒行走的规则：可以向下、或者向右。 同时在棋盘上的任一点有一个对方的马（如下图中的同时在棋盘上的任一点有一个对方的马（如下图中的C点），该点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的图中的C点和点和P1，P2，P8）。）。 卒不能通过对方马的控制点。棋盘用坐标表示，卒不能通过对方马的控制点。棋盘用坐标表示，A点点(0,0)、B点点(n, m) (n,m为不超过为不超过20的整数的整数)，同样马的位置坐标是需要给出的，同样马的位置坐标是需要给出的，CA且且CB。编程：编程：输入输入n，m，计算出卒，计算出卒从从A

19、点能够到达点能够到达B点的路径的条数。点的路径的条数。例例11.4 马踏过河卒马踏过河卒-选讲选讲 马踏过河卒是一道很老的题目，一些程序设计比赛中马踏过河卒是一道很老的题目，一些程序设计比赛中也经常出现过这一问题的变形。一看到这种类型的题也经常出现过这一问题的变形。一看到这种类型的题目容易让人想到用搜索来解决，但盲目的搜索仅当目容易让人想到用搜索来解决，但盲目的搜索仅当n,m=15就会超时。可以试着用递推来进行求解。就会超时。可以试着用递推来进行求解。 根据卒行走的规则，过河卒要到达棋盘上的一个点，根据卒行走的规则，过河卒要到达棋盘上的一个点，只能有两种可能：只能有两种可能：从左边过来（左点）

20、或是从上面过从左边过来（左点）或是从上面过来（上点），所以根据加法原理，过河卒到达某一点来（上点），所以根据加法原理，过河卒到达某一点的路径数目，就等于其到达其相邻的的路径数目，就等于其到达其相邻的上点和左点上点和左点的路的路径数目之和，因此可用逐列（或逐行）递推的方法求径数目之和，因此可用逐列（或逐行）递推的方法求出从起点到终点的路径数目。障碍点（马的控制点）出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达也完全适用，只要将到达该点的路径数目设置为该点的路径数目设置为0即可即可。 例例11.4 马踏过河卒马踏过河卒-选讲选讲 用二维数组元素用二维数组元素fijfij表示到

21、达点（表示到达点（i i，j j）的路径数目；）的路径数目； 用用gijgij表示点（表示点（i i，j j）是否是对方马的控制点；）是否是对方马的控制点； 若若gij=0gij=0表示不是对方马的控制点，表示不是对方马的控制点，gij=1gij=1表示是对表示是对方马的控制点。方马的控制点。则可以得到如下的递推关系式：则可以得到如下的递推关系式： fij = 0 fij = 0 当当 gij=1gij=1 fi0 = fi-10 fi0 = fi-10 当当 i i0, gij=00, gij=0 f0j = f0j-1 f0j = f0j-1 当当 j j0, gij=00, gij=0

22、fij = fi-1j + fij-1 fij = fi-1j + fij-1 当当 i i0, j0, j0, gij=00, gij=0 递推边界：递推边界：f00 = 1 #include / 马踏过河卒马踏过河卒 int main() int i,j,n,m,f2020,g2020,x,y; scanf(%d %d %d %d,&n,&m,&x,&y); for (i=1;i=n;i+)for (j=1;j=m;j+) fij=0; for (i=0;i=n;i+) for (j=0;j=m;j+) gij=0;gxy=1; gx-1y-2=1; gx+1y-2=1;gx-2y-1=1

23、; gx+2y-1=1; gx-2y+1=1;gx+2y+1=1; gx-1y+2=1; gx+1y+2=1;for (i=1;i=n;i+)if(gi0!=1) fi0=1;else for (;i=n;i+) fi0=0;for (j=1;j=m;j+)if(g0j!=1) f0j=1;else for(;j=m;j+) f0j=0;for (i=1;i=n;i+) for (j=1;j=m;j+)if (gij=0) fij=fi-1j+fij-1;printf(%dn,fnm);return 0;例例11.4 马踏过河卒马踏过河卒改进改进为了更简洁地表示马的控制点，可以引入两个一维数组

24、，分别用来为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马的初始位置可以横向移动的位移与纵向移动的位移。统计从马的初始位置可以横向移动的位移与纵向移动的位移。程序的改进如下：程序的改进如下：#includeint main() int dx9=0,-2,-1,1,2,2,1,-1,-2; int dy9=0,1,2,2,1,-1,-2,-2,-1; int n,m,x,y,i,j; int f2020=0,g2020=0; scanf(%d%d%d%d,&n,&m,&x,&y); gxy= 1;例例11.4 马踏过河卒马踏过河卒 for(i=1;i=0)&(x+dxi=0)&

25、(y+dyi=m)gx+dxiy+dyi=1; for(i=1;i=n;i+) if (gi0!=1) fi0=1; else for(;i=n;i+)fi0=0; for(j=1;j=m;j+) if(g0j!=1) f0j=1; else for(;j=m;j+) f0j=0; for(i=1;i=n;i+) for(j=1;j=m;j+)if (gij=1) fij=0; else fij=fi-1j+fij-1; printf(%dn,fnm); return 0; 递推应用：王小二切饼，要求每递推应用：王小二切饼，要求每2条线都有交点。条线都有交点。 找规律：王小二切饼，要求每找规律

26、：王小二切饼，要求每2条线都有交点。条线都有交点。规律：规律：p(n)=p(n-1)+n #include / 用递推求解用递推求解-切饼问题切饼问题 int main() int n,i; int p100; p0=1;scanf(%d,&n);for (i=1;i=n;i+) pi=pi-1+i; printf(%dn,pi); return 0; 递推思考递推思考输出输出杨晖三角形的前杨晖三角形的前10行。行。杨晖三角形的前杨晖三角形的前5行如左下图所示。行如左下图所示。问题分析：问题分析：观察左上图不太容易找到规律，但如果观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现

27、杨辉三角形其实将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。就是一个二维表（数组）的下三角部分。#include /打印杨辉三角形打印杨辉三角形void main() int i,j，a1010; for (i=0;i10;i+) ai0=1; for (i=0;i10;i+) for (j=i+1;j10;j+) aij=0; for (i=1;i10;i+) for (j=1;j=i;j+) aij=ai-1j-1+ai-1j; for (i=0;i10;i+) for (j=0;j=i;j+) printf(%4d,aij); printf(n); 递推

28、小结递推小结1）递推是）递推是从已知条件从已知条件开始；开始；2）递推）递推必须有明确必须有明确的通用公式；的通用公式；3）递推）递推必须是有限次必须是有限次运算。运算。11.2 递归递归递归的定义：递归的定义：在一个函数的定义中在一个函数的定义中又直接或间又直接或间接调用自身接调用自身的一种方法，它通常把一个大型的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。规模较小的问题来求解。11.2 递归递归递归思想：递归思想： 把规模大的、较难解决的问题变成规模较小的、把规模大的、较难解决的问题变成规模较小的、易解决的同一

29、问题。规模较小的问题又变成规模更小的问易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。来问题的解。 递归优点：递归优点：只需少量的程序就可描述出解题过程所需要的只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。用递归算法多次重复计算，大大地减少了程序的代码量。用递归算法编写的程序结构清晰，具有很好的可读性。编写的程序结构清晰，具有很好的可读性。 递归缺点：递归缺点：通过直接的递归过程和函数实现起来，有时效通过直接的递归过程和函数实现起来，有时效率很差（

30、用递归函数去求率很差（用递归函数去求1000!）。）。递归算法适用在三个场合递归算法适用在三个场合1) 数据数据的定义形式是递归的，如求的定义形式是递归的，如求n! ；2) 数据之间数据之间的逻辑关系（即数据结构）是递归的，的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作；如树、图等的定义和操作；3) 某些问题某些问题虽然没有明显的递归关系或结构，但虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问问题的解法是不断重复执行一种操作，只是问题规模由大化小，直至某个原操作（基本操作）题规模由大化小，直至某个原操作（基本操作）就结束。例如：就结束。例如：汉诺塔问题。汉诺

31、塔问题。递归设计的要件递归设计的要件(1) 在函数中必须有直接或间接调用自身的语句；在函数中必须有直接或间接调用自身的语句；(2) 在使用递归策略时，必须有一个明确的递归结在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口（或递归边界）。束条件，称为递归出口（或递归边界）。编写递归算法程序时，首先要对问题的以下三个方面进行分析：编写递归算法程序时，首先要对问题的以下三个方面进行分析： u决定问题规模的参数。决定问题规模的参数。 需要用递归算法解决的问题，其规模通常都是比较大的，在需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？问题中

32、决定规模大小（或问题复杂程度）的量有哪些？u问题的边界条件及边界值。问题的边界条件及边界值。 在什么情况下可以直接得出问题的解？在什么情况下可以直接得出问题的解？- -问题的边界条件及问题的边界条件及边界值。边界值。 u解决问题的通式解决问题的通式。 把规模大的、较难解决的问题变成规模较小、易解决的同一把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？问题，需要通过哪些步骤或等式来实现？-解决递归问题的难解决递归问题的难点，把这些步骤或等式确定下来。点，把这些步骤或等式确定下来。 递归设计实例递归设计实例1 -哈诺（哈诺（HanoiHanoi）塔问题：）塔

33、问题：1)1)相传在古代印度的相传在古代印度的 Bramah Bramah 庙中，有位僧人整天把三根柱子庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把上的金盘倒来倒去，原来他是想把6464个一个比一个小的金盘个一个比一个小的金盘从一根柱子上移到另一根柱子上去。从一根柱子上移到另一根柱子上去。2)2)移动规则：移动规则：每次只允许移动一只盘，大盘不得落在小盘上面。每次只允许移动一只盘，大盘不得落在小盘上面。3)3)如以每秒移动一只盘子如以每秒移动一只盘子，按照上述规则，按照上述规则将将6464只盘子从一个柱只盘子从一个柱子移至另一个柱子上，所需时间约为子移至另一个柱子上，所需时间约为

34、58005800亿年。亿年。 先从最简单的情况开始分析，理出思路。先从最简单的情况开始分析，理出思路。1、在在 A 柱上只有一只盘子柱上只有一只盘子，假定盘号为，假定盘号为 1，这时，这时只需将该盘从只需将该盘从 A 搬至搬至 C，一次完成，记为，一次完成，记为: move 1# from A to C ABC12、在在 A 柱上柱上有有 2 只盘子，只盘子，1 为小盘，为小盘，2 为大盘。为大盘。第（第（1）步将步将1号盘从号盘从A移至移至B，这是为了让，这是为了让 2号盘能动；号盘能动； move 1# from A to B;第（第（2）步将步将 2 号盘从号盘从A 移至移至 C； mo

35、ve 2# from A to C;第（第（3）步再将步再将 1 号盘从号盘从 B 移至移至 C； move 1# form B to C;ABC213、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号号第（第（1）步）步 ：将将1号盘和号盘和2号盘视为一个整体；先将二者号盘视为一个整体；先将二者作为整体从作为整体从A移至移至B，给，给3号盘创造能够一次移至号盘创造能够一次移至C的机的机会。会。这一步记为这一步记为 move( 2, A, C, B) 含义：含义：将上面的将上面的2只盘子作为整体从只盘子作为整体从A借助借助C移至移至B。第（第（2）步）

36、步 ：将将3号盘从号盘从A移至移至C，一次到位。记为，一次到位。记为 move 3# from A to C第（第（3）步）步 ：处于处于B上的作为一个整体的上的作为一个整体的2只盘子，再移只盘子，再移至至C。这一步记为。这一步记为 move( 2, B, A, C)含义：含义：将将2只盘子作为整体从只盘子作为整体从B借助借助A移至移至C。move (3, A, B, C)move (2, A, C, B)move (1, A, B, C)move (2, B, A, C)ABC213移动移动3 3个盘子的分解：个盘子的分解：move (3, A, B, C)move (2, A, C, B)

37、move (1, A, B, C)move (1, A, C, B)move (1, C, A, B)move (1, A, B, C)move (2, B, A, C)move (1, B, C, A)move (1, B, A, C)move (1, A, B, C)ABC2134、从题目的约束条件看，大盘上可以随便摞小、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将盘，相反则不允许。在将1号和号和2号盘当整体从号盘当整体从A移至移至B的过程中的过程中 move(2, A, C, B) 实际上是分实际上是分解为以下三步解为以下三步第（第（1）.1步：步：move 1# for

38、m A to C;第（第（1）.2步：步：move 2# form A to B;第（第（1）.3步：步：move 1# form C to B;经过以上步骤，将经过以上步骤，将 1 号和号和 2 号盘作为整体号盘作为整体从从 A 移至移至 B，为，为 3 号盘从号盘从 A 移至移至 C 创造了条创造了条件。同样，件。同样，3号盘一旦到了号盘一旦到了 C，就要考虑如何，就要考虑如何实现将实现将 1 号和号和 2 号盘当整体从号盘当整体从 B 移至移至 C 的过的过程了。实际上程了。实际上 move( 2, B, A, C ) 也要分解为也要分解为三步：三步：第（第（3）.1步：步：move 1

39、# form B to A;第（第（3）.2步：步：move 2# form B to C;第（第（3）.3步：步：move 1# form A to C;5、move(2, A, C, B) 是将是将 2 只盘子从只盘子从 A 搬至搬至 B，但没有但没有 C 不行，因为第（不行，因为第（1）.1步就要将步就要将 1# 盘盘从从 A 移到移到 C，给，给2 #盘创造条件从盘创造条件从 A 移至移至 B，然后再把然后再把 1# 盘从盘从 C 移至移至 B。 注意：在注意：在move(2, A, C, B)中，中， C 是一个桥梁用。是一个桥梁用。move(n, A, B, C) 分解为分解为3步

40、：步：(1) move(n-1, A, C, B) ：将：将 n-1 只盘子作为一个整体只盘子作为一个整体从从A经经C移到移到B；(2) 输出输出n：A to C：将将n号盘从号盘从A移到移到C，是直接可，是直接可解结点；解结点；(3) move(n-1, B, A, C)：将将n-1只盘子作为一个整体从只盘子作为一个整体从B经经A移到移到C。-递归递归实现实现 move(n-1, A, C, B)要分为要分为 3 步：步：第第1步：步：将将 n-2 只盘子作为一个整体从只盘子作为一个整体从A经经B到到C - move(n-2, A, B, C)；第第2步：步：第第n-1号盘子从号盘子从A直接

41、移至直接移至B，即，即 n-1:A to B；第第3步：步：将将 n-2 只盘子作为一个整体从只盘子作为一个整体从C经经A移至移至B - move(n-2, C, A, B)；/m表示盘子数目表示盘子数目; a，b，c表示柱子标号表示柱子标号 void move(int m, char a, char b, char c) if (m=1)/ 如果如果1个盘子，则为直接可解结点个盘子，则为直接可解结点 step+;/ 步数加步数加1 printf(n%d move 1# from %c to %cn,step,a,c); else move(m-1,a,c,b);/ 递归调用递归调用move(

42、m-1) /直接可解结点直接可解结点,输出移盘信息输出移盘信息 step+;/ 步数加步数加1 printf(n%d move %d# from %c to %cn,step,m,a,c ); move(m-1,b,a,c);/ 递归调用递归调用move(m-1) #include / 用递归求解用递归求解Hanoi问题问题 int step=0; / 整型全局变量，移动步数整型全局变量，移动步数 int main() int n; printf(请输入盘数请输入盘数 n=); scanf(%d,&n); printf(在在3根柱子上移根柱子上移 %d 只盘的步骤为只盘的步骤为:,n); mo

43、ve(n,A,B,C); return 0; 该题是该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：年全国青少年信息学奥林匹克的一道试题。叙述如下： 1）一条小溪尺寸不大，一条小溪尺寸不大，青蛙可以从左岸跳到右岸青蛙可以从左岸跳到右岸，在左岸有一石，在左岸有一石柱柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面，面积也只容得下一只青蛙落脚。积也只容得下一只青蛙落脚。2）有一队青蛙从小到大编号：有一队青蛙从小到大编号：1，2，n。3）初始时：）初始时：青蛙只能趴在左岸的石头青蛙只能趴在左岸的石头 L 上，按编号一个落一个，上，按

44、编号一个落一个，小的落在大的上面。不允许大的在小的上面。小的落在大的上面。不允许大的在小的上面。递归设计实例递归设计实例2该题是该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：年全国青少年信息学奥林匹克的一道试题。叙述如下：4）在小溪中有在小溪中有S个石柱，有个石柱，有y片荷叶，规定溪中的片荷叶，规定溪中的石柱如有多只青石柱如有多只青蛙也是蛙也是大在下、小在上，而且大在下、小在上，而且必须编号相邻必须编号相邻；5）对于对于荷叶只允许一只青蛙落脚荷叶只允许一只青蛙落脚，不允许多只落在其上；，不允许多只落在其上；6）对于右岸的对于右岸的石柱石柱R，与左岸的石柱，与左岸的石柱L一样允许

45、多个青蛙落脚一样允许多个青蛙落脚，但，但须一个落一个，小的在上，大的在下，且编号相邻；须一个落一个，小的在上，大的在下，且编号相邻；7）当青蛙从左岸的当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸上跳至右岸R，或从溪中荷叶、溪中石柱跳至右岸，或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也上的青蛙也不允许再离开。不允许再离开。问：问：在已知溪中有在已知溪中有 s 根石柱根石柱和和 y 片片荷叶的情况下，最多能跳过多少荷叶的情况下，最多能跳过多少只青蛙？只青蛙？思路：思路：先从柱子和荷业较少的情况开始分析，先从柱子和荷业较少的情况开始分析，对多

46、个因素作分解，找出规律。对多个因素作分解，找出规律。1、 定义函数定义函数 Jump ( s ,y ) 最多可跳过河的青蛙数最多可跳过河的青蛙数 其中：其中： s 河中柱子数河中柱子数 y 荷叶数荷叶数2、河中无柱子：、河中无柱子：S=0，即，即Jump(0,y) y=1时，河中有一片荷叶，起始时时，河中有一片荷叶，起始时L上有两只青蛙，上有两只青蛙，1#在在2#上面。上面。 第一步：第一步：1# 跳到荷叶上；跳到荷叶上； 第二步：第二步：2# 从从L直接跳至直接跳至R上；上； 第三步：第三步：1# 再从荷叶跳至再从荷叶跳至R上。上。 结论：结论：Jump(0,1)=2； / 河中有河中有1片

47、片荷叶，能过荷叶，能过2只只青蛙。青蛙。左岸L右岸R荷叶当当y=2时河中有两片荷叶时，起始时：时河中有两片荷叶时，起始时：1#，2#，3# -共共3只青蛙落在只青蛙落在L上，上， 第一步：第一步：1# 从从L跳至叶跳至叶 1上，上， 第二步：第二步：2# 从从L跳至叶跳至叶 2上，上， 第三步：第三步：3# 从从L直接跳至直接跳至R上，上， 第四步：第四步：2# 从叶从叶2跳至跳至R上，上， 第五步：第五步：1# 从叶从叶1跳至跳至R上上 结论：结论： Jump(0,2)=3；/ 河中有河中有2片荷叶，能过片荷叶，能过3只青蛙。只青蛙。左岸左岸L右岸右岸R荷叶荷叶2荷叶荷叶12、河中无柱子：、

48、河中无柱子：S=0，即，即Jump(0,y)小结：小结： Jump ( 0 ,1 ) = 2 ； -能跳过能跳过2只青蛙只青蛙 Jump ( 0 , 2 ) = 3 ； -能跳过能跳过3只青蛙只青蛙思考：思考： Jump(0,3) = ? Jump(0,4) = ? Jump(0,y) = ?归纳法：归纳法：Jump(0,y)=y+1含义：含义：没有石柱时，没有石柱时，过河青蛙数过河青蛙数=荷叶数荷叶数+13、河中有石柱、河中有石柱Jump(S, y) = ？ 一个最简单情况：一个最简单情况：S=1、y=1时：时： 1# 青蛙从青蛙从 L Y； 2# 青蛙从青蛙从 L S； 1# 青蛙从青蛙从

49、 Y S； 3# 青蛙从青蛙从 L Y； 4# 青蛙从青蛙从 L R；左岸左岸L右岸右岸R荷叶荷叶Y石柱石柱S 3# 青蛙从青蛙从 Y R； 1# 青蛙从青蛙从 S Y； 2# 青蛙从青蛙从 S R； 1# 青蛙从青蛙从 Y R；结论：结论：Jump(1,1)=4 2*Jump(0,1)=2*2参照汉诺塔问题将借助参照汉诺塔问题将借助一个石柱一个石柱( s=1 )、一个荷叶、一个荷叶( y=1 )的青蛙的青蛙跳跃问题分成五个步骤：跳跃问题分成五个步骤：第一步：第一步：借助借助荷叶荷叶将将左左岸上面的若干青蛙（此时是岸上面的若干青蛙（此时是1#与与2#两只）两只）跳到跳到石柱石柱上暂存；上暂存；

50、第二步：第二步：左岸左岸下一下一只青蛙（此时是只青蛙（此时是3#）跳到）跳到荷叶荷叶上；上；第三步：第三步：左岸左岸再下一只青蛙再下一只青蛙（此时是（此时是4#）跳到）跳到右岸；右岸；第四步：荷叶暂存的青蛙（第四步：荷叶暂存的青蛙（ 3# ）跳到）跳到到右岸；到右岸；第五步：石柱上暂存青蛙（第五步：石柱上暂存青蛙（1#、2#）借助荷叶完成到跳到右岸。借助荷叶完成到跳到右岸。以上的以上的石柱石柱如果看成右岸如果看成右岸(步骤步骤1)或左岸（步骤或左岸（步骤2）的话，进一）的话，进一步的分析，还可以将上述步的分析，还可以将上述五个步骤五个步骤分成以下两个阶段：分成以下两个阶段： 第一、五两步第一、

51、五两步实际上完成的就是青蛙借助一个荷叶跳跃的实际上完成的就是青蛙借助一个荷叶跳跃的过程，并且这两步的对象是同一批青蛙，青蛙个数是过程，并且这两步的对象是同一批青蛙，青蛙个数是Jump(0,1)。 第二、三、四步第二、三、四步实际上完成的也是青蛙借助一个荷叶跳跃实际上完成的也是青蛙借助一个荷叶跳跃的过程，青蛙个数是的过程，青蛙个数是Jump(0,1)。所以：所以：Jump(1,1)的值是的值是Jump(0,1)+ Jump(0,1) 即：即：Jump(1,1)=2*Jump(0,1)；对于借助对于借助s个石柱、个石柱、y个荷叶的青蛙跳跃过程也可以类似的归纳出来，个荷叶的青蛙跳跃过程也可以类似的归

52、纳出来，这个实现步骤可以分成七个步骤：这个实现步骤可以分成七个步骤： 第一步：第一步：借助所有借助所有荷叶荷叶以及其余以及其余石柱石柱将左岸上面的若干青蛙跳到将左岸上面的若干青蛙跳到第一第一个石柱上个石柱上暂存；暂存； 第二步：第二步：左岸左岸余下的青蛙余下的青蛙借助其它可用的借助其它可用的石柱以及所有荷叶石柱以及所有荷叶跳到跳到其它石柱其它石柱上；上； 第三步：第三步：左岸左岸再余下的青蛙跳到所有荷叶再余下的青蛙跳到所有荷叶上；上； 第四步：第四步：左岸左岸再下一只青蛙完成到右岸的直接跳跃再下一只青蛙完成到右岸的直接跳跃-最大最大1只只 第五步：第五步：荷叶暂存的青蛙完成到右岸的跳跃；荷叶暂

53、存的青蛙完成到右岸的跳跃； 第六步：第六步：除了第一个外其余石柱上暂存青蛙完成到右岸的跳跃；除了第一个外其余石柱上暂存青蛙完成到右岸的跳跃； 第七步：第七步：第一个石柱上暂存的青蛙借助其余石柱以及所有荷叶完第一个石柱上暂存的青蛙借助其余石柱以及所有荷叶完成到右岸的跳跃；成到右岸的跳跃；如果以上的石柱在跳跃过程中可以看成右岸或左岸，这七个如果以上的石柱在跳跃过程中可以看成右岸或左岸，这七个步骤也可以简化成两个阶段：步骤也可以简化成两个阶段： 第一、七两步实际上是青蛙借助第一、七两步实际上是青蛙借助s-1个石柱以及个石柱以及y个荷叶个荷叶，完，完成从左岸到第一个石柱，再到右岸的跳跃的过程，而这两成

54、从左岸到第一个石柱，再到右岸的跳跃的过程，而这两步的对象是同一批青蛙，步的对象是同一批青蛙，青蛙个数是青蛙个数是Jump(s-1,y)。 第二步到第六步完成的是左岸的青蛙借助剩余的第二步到第六步完成的是左岸的青蛙借助剩余的n-1个石柱个石柱以及所有以及所有y个荷叶跳跃到右岸的过程，青蛙个数是个荷叶跳跃到右岸的过程，青蛙个数是Jump(s-1,y)。结论：结论：Jump(s, y)是是Jump(s-1,y)+ Jump(s-1,y)。 即：即：Jump(s,y)=2*Jump(s-1,y)；注意：注意：当石柱数目为当石柱数目为0是不需要递归的，此时跳跃的青蛙数目是不需要递归的，此时跳跃的青蛙数目

55、为为荷叶数目荷叶数目+1。即递归的结束条件为：即递归的结束条件为：Jump(0,y)=y+1;LRYS2876543S1214321例如：荷叶数是例如：荷叶数是1、石柱数是、石柱数是2的的Jump(2,1)=2* Jump(1,1)= 8 int Jump(int s,int y) /青蛙过河青蛙过河递归函数递归函数 int k;if (s=0) / s=0表示无石柱表示无石柱 , 则为直接可解结点则为直接可解结点 k=y+1;else / 如果如果 r 不为不为0 , 则要则要 Jump(r-1,z) k=2*Jump(s-1,y);return(k); #include void main

56、( ) int s,y,sum; / s 为河中石柱数为河中石柱数 , y为荷叶数为荷叶数printf(请输入石柱数请输入石柱数s= ); scanf(%d,&s);printf(请输入荷叶数请输入荷叶数y= );scanf(%d,&y);sum=Jump(s,y); printf(Jump(%d,%d)=%dn,s,y,sum); 汉诺塔游戏与青蛙跳河的不同汉诺塔游戏与青蛙跳河的不同1）初始位置、结束位置不同；初始位置、结束位置不同；2）在汉诺塔游戏中，所搬盘子总数在汉诺塔游戏中，所搬盘子总数n的值决定第的值决定第一个盘子是搬到一个盘子是搬到B、还是搬到、还是搬到C；3）在青蛙跳河中，青蛙总

57、数在青蛙跳河中，青蛙总数n的值不决定第一个的值不决定第一个青蛙搬到那个石柱上。青蛙搬到那个石柱上。 选择排序、冒泡排序的排序思路比较简单，但是排序效率较选择排序、冒泡排序的排序思路比较简单，但是排序效率较低，不能满足需求（比如在低，不能满足需求（比如在OJ或比赛题目中）。或比赛题目中）。效率更高的排序方法呢？效率更高的排序方法呢？ 快速排序快速排序是利用是利用分治递归分治递归技术实现的一种高效的方法。技术实现的一种高效的方法。 分治法分治法简而言之就是简而言之就是“分而治之分而治之”，即把一个复杂的问题分，即把一个复杂的问题分成两个或更多的子问题，再把子问题分成更小的子问题成两个或更多的子问题

58、，再把子问题分成更小的子问题直到最后分解成的子问题可以直接求解，原问题的直到最后分解成的子问题可以直接求解，原问题的解即子问解即子问题的解的合并。题的解的合并。递归设计实例递归设计实例3-快速排序快速排序 将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 对子问题分别求解。如果子问题的规模仍然不够小，则对子问题分别求解。如果子问题的规模仍然不够小，则再划分子问题，如此递归的进行下去，直到问题规模再划分子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n

59、/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 将求出的小规模的问题的解合并为一个更将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原大规模的问题的解，自底向上逐步求出原来问题的解。来问题的解。快速排序的思想快速排序的思想快速排序是基于分治递归的思想来实现的：快速排序是基于分治递归的思想来实现的：1）设要排序的数组是设要排序的数组是a0an-1；2）任意选取一个数据（通常选用第一个数据）作为关任意选取一个数据（通常选用第一个数据

60、）作为关键数据；键数据；3）将所有比关键数据小的数都放到它前面（左），所将所有比关键数据小的数都放到它前面（左），所有比关键数据大的数都放到它后面（右）有比关键数据大的数都放到它后面（右）-这个过程称为一趟快速排序。这个过程称为一趟快速排序。4）对关键数据前、后的数据再分别进行一趟快速排序，对关键数据前、后的数据再分别进行一趟快速排序，直到直到参加排序参加排序的数字是一个为止。的数字是一个为止。一趟快速排序的算法步骤如下：一趟快速排序的算法步骤如下： 1）设置两个变量设置两个变量i、j，排序初：，排序初：i=0，j=n-1； 2）以以 a0 作为关键数据，即作为关键数据，即 key=a0； 3