资源描述：
《清华大学C语言教学课件(共16个PPT)第7个教学内容.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、清华大学C语言教学课件(共16个PPT)第7个递归算法举例——青蛙过河2讨论问题——青蛙过河该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下：一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，当然是一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚
2、，如有多只同样要求一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？3这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。思路：1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因
3、素来分析，化难为易。2.定义函数Jump(S,y)——最多可跳过河的青蛙数其中：S——河中柱子数y——荷叶数43.先看简单情况，河中无柱子：S=0，Jump(0,y)当y=1时，Jump(0,1)=2；说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。第一步：1#跳到荷叶上；第二步：2#从L直接跳至R上；第三步：1#再从荷叶跳至R上。如下图：5当y=2时，Jump(0,2)=3；说明：河中有两片荷叶时，可以过3只青蛙。起始时：1#，2#，3#3只青蛙落在L上，第一步：1#从L跳至叶1上，第二步：2
4、#从L跳至叶2上，第三步：3#从L直接跳至R上，第四步：2#从叶2跳至R上，第五步：1#从叶1跳至R上，采用归纳法：Jump(0,y)=y+1；意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。6再看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；7tLSYRL4L3L2L1S2
5、S1R4R3R2R10 1 2 3 4 5 6 7 8 94 4 4 4 43 3 3 32 212 2 2 2 21 1 11 1 3 1 14 4 4 4 43 3 3 32 21表一8为了将过河过程描述得更清楚，我们给出了表1。表中L1L2L3L4表示左岸石柱上落在一起的青蛙的高度位置。L1在最上面，L4在最下面的位置。引入这个信息就可比较容易地看出对青蛙占位的约束条件。同理R1R2R3R4也是如此。对水中石柱S，也分成两个高度位置S1S2。对荷叶Y无须分层，因为它只允许一只青蛙落在其上。t=0为初始时刻，
6、青蛙从小到大落在石柱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上。这一过程是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了S上。这是我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者二只青蛙号大；后者二只
7、青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。9对于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=1Jump(2,1)我们将河中的两个石柱称作S1和S2，荷叶叫y，考虑先将L上的青蛙的一半借助于S2和y转移到S1上，当然是一半小号的青蛙在S1上，大的留在L上。10这样LS1S2yR系统分解为：（LS2yR系统）+（S1S2yR系统）=2*（LS2
8、yR系统）=2*Jump(1,1)用归纳法Jump(S,y)=2*Jump(S-1,y)115.将上述分析出来的规律写成递归形式的与或结点图为：12举例：S=3，y=4，算Jump(3,4)13#include//预编译命令intJump(int,int);//声明有被调用函数void
