1、1第五讲 递推与递归主要内容递推及其应用递归及其应用 2整 体 概 述THE FIRST PART OF THE OVERALL OVERVIEW,P L E A S E S U M M A R I Z E T H E C O N T E N T第一部分3第五讲 递推与递归递推是通过数学推导，将复杂的运算化解为若干重复的简单运算，以充分发挥计算机擅长重复处理的特点。递归是将复杂的操作分解为简单操作的多次重复，一般用函数调用完成。411.1 递 推511.1 递 推611.1 递 推例如：Fibonacci数列问题 已知：F(1)=0 ，F(2)=1，若：n2，则F(n)=F(n-1)+F(n-
2、2)注意：1）每个数据项都和它前面的若干个数据项（或后面的若干个数据项）有一定的关联-递推关系式。2）从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而得到最终结果。711.1 递 推注意：3）递推必须有“边界”。4）解决递推类型问题有三个重点：如何建立正确的递推关系式；递推关系有何性质；递推关系式如何求解。基础，重点811.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=
3、0，n!=1n!=19例1：猴子第1天摘下若干个桃子，当即吃了一半又一个。第2天又把剩下的桃吃了一半又一个，以后每天都吃前一天剩下的桃子的一半又一个，到第10天猴子想吃时，只剩下一个桃子。问：猴子第1天一共摘了多少桃子?分析：已知条件：第 10 天剩下 1 个桃子；隐含条件：每一次前一天的桃子个数等于后一天桃子的个数加 1 的 2 倍。逆向思维：从后往前推，可用倒推法求解。10#include void main()int i,a=1;for(i=9;i=1;i-)a=(a+1)*2;printf(a=%dn,a);例1：逆推法-求解猴子吃桃子11例2：猴子分食桃子1)五只猴子采得一堆桃子，猴
4、子彼此约定隔天早起后再分食。2)半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。3)第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。问：五只猴子采得一堆桃子数最少应该有几个呢？逆推法12算法分析：先要找第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：第N只猴 第N只猴前桃子数目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1通过
5、递推，求出s1即可例2：猴子分食桃子-逆推法注意：其中的s1、s2、s3、s4、s5必须是整数13/例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+;else break;s=s*5/4+1;x=x+5;printf(s=%dn,s);1411.1.2 递推设计实例例11.1：母牛的故事 问题描述：有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。编程实现：在第n年的时候，共有多少头母牛
6、？15例11.1：母牛的故事-顺推法 设数组f(i)表示第 i 年的母牛总数，则第 n 年的母牛总数为f(n)。f(n)与两个值有关 在本年之前就已经出生的母牛数目 在本年新出生的小母牛数目。1）本年之前就已经出生的母牛数目，实际上就是前一年的母牛总数-f（n-1）。2）由于每一头母牛每年只生育一头小母牛，所以在本年新出生的小母牛数目，实际上是到今年可以生育的母牛的数目。3)而每头小母牛从第四个年头才开始生育，所以今年可以生育的母牛的数实际上就是三年前的母牛总数，即为f（n-3）。16例11.1：母牛的故事-顺推法递推公式：f(n)=f(n-1)+f(n-3)（n=4）f(1)=1；f(2)=
7、2;f(3)=3；递推边界17 若数组f(i)表示第 i 年的母牛总数，则第 n 年的母牛总数为f(n)。18例11.1：母牛的故事-顺推法#include void main()_int64 f50;/_int64 -定义大整数 int 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大整数输入/输出格式 19例11.2 骨牌问题-顺推法20例11.2 骨牌问题-顺推法21例11.2 骨牌问题-顺推法 22 例11.2 骨牌问题-顺推法23因此，n块骨牌的铺法是首块骨牌横铺
8、方式的铺法与竖铺方式的铺法之和。即：f(n)=f(n-1)+f(n-2)边界：f(1)=1 ，f(2)=2例11.2 骨牌问题-顺推法递推公式24#includeint 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 骨牌问题25#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(%I64dn,fn
9、-1);例11.2 骨牌问题-顺推法26问题描述：设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级。问：求从底层开始走完全部楼梯的有多少种走法。例如，当n=3时，走法如下：1+1+1 1+2 2+1 3思考：上楼问题n=3，共有4种走法27n的值 走法f(n)1 1 2 2 3 4 4 7从递推的思想出发，可以设想，从第4 4项开始，每1 1项等于前面3 3项的和。上楼问题-算法分析 f(n)=f(n-1)+f(n-2)+f(n-3)-递推公式 f(1)=1,f(2)=2,f(3)=4-递推边界28#include /上楼问题 void main()int x,n,i,a,b,
10、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);29例11.3 错排信件问题描述：某人写了n封信和n个信封，所有的信都装错了信封。要求：若所有的信都装错信封，共有多少种不同情况？30例11.3 错排信件找规律：对n封信以及n个信封各自按照从 1.n 进行编号；f(n)-n个编号的信放在n个编号的信封，各不对应的方法数；f(n-1)-n-1个编号的信放在n-1个编号位置的信封，各不对应的方法数。31例11.3
11、错排信件找规律：第一步:把第n封信放在第k个信封（kn），不对应的共有n-1种方法；第二步:放编号为 k 的信，有两种情况：1）放编号为 k 的信放到第n个信封，则对于剩下的n-2封信，需要放到剩余的n-2个信封且各不对应，就有f(n-2)种方法；2）放编号为 k 的信不放到位置n，对于这n-1封信，放到剩余的n-1个信封且各不对应，有f(n-1)种方法；结论：f(n)=(n-1)*(f(n-2)+f(n-1)特例：f（1）=0，f（2）=1 -边界32例11.3 错排信件#includevoid main()int i,n,f20;f1=0;f2=1;scanf(%d,&n);for(i=3
12、;i=n;i+)fi=(i-1)*(fi-2+fi-1);printf(%dn,fi);33例11.4 马踏过河卒-选讲 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C点和P1，P2，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n,m)(n,m为不超过20的整数)，同样马的位置坐标是需要给出的，CA且CB。编程：输入n，m，计算出卒从A点能够到达B点的路径的条数。34例11.4 马踏过河卒-选讲 马踏过河卒是一道很老的
13、题目，一些程序设计比赛中也经常出现过这一问题的变形。一看到这种类型的题目容易让人想到用搜索来解决，但盲目的搜索仅当n,m=15就会超时。可以试着用递推来进行求解。根据卒行走的规则，过河卒要到达棋盘上的一个点，只能有两种可能：从左边过来（左点）或是从上面过来（上点），所以根据加法原理，过河卒到达某一点的路径数目，就等于其到达其相邻的上点和左点的路径数目之和，因此可用逐列（或逐行）递推的方法求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径数目设置为0即可。35例11.4 马踏过河卒-选讲 用二维数组元素fijfij表示到达点（i i，j j）的路径数目；用gijgi
14、j表示点（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 fij=fi-1j+fij-1 fij=fi-1j+fij-1 当 i i0,j0,j0,gij=00,gij=0 递推边界：f00=1 36#include /马踏过河卒 int main()int i,j,n,m,f202
15、0,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;gx+2y-1=1;gx-2y+1=1;gx+2y+1=1;gx-1y+2=1;gx+1y+2=1;37for(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
16、+)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;38例11.4 马踏过河卒改进为了更简洁地表示马的控制点，可以引入两个一维数组，分别用来统计从马的初始位置可以横向移动的位移与纵向移动的位移。程序的改进如下：#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,&
17、m,&x,&y);gxy=1;39例11.4 马踏过河卒for(i=1;i=0)&(x+dxi=0)&(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;40 递推应用：王小二切饼，要求每2条线都有交点。4
18、1 找规律：王小二切饼，要求每2条线都有交点。规律：p(n)=p(n-1)+n42#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;43递推思考输出杨晖三角形的前10行。杨晖三角形的前5行如左下图所示。问题分析：观察左上图不太容易找到规律，但如果将左上图转化为右上图就不难发现杨辉三角形其实就是一个二维表（数组）的下三角部分。44#include /打印杨辉三角形 void main()int i,j，a1010;for
19、(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);45递推小结1）递推是从已知条件开始；2）递推必须有明确的通用公式；3）递推必须是有限次运算。4611.2 递归递归的定义：在一个函数的定义中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。4711.2 递归递归思想：把
20、规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。递归优点：只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。用递归算法编写的程序结构清晰，具有很好的可读性。递归缺点：通过直接的递归过程和函数实现起来，有时效率很差（用递归函数去求1000!）。48递归算法适用在三个场合1)数据的定义形式是递归的，如求n!；2)数据之间的逻辑关系（即数据结构）是递归的，如树、图等的定义和操作；3)某些问题虽然没有明显的递归关系或结构，但问题的解法是不断重复执行一种操作，只是问题规模
21、由大化小，直至某个原操作（基本操作）就结束。例如：汉诺塔问题。49递归设计的要件在函数中必须有直接或间接调用自身的语句；(2)在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口（或递归边界）。50编写递归算法程序时，首先要对问题的以下三个方面进行分析：u决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？u问题的边界条件及边界值。在什么情况下可以直接得出问题的解？-问题的边界条件及边界值。u解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？-解决递归问题的难点，把
22、这些步骤或等式确定下来。51递归设计实例1-哈诺（HanoiHanoi）塔问题：1)1)相传在古代印度的 Bramah Bramah 庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把6464个一个比一个小的金盘从一根柱子上移到另一根柱子上去。2)2)移动规则：每次只允许移动一只盘，大盘不得落在小盘上面。3)3)如以每秒移动一只盘子，按照上述规则将6464只盘子从一个柱子移至另一个柱子上，所需时间约为58005800亿年。52先从最简单的情况开始分析，理出思路。1、在 A 柱上只有一只盘子，假定盘号为 1，这时只需将该盘从 A 搬至 C，一次完成，记为:move 1#from A to
23、 C ABC1532、在 A 柱上有 2 只盘子，1 为小盘，2 为大盘。第（1）步将1号盘从A移至B，这是为了让 2号盘能动；move 1#from A to B;第（2）步将 2 号盘从A 移至 C；move 2#from A to C;第（3）步再将 1 号盘从 B 移至 C；move 1#form B to C;ABC21543、在A柱上有3只盘子，从小到大分别为1号，2号，3号第（1）步：将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为 move(2,A,C,B)含义：将上面的2只盘子作为整体从A借助C移至B。第（2）步：将3号盘
24、从A移至C，一次到位。记为 move 3#from A to C第（3）步：处于B上的作为一个整体的2只盘子，再移至C。这一步记为 move(2,B,A,C)含义：将2只盘子作为整体从B借助A移至C。55move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213移动3 3个盘子的分解：56move(3,A,B,C)move(2,A,C,B)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,
25、B,C)ABC213574、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中 move(2,A,C,B)实际上是分解为以下三步第（1）.1步：move 1#form A to C;第（1）.2步：move 2#form A to B;第（1）.3步：move 1#form C to B;58经过以上步骤，将 1 号和 2 号盘作为整体从 A 移至 B，为 3 号盘从 A 移至 C 创造了条件。同样，3号盘一旦到了 C，就要考虑如何实现将 1 号和 2 号盘当整体从 B 移至 C 的过程了。实际上 move(2,B,A,C)也要分解为三步：第（3）
26、.1步：move 1#form B to A;第（3）.2步：move 2#form B to C;第（3）.3步：move 1#form A to C;595、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 是一个桥梁用。60move(n,A,B,C)分解为3步：(1)move(n-1,A,C,B)：将 n-1 只盘子作为一个整体从A经C移到B；(2)输出n：A to C：将n号盘从A移到C，是直接可解结
27、点；(3)move(n-1,B,A,C)：将n-1只盘子作为一个整体从B经A移到C。-递归61实现 move(n-1,A,C,B)要分为 3 步：第1步：将 n-2 只盘子作为一个整体从A经B到C -move(n-2,A,B,C)；第2步：第n-1号盘子从A直接移至B，即 n-1:A to B；第3步：将 n-2 只盘子作为一个整体从C经A移至B -move(n-2,C,A,B)；62/m表示盘子数目;a，b，c表示柱子标号void move(int m,char a,char b,char c)if(m=1)/如果1个盘子，则为直接可解结点 step+;/步数加1 printf(n%d mo
28、ve 1#from%c to%cn,step,a,c);else move(m-1,a,c,b);/递归调用move(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)63#include /用递归求解Hanoi问题int step=0;/整型全局变量，移动步数int main()int n;printf(请输入盘数 n=);scanf(%d,&n);printf(在3根柱子上移%d 只盘的步骤为:,n);move(n,A,B,C);re
29、turn 0;64该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：1）一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。2）有一队青蛙从小到大编号：1，2，n。3）初始时：青蛙只能趴在左岸的石头 L 上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。递归设计实例265该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：4）在小溪中有S个石柱，有y片荷叶，规定溪中的石柱如有多只青蛙也是大在下、小在上，而且必须编号相邻；5）对于荷叶只允许一只青蛙落脚，不允许多只落在其上；6）对
30、于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻；7）当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。问：在已知溪中有 s 根石柱和 y 片荷叶的情况下，最多能跳过多少只青蛙？66思路：先从柱子和荷业较少的情况开始分析，对多个因素作分解，找出规律。1、定义函数 Jump(s,y)最多可跳过河的青蛙数 其中：s 河中柱子数 y 荷叶数672、河中无柱子：S=0，即Jump(0,y)y=1时，河中有一片荷叶，起始时L上有两只青蛙，1#在2#上面。第一步：1#跳到荷叶上；第
31、二步：2#从L直接跳至R上；第三步：1#再从荷叶跳至R上。结论：Jump(0,1)=2；/河中有1片荷叶，能过2只青蛙。左岸L右岸R荷叶68当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、河中无柱子：S=0，即Jump(0,y)69小结：Jump(0,1)=2；-能跳过2只青蛙 Jump(0,2)=3；-能跳过3只青蛙思考：Jump(0
32、,3)=?Jump(0,4)=?Jump(0,y)=?归纳法：Jump(0,y)=y+1含义：没有石柱时，过河青蛙数=荷叶数+1703、河中有石柱Jump(S,y)=？一个最简单情况：S=1、y=1时：1#青蛙从 L Y；2#青蛙从 L S；1#青蛙从 Y S；3#青蛙从 L Y；4#青蛙从 L R；左岸L右岸R荷叶Y石柱S3#青蛙从 Y R；1#青蛙从 S Y；2#青蛙从 S R；1#青蛙从 Y R；结论：Jump(1,1)=4 2*Jump(0,1)=2*271参照汉诺塔问题将借助一个石柱(s=1)、一个荷叶(y=1)的青蛙跳跃问题分成五个步骤：第一步：借助荷叶将左岸上面的若干青蛙（此时是
33、1#与2#两只）跳到石柱上暂存；第二步：左岸下一只青蛙（此时是3#）跳到荷叶上；第三步：左岸再下一只青蛙（此时是4#）跳到右岸；第四步：荷叶暂存的青蛙（3#）跳到到右岸；第五步：石柱上暂存青蛙（1#、2#）借助荷叶完成到跳到右岸。72以上的石柱如果看成右岸(步骤1)或左岸（步骤2）的话，进一步的分析，还可以将上述五个步骤分成以下两个阶段：第一、五两步实际上完成的就是青蛙借助一个荷叶跳跃的过程，并且这两步的对象是同一批青蛙，青蛙个数是Jump(0,1)。第二、三、四步实际上完成的也是青蛙借助一个荷叶跳跃的过程，青蛙个数是Jump(0,1)。所以：Jump(1,1)的值是Jump(0,1)+Jum
34、p(0,1)即：Jump(1,1)=2*Jump(0,1)；73对于借助s个石柱、y个荷叶的青蛙跳跃过程也可以类似的归纳出来，这个实现步骤可以分成七个步骤：第一步：借助所有荷叶以及其余石柱将左岸上面的若干青蛙跳到第一个石柱上暂存；第二步：左岸余下的青蛙借助其它可用的石柱以及所有荷叶跳到其它石柱上；第三步：左岸再余下的青蛙跳到所有荷叶上；第四步：左岸再下一只青蛙完成到右岸的直接跳跃-最大1只 第五步：荷叶暂存的青蛙完成到右岸的跳跃；第六步：除了第一个外其余石柱上暂存青蛙完成到右岸的跳跃；第七步：第一个石柱上暂存的青蛙借助其余石柱以及所有荷叶完成到右岸的跳跃；74如果以上的石柱在跳跃过程中可以看成
35、右岸或左岸，这七个步骤也可以简化成两个阶段：第一、七两步实际上是青蛙借助s-1个石柱以及y个荷叶，完成从左岸到第一个石柱，再到右岸的跳跃的过程，而这两步的对象是同一批青蛙，青蛙个数是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是不需要递归的，此时跳跃的青蛙数目为荷叶数目+1。即递归的结束条件为：Jump(0,y)=y+1;75LRYS2876543S
36、1214321例如：荷叶数是1、石柱数是2的Jump(2,1)=2*Jump(1,1)=876 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);77#include void main()int s,y,sum;/s 为河中石柱数,y为荷叶数printf(请输入石柱数s=);scanf(%d,&s);printf(请输入荷叶数y=);scanf(%d,&y);sum=Jump(s,y);print
37、f(Jump(%d,%d)=%dn,s,y,sum);78汉诺塔游戏与青蛙跳河的不同1）初始位置、结束位置不同；2）在汉诺塔游戏中，所搬盘子总数n的值决定第一个盘子是搬到B、还是搬到C；3）在青蛙跳河中，青蛙总数n的值不决定第一个青蛙搬到那个石柱上。79 选择排序、冒泡排序的排序思路比较简单，但是排序效率较低，不能满足需求（比如在OJ或比赛题目中）。效率更高的排序方法呢？快速排序是利用分治递归技术实现的一种高效的方法。分治法简而言之就是“分而治之”，即把一个复杂的问题分成两个或更多的子问题，再把子问题分成更小的子问题直到最后分解成的子问题可以直接求解，原问题的解即子问题的解的合并。递归设计实例
38、3-快速排序80 将要求解的较大规模的问题分割成k个更小规模的子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对子问题分别求解。如果子问题的规模仍然不够小，则再划分子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。81nT(n)=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)n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。82快速排序的思想快速排序是基于
39、分治递归的思想来实现的：1）设要排序的数组是a0an-1；2）任意选取一个数据（通常选用第一个数据）作为关键数据；3）将所有比关键数据小的数都放到它前面（左），所有比关键数据大的数都放到它后面（右）-这个过程称为一趟快速排序。4）对关键数据前、后的数据再分别进行一趟快速排序，直到参加排序的数字是一个为止。83一趟快速排序的算法步骤如下：1）设置两个变量i、j，排序初：i=0，j=n-1；2）以 a0 作为关键数据，即 key=a0；3）从 j 开始向前搜索，即由后开始向前搜索（j=j-1），找到第一个小于key的值aj，将其值赋给ai；4）从i开始向后搜索，即由前开始向后搜索（i=i+1），找
40、到第一个大于key的ai，将其值赋给aj；5）重复第3）、4）步，直到 i=j，此时将key暂存的值赋给ai（或aj）；注意：一趟快速排序完成，其结果是以key作为轴心数据，把数组的原数据分为 2 部分。比 key 小的数据放在key的前面（左），比 key 大的数据放在 key 的后面（右）。845261734a0a1a2a3a4a5a6key5261734545253515=key，j往前移动（j-），继续比较下一个aj，直到遇到小于key的元素停止。将此时的小于key的aj赋值给前面的元素ai，即：ai=aj，同时i后移（i+），指向下一个元素。7825一趟快速排序的算法举例2（从小到大
41、）：8650458036156072922578ija0a1a2a3a4a5a6a7a8a9key=50过程2：从前面的元素（i所指）与key进行比较，如果ai=key，i往后移动（i+），继续比较下一个ai，直到遇到大于key的元素停止。将此时的大于key的ai赋值给前面的元素aj，即：aj=ai，同时j前移（j-），指向下一个元素。78254580一趟快速排序的算法举例2（从小到大）：8750458036156072922578ija0a1a2a3a4a5a6a7a8a9key=50 重复上述过程1与过程2两个步骤，直到下标 i 与下标 j 指向同一元素（即i=j）为止。当 i=j 时，i
42、(或j)所指的位置就是初始选作关键数据key应该存放的位置，把key放入该位置。.一趟快速排序的过程7825458092jjj726015ii3650一趟快速排序的算法举例2（从小到大）：88通过一趟快速排序过程，以50作为划分关键元素，把一个无序的序列做了重新的元素调整，变成：其中在50之前存放的元素都小于等于50，在50之后的存放元素都大于等于50。25，45，15，36,50,60，72，92，80，78一趟快速排序的算法举例 2（从小到大）：u 疑问：1）这个序列还不是一个完全有序的序列；2）我们的目标是所有元素的排序。8925，45，15，36,60，72，92，80，7850,这不
43、是一个有序的序列但，如果把50之前的4个元素的排好序，以及元素50之后的5个元素的排好序，就可得到所有10个元素的有序序列了。这两个序列如何排序？这两个区间的排序问题与原问题相比较是性质相同，但规模更小的问题，所以可以用分治递归的策略来完成。一趟快速排序的算法举例2（从小到大）：90递归不能无限进行下去，当划分的区间只包含一个元素时，该区间自身一定是一个有序的区间，不再做递归.-递归终止的条件。排序的递归函数要以待排序序列的边界作为参数，使每次递归调用时完成不同区间的排序。91 假设以参数 L 与参数 r 分别作为区间的左右边界，当L=r 时表示区间只有一个元素，不需要再递归。递归程序思路如下
44、：当左边界 L 右边界 r 时，作如下操作：1）执行一趟快速排序过程，以 i 为界形成两个子序列，i 前所有元素都小于ai，i 之后的所有元素都大于ai；2）对 i 之前的区间做递归调用，左边界不变，右边界为 i-1；3）对 i 之后的区间做递归调用，左边界为 i+1，右边界不变。92#include void qsort(int a,int L,int r)/从小到大快速排序 int key=aL,i=L,j=r;/以第一个数为一趟快速排序的枢轴元素if(L=r)return;/递归终止while(ij)while(ikey)j-;ai=aj;while(ij&aikey)i+;aj=ai;
45、ai=key;qsort(a,L,i-1);/左半区间递归调用qsort(a,i+1,r);/右半区间递归调用 93void main()int i,a10;printf(input 10 int:);for(i=0;i10;i+)scanf(%d,&ai);qsort(a,0,9);/调用快速排序函数for(i=0;i10;i+)printf(%d ,ai);printf(n);94快速排序的应用排序与查找是最常用的数据操作利用分治递归的方法可以有效提高排序的效率 -快速排序利用同样的方法，也可以提高查找的效率：-找第k小的数 -二分查找（折半查找）95例：找第k小的数输入n个数，找出其中第
46、k(0kn)小的数常用方法：先对数组做排序，再找第k个位置的元素；排好前k个元素的顺序，找到第k小的元素；-思路简单，但时间开销大怎么办？利用类似快速排序的思想-分治递归 96快速排序的启示一趟快速排序的结果，以30为轴心，分成两个序列，30之前的元素均不大于30，30之后的元素均不小于30.如果需要整个序列排序，只需对两个子序列分别做递归调用即可。现在的目标是找到其中第 k 小的元素，有何关系？30 12 62 25 80 38 50 42 70 16key=30lowhigh16low12low62highhighhighhighhighhigh704250388025low3097快速排
47、序的启示例如：k=4，即要找第4小的元素，有什么发现？low=4high=4如何来判定？low=khigh=k30 12 62 25 80 38 50 42 70 16key=3016 1262high704250388025low3098快速排序的启示如果k=2，怎么办？在low位置之前的序列进行查找 性质相同但规模更小的问题，可递归求解如何表示？如果函数原型为 find(a,L,r,k)则递归调用形式为：find(a,L,low-1,k)30 12 62 25 80 38 50 42 70 1616 1262high704250388025low3099快速排序的启示如果k=7，又怎么办？
48、在low位置之后的序列进行查找性质相同但规模更小的问题，可递归求解如果函数原型为 find(a,L,r,k)，k=2时的递归调用形式为：find(a,L,low-1,k)，K=7时，可写为 find(a,low+1,r,k)30 12 62 25 80 38 50 42 70 1616 1262high704250388025low30100#include int find(int a,int L,int r,int k)/查找第 k 小数 int x=aL,low=L,high=r;/以第一个数为枢轴元素while(lowhigh)while(lowx)high-;alow=ahigh;w
49、hile(lowhigh&alowk)find(a,L,low-1,k);/左半区间递归调用 else find(a,low+1,r,k);/右半区间递归调用 return ak;void main()int i,b,a11;printf(intput 10 int:);for(i=1;i11;i+)scanf(%d,&ai);b=find(a,1,10,3);printf(nb=%d n,b);101二分查找 二分查找：采用跳跃式方式查找，先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半，再在小区间
50、查找-二分查找或折半查找。二分查找是一种高效的查找方法，它可以明显减少比较次数，提高查找效率。二分查找的数据序列必须是有序的序列。102二分查找的步骤（升序为例）A、取得有序序列的中间位置的数据，与待查找的数据进行比较，如果两者相等表示找到，查找结束；B、如果两者不相等，则存在两种可能：（1）中间位置的元素大于待查找的数据元素，说明如果该元素存在，只可能在中间位置之前的半个区间，到前半区间做递归查找；（2）中间位置的元素小于待查找的数据元素，说明如果该元素存在，只可能在中间位置之后的半个区间，到后半区间做递归查找；重复以上A、B过程，直到找到满足条件的记录，使查找成功，或直到区间不存在为止，此
