计算机语言与程序设计递归算法举例

1、青蛙过河快速排序分书问题第七讲 递归算法举例12递 归 算 法 举 例青蛙过河3讨论问题青蛙过河该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，当然是一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙

2、落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？4这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。思路：1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。2. 定义函数 Jump(S,y) 最多可跳过河的青蛙数 其中：S 河中柱子数 y 荷叶数53. 先看简单情况，河中无柱子：

3、S=0，Jump(0,y) 当y=1时，Jump(0,1)=2； 说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。 第一步：1# 跳到荷叶上； 第二步：2# 从L直接跳至R上； 第三步：1# 再从荷叶跳至R上。 如下图：6当y=2时， Jump(0,2)=3； 说明：河中有两片荷叶时，可以过3只青蛙。起始时： 1#，2#，3# 3只青蛙落在L上， 第一步：1# 从L跳至叶 1上， 第二步：2# 从L跳至叶 2上， 第三步：3# 从L直接跳至R上， 第四步：2# 从叶2跳至R上， 第五步：1# 从叶1跳至R上，采用归纳法：Jump(0,y)=y+1； 意思是：在河中没

4、有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。7再看Jump(S, y)先看一个最简单情况： S=1，y=1。从图上看出需要9步，跳过4只青蛙。1# 青蛙从 L Y；2# 青蛙从 L S；1# 青蛙从 Y S；3# 青蛙从 L Y；4# 青蛙从 L R；3# 青蛙从 Y R；1# 青蛙从 S Y；2# 青蛙从 S R；1# 青蛙从 Y R；8tLSYRL4L3L2L1S2S1R4R3R2R101234567894444433332212222211111311444443333221表一9 为了将过河过程描述得更清楚，我们给出了表1。表中L1 L2 L3 L4表示左岸石柱上落在

5、一起的青蛙的高度位置。L1 在最上面，L4 在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理R1 R2 R3 R4也是如此。对水中石柱S，也分成两个高度位置S1 S2。对荷叶Y无须分层，因为它只允许一只青蛙落在其上。t=0为初始时刻，青蛙从小到大落在石柱L上。t=1为第一步：1#从L跳至荷叶Y上；L上只剩2# 3# 4#。T=2 为第二步；2#从L跳至石柱S上，处在S2位置上，L上只剩3#和4#。T=3为第三步，1#从Y跳至S，将Y清空。这时你看，S上有1#、2#，L上有3#、4#，好象是原来在L上的4只青蛙，分成了上下两部分，上面的2只通过荷叶y转移到了S上。这一过程

6、是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了S上。这是我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。10对于LYR系统，相当于Jump(0,1)对于SYR系统，相当于Jump(0,1) 两个系统之和为2*Jump(0,1)，因此有：Jump(1,1)=2*Jump(0,1)=2*2=4。现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作S1和S2，荷叶叫y，考虑先将L上的青蛙的一半借助于S2和y转移到S1上，当然

7、是一半小号的青蛙在S1上，大的留在L上。11这样 L S1 S2 y R 系统分解为 ： （L S2 y R 系统） + （S1 S2 y R 系统）= 2 * （L S2 y R 系统）= 2 * Jump(1,1)用归纳法Jump(S, y)=2*Jump(S-1, y)125. 将上述分析出来的规律写成递归形式的与或结点图为：13举例：S=3，y=4，算 Jump(3,4)14#include /预编译命令int Jump(int, int);/声明有被调用函数void main()/主函数/主程序开始int s,y,sum;/整型变量,s为河中石柱数,y为荷叶数printf(请输入石柱

