2022年递归算法实现青蛙过河问题 .pdf

《2022年递归算法实现青蛙过河问题 .pdf》由会员分享，可在线阅读，更多相关《2022年递归算法实现青蛙过河问题 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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上；第三步：1#再从荷叶跳至 R 上。2、

3、当 y=2 时， Jump(0,2)=3；说明：河中有两片荷叶时，可以过3 只青蛙。起始时： 1# ，2#，3# 3 只青蛙落在 L 上，第一步： 1# 从 L 跳至叶 1 上，2#1#213L左岸R右岸名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 第二步： 2# 从 L 跳至叶 2 上，第三步： 3# 从 L 直接跳至 R上，第四步： 2# 从叶 2 跳至 R上，第五步： 1# 从叶 1 跳至 R上，采用归纳法： Jump(

4、0,y)=y+1 ；意思是：在河中没有石柱的情况下， 过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。3、若 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；3、对于 S = 1 ，y = 1 的情形，从另外一个角度来分析若没有石柱S，最多可过y+1=2 只青蛙。有了石柱S 后，最多可过 2*2 = 4 只青蛙。步骤 1：1#和 2# 从 L S

5、；步骤 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只从 S R；5、对于 S = 2，y 1 的情形若只有石柱S1，最多可过 2*(y+1) 只青蛙。有了石叶 1315LR叶224SY546LR1237891#2#4#3#3#1#2#1#1#名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

6、名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 柱 S2 后，最多可过 4*(y+1) 只青蛙。步骤 1：前 2*(y+1) 只从 LS2 ；步骤 2：后 2*(y+1) 只从 LR ；步骤 3：前 2*(y+1) 只从 S2R ；6、根据上述分析采用归纳法，可得出如下的递归形式：Jump(S,y)=2*Jump(S-1,y)；意思是：先让一半的青蛙利用y 片荷叶和 S-1 根石柱，落在河中剩下的那根石柱上； 然后让另一半的青蛙利用y 片荷叶和 S-1 根石柱，落在右岸的 R 上面；最后再让先前的一半青蛙，利用y 片荷叶和 S-1根石柱，落

7、在右岸的R上面。递归边界： Jump(0,y)=y+1 将上述分析出来的规律写成递归形式的与或结点图为：举例： S=3 ，y=4，算 Jump(3,4) Jump(3,4)Jump(S,y)y+1S!=0S=0Jump(S-1,y)2*Jump(S-1,y)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 三、程序代码#include int Jump(int s,int y) int a; if(s=0)a=y+1; else

8、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - a=2*Jump(s-1,y); return a; void main() int s,y,a; printf(请输入石柱数 s= ); scanf(%d,&s); printf(请输入荷叶数 y= ); scanf(%d,&y); a=Jump(s,y); printf(“Jump(%d,%d)=%d n,s,y,a); 三、算法分析：时间复杂度为 T（n）=O(s),s 为石柱的个数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -