递归算法实现青蛙过河问题

《递归算法实现青蛙过河问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、递归算法实现青蛙过河问题一、问题描述一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，当然是一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样允许多

2、个青蛙落脚，但须一个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？二、程序设计思想定义函数Jump(S,y)——最多可跳过河的青蛙数其中：S——河中柱子数y——荷叶数1、当河中无柱子时：即S=0，Jump(0,y)当y=1时，Jump(0,1)=2说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。第一步：1#跳到荷叶上；第二步：2#从L直接跳至R上

3、；第三步：1#再从荷叶跳至R上。2、当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；意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。3、若Jump(S,y)，先看一个最简单情况：S=1，y=1。从图上看出需要9步，跳过4只青蛙。1#青蛙从L－>Y；2#青蛙从L－>S

4、；1#青蛙从Y－>S；3#青蛙从L－>Y；4#青蛙从L－>R；3#青蛙从Y－>R；1#青蛙从S－>Y；2#青蛙从S－>R；1#青蛙从Y－>R；3、对于S=1，y=1的情形，从另外一个角度来分析若没有石柱S，最多可过y+1=2只青蛙。有了石柱S后，最多可过2*2=4只青蛙。步骤1：1#和2#从L－>S；步骤2：3#和4#从L－>R；步骤3：1#和2#从S－>R；4、对于S=1，y>1的情形若没有石柱S，最多可过y+1只青蛙。有了石柱S后，最多可过2*(y+1)只青蛙。步骤1：前y+1只从L－>S；步骤2：后y+1只从L－>R；步骤3：前y+1只

5、从S－>R；5、对于S=2，y>1的情形若只有石柱S1，最多可过2*(y+1)只青蛙。有了石柱S2后，最多可过4*(y+1)只青蛙。步骤1：前2*(y+1)只从L－>S2；步骤2：后2*(y+1)只从L－>R；步骤3：前2*(y+1)只从S2－>R；6、根据上述分析采用归纳法，可得出如下的递归形式：Jump(S,y)=2*Jump(S-1,y)；意思是：先让一半的青蛙利用y片荷叶和S-1根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用y片荷叶和S-1根石柱，落在右岸的R上面；最后再让先前的一半青蛙，利用y片荷叶和S-1根石柱，落在右岸

6、的R上面。递归边界：Jump(0,y)=y+1将上述分析出来的规律写成递归形式的与或结点图为：举例：S=3，y=4，算Jump(3,4)三、程序代码#includeintJump(ints,inty){inta;if(s==0){a=y+1;}else{a=2*Jump(s-1,y);}returna;}voidmain(){ints,y,a;printf("请输入石柱数s=");scanf("%d",&s);printf("请输入荷叶数y=");scanf("%d",&y);a=Jump(s,y);printf(“Jump

7、(%d,%d)=%d",s,y,a);}一、算法分析：时间复杂度为T（n）=O(s),s为石柱的个数。