8、数s= );/提示信息scanf(%d,&s);/输入正整数sprintf(请输入荷叶数y= );/提示信息scanf(%d,&y);/输入正整数ysum=Jump(s,y);/Jump(s,y)为被调用函数printf(“Jump(%d,%d)=%dn,s,y,sum); /输出结果/主程序结束/以下函数是被主程序调用的函数int Jump(int r,int z)/整型自定义函数,r,z为形参/自定义函数体开始int k;/整型变量if (r=0)/如果r为0,则为直接可解结点,k=z+1;/直接可解结点,k值为z+1else/如果不为1,则要调用Jump(r-1,z) k=2*Jump(

9、r-1,z);/计算Jump(r-1,z)再乘以2赋给kreturn(k);/将k的值返回给Jump(s,y)/自定义函数体结束15递 归 算 法 举 例快速排序16快速排序的思路：1、将待排序的数据放入数组a中，下标从l到r；2、取al放变量k中，通过由右、左两边对k的大小的比较，为k选择应该排定的位置。这时要将比k大的数放右边，比k小的数放左边。当k到达最终位置后，由k划分了左右两个集合。然后再用同样的思路处理左集合与右集合。3、令sort(l,r)为将数组元素从下标为l到下标为r的r-l+1个元素从小到大排序。17我们画出与或图来阐述快速排序的思路：18分区处理：1、让k=al2、将k放

10、在am3、使al,al+1,am-1=am4、使am=r，则什么也不做。这是直接可解结点。C结点是在lr情况下A结点的解。C是一个与结点。要对C求解需分解为三步。依次为：191、先解D结点，D结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是（1）将al中的元素放到它应该在的位置上，比如m位置。这时amal；（2）让下标从l到m-1的数组元素小于等于am；（3）让下标从m+1到r的数组元素大于am；比如a数组中al=5，经分组处理后，5送至a4。5到位后，其左边a0a3的值都小于5；其右边a5a6大于5。（见下图）205261734a0123456lr4231576a01

11、23456m下标：下标：lm-1rm+1212、再解E结点，这时要处理的是a0a3；3、再解F结点，处理a5a6。下面按照这种思路构思一个快速排序的程序框图。void sort(int array , int ll, int rr)int l,r,i,k;2223下面举例说明排序过程图1 a数组中有7个元素待排序1 让k=al=a0=552617340123456lr图 15k242 进入直到型循环执行（1）ar=a6=4 不满足当循环条件，r不动。执行（2）lr，做两件事：al=ar，即a0=a6=4，l=l+1=0+1=1，见图242617340123456lr图 25k25执行（3）图2

12、中的a1k满足当循环的条件，r=r-1=6-1=5见图5，之后退出当循环，因为ar=3k42617360123456lr图 55k28执行（2）al=ar，并让l=l+1=3，见图6 42317360123456lr图 65k29执行（3）由于a3=1k，退出循环。见图7 42317360123456lr图 75k30执行（4）ar=al，a5=7。见图8 这时仍然lk，让r=r-1=4。见图942317760123456lr图 95k32之后，l=r，退出直到型循环，做al=k，l=4，a4=5，这是5的最终位置，5将整个数据分成左右两个集合，见图10。42315760123456lr图 1

13、0左右5k33用上述思路去排左边的部分从l=0到r=3，见图11。让k=al=a0=4，然后进到直到型循环，执行（1）ar=1k，不满足当循环的条件，r不动。执行（2）al=ar，l=l+1=1,见图1212310123lr图 1242310123lr图 114k34执行（3）alk，l=l+1=2，a2k，l=l+1=3，这时l=r，不会执行（4），同时退出直到型循环，见图13。然后做al=k，即a3=4，见图14，左边也排好了。12340123图 1412310123lr图 13lr4k4k354、用上述思路去排右边的部分，见图15，让k=al=a5=7，进入直到型循环；执行（1）ar=6

