递归算法实现青蛙过河问题
-
递归算法实现青蛙过河问题
一、
问题描述
一条小溪尺寸不大，青蛙可
以从左岸跳到右岸，在左岸有一石柱
L
，面积只
容得下一只青蛙落脚，同样右岸也有一石柱
R
，面积也
只容得下一只青蛙落脚。
有一队青蛙从尺寸上一个比一个小。
我
们将青蛙从小到大，
用
1
，
2
，
…，
n
编号。
规定初始时这队青蛙只能趴在左岸的石头
L<
/p>
上，
当然是一个落一个，
小的落在大
的上面。
不允许大的在小的上面。
在小溪中
有
S
个石柱，有
y
片荷叶，
规定溪中
的柱子上允许一只青蛙落脚，
如有多只同样要求一个落一个，
大的在下，
小的在
上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱
R
，与
左岸的石柱
L
一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。
当青蛙
从左岸的
L
上跳走后就不允许再跳回来；同样，从左岸
L
上跳至右岸
R
，
或从溪中荷叶或溪中石柱跳至右岸
R
上的
青蛙也不允许再离开。问在已知溪中
有
S
根石柱和
y
片荷叶的情况下，最多能跳过多少只青蛙？
二、
程序设计思想
定义函数
Jump ( S ,y
)
——
最多可跳过河的青蛙数
其中：
S
——
河中柱子数
y
——
荷叶数
1
、当河中无柱子时：即
S =0
，
Jump(0,y)
当
< br>y = 1
时，
3
1
1#
L<
/p>
2#
R
左岸
右岸
2
Jump(0,1)=2
说明：河中有一片荷叶，可以过两只青蛙，
起始时
L
上有两只青蛙，
1#
在
2#
上面。第一步：
1#
跳到荷叶上；第二步：
2#
从
L
直接跳至
R
上
；第三步：
1#
再从荷叶跳至
R
上。
2
、当
y=2
时，
Jump(0,2)=3
；
说明：河中有两片荷叶时，可以过
3
只青蛙。起始时：
1#<
/p>
，
2#
，
3#
3
只青蛙落在
L
上，
< br>
第一步：
1#
从
L
跳至叶
1
上，
第二步：
2#
从
L
跳至叶
2
上，
第三步：
3#
从
L
直接跳至
R
上，
第四步：
2#
从叶
2
跳至
R
上，
第五步：
1#
从叶
< br>1
跳至
R
上，
< br>
5
1
叶
1
R
L
3
2
4
叶
2
采用归纳法：
Jump(0,y)=
y+1
；
意思是：
< br>在河中没有石柱的情况下，
过河的青蛙数仅取决于荷叶数，
数目是荷叶
数
+1
。
3
、若
Jump(S,
y)
，先看一个最简单情况：
S=1
，
y=1
。
从图上看出需要
9
步，跳过
4
只青蛙。
1#
青蛙从
L
－
> Y
；
4
3#
3#
2
#
青蛙从
L
－
> S
；
6
1#
青蛙从
Y
－
> S
；
1
Y
3#
青蛙从
L
－
> Y
；
R
9
1#
L<
/p>
1#
4#
青蛙从
L
－
> R
；
3
7
1#
1#
3#
青蛙从
Y
－
> R
；
2
2#
S
2#
8
1#
青蛙从
S
－
> Y
；
2#
青蛙从
S
－
> R
；
5
4#
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
只从
< br>L
－
>
S
；
步骤
2
：后
y+1
只从
L
－
>
R
；
步骤
3
：前
y+1
只从
S
－
>
R
；
5
、
对于
S
=
2
，
y
>
1
的情形若只有石柱
S1
，最多可过
2*(y+1)
只青蛙。有了石