14、k，r不动执行（2）al=ar=6，l=l+1=5+1=6，见图16图 167656lr图 156656lr7k36这时l=r，不再执行（3）（4），退出直到型循环后，做al=k，见图17。图 176756lr7k37在有了递归调用函数之后，主程序很容易写，主程序中应包含1、 定义整型变量：数组a10，i；2、 用循环结构输入待排序的数，将其放入a数组；3、 调用sort函数，使用三个实际参数a将数组a当实参；0数组下标下界；9数组下标上界；4、 输出排序结果下面给出参考程序（分两页）38#include /预编译命令void sort(int array ,int ll,int rr) /被

15、调用函数，数组array，ll,rr为形参 /函数体开始 int l,r,i,k; /定义变量 if(llrr) /如果llrr,则做下列7件事: /7件事开始l=ll;r=rr;k=arrayl; /第1件事do /第2件事(开始) while(l=k)r=r-1; /2.1,右边的元素=k,让r往中间移if(lr) /2.2,右边的元素k,让 arrayl=arrayr; /arrayr送给arrayl， l=l+1; /同时让l往中间移 while(lr)&(arrayl=k)l=l+1; /2.3,左边的元素=k,让l往中间移 if (lk,让arrayl /送给arrayr /whi

16、le(l!=r); /第2件事(结束)arrayl=k; /第3件事,k已排到位for(i=ll;i=rr;i=i+1) /第4件事，输出 printf(a%d=%d;,i,arrayi); /printf(n); /第5件事，换行sort(array,ll,l-1); /第6件事，排左边部分sort(array,l+1,rr); /第7件事，排右边部分 /7件事结束 /函数体结束39void main() /主函数开始 int a10,i; /整型变量printf(请输入10个整数n );/提示信息for (i=0;i10;i=i+1)/输入10个整数scanf(%d,&ai);/sort(

17、a,0,9);/调用sort函数,实参为数组a和0，9printf(排序结果为:); /提示信息for (i=0;i10;i=i+1)/printf(%d;,ai);/输出排序结果printf(n);/ /主函数结束 40递 归 算 法 举 例分书问题41教学目标：巩固用递归思想编写程序教学内容：分书问题题 目：有编号分别为1，2，3，4，5的五本书，准备分给A,B,C,D,E五个人，每个人阅读兴趣用一个二维数组加以描述：42希望你写一个程序，输出所有分书方案，让人人皆大欢喜。假定5个人对5本书的阅读兴趣如下表： 0 1 2 3 4ABCDE0011011001011010001001001人

18、书431、定义一个整型的二维数组，将表中的阅读喜好用初始化方法赋给这个二维数组。可定义int like55=0,0,1,1,0,1,1,0,0,1, 0,1,1,0,1,0,0,0,1,00,1,0,0,1;2、定义一个整型一维数组book5用来记录书是否已被选用。用下标作为五本书的标号，被选过元素值为1，未被选过元素值为0，初始化皆置0。Int book5=0,0,0,0,0;解题思路：443、画出思路图定义 try(i)试着给第i人分书(i=0,1,4)4546说明：（1）试着给第i个人分书，先试分0号书，再分1号书，分2号书，因此有一个与结点，让j=0,1,2,3,4。j表示书。（2）L

19、P为循环结构的循环体。（3）条件C是由两部分“与”起来的。“第i个人喜欢j书，且j书尚未被分走”。满足这个条件是i人能够得到j书的条件。（4）如果不满足C条件，则什么也不做，这是直接可解结点。47（5）满足C条件，做三件事。sh1第一件事：将j书分给i，用一个数组takei=j，记住书j给了i人，同时记录j书已被选用，booki=1。sh2第二件事：查看i是否为4，如果不为4，表示尚未将所有5个人所要的书分完，这时应递归再试下一人，即try(i+1)。如果i=4，则应先使方案数n=n+1，然后输出第n个方案下的每个人所得之书。Sh3第三件事：回溯。让第i人退回j书，恢复j书尚未被选的标志，即takei=-1和bookj=0。这是在已输出第n个方案之后，去寻找下一个分书方案所必需的。（6）在有了上述的与或图之后，我们很容易写出一