最近微信里很多人在玩青蛙过河这个小游戏，其实会完Hanoi塔（汉诺塔）的人应该很快也能掌握这个游戏，因为解决的办法都是递归。（注：图片来源于网络）

下面从网上找来的解答图，只给出一到六步，以后的步骤相当明显，而且这样方便递归。

因此下面的只考虑如何将青蛙排成一只左青蛙一只右青蛙。

仔细观察可以发现，下面是一边两只青蛙的解法。

下面是一边一只青蛙的解法。

现在可以开始递归了，用A表示左青蛙，B表示右青蛙，#表示石头。

假设我们已经将一边n只青蛙的前面n-1只排成了AB......AB#或者#AB......AB的情形。

这时候青蛙们的排布情况为AAB......AB#B或者A#AB......ABB，可以看出两种情况实际上是等价的。

因此只考虑A#AB......ABB的情况。

右青蛙（B）从左至右依次跳跃即可变成ABAB...AB#。

可以顺便归纳一下完成个需要的步数，一边一只青蛙的时候需要一步，

从n到n-1要n步。因此一边n只青蛙走成AB......AB需要1+2+......+n=n*(n+1)/2。

把后面比较明显的步骤也考虑一下。

AB......AB#要变成B...B#A...A，

首先左青蛙（A）从右到左依次跳跃变成#BA......BA。

n=1时即#BA，此时右青蛙（B）向左跳一步即可。

n=2时即#BABA，此时右青蛙（B）从左到右依次跳跃变成BBA#A，

然后左青蛙（A）向右跳一步即可，共3步。

其他情况重复下面两步，

右青蛙（B）从左到右依次跳跃变成BBA......BA#A，

左青蛙（A）从右到左依次跳跃变成BB#BA...BAAA，

如此类推，最后变成n=2或n=1的情形。

当n=2k为偶数时要k*(k+1)+1=k^2+k+1=(n+1)^2/4+3/4，

当n=2k-1为奇数时要k*(k+1)-k=k^2=(n+1)^2/4。

因此解决一边n只青蛙过河的问题

当n为偶数的时候需要n*(n+1)/2+n+(n+1)^2/4+3/4=(2*n^2+4*n+4)/4步，

当n为奇数的时候需要n*(n+1)/2+n+(n+1)^2/4=(3*n+1)*(n+1)/4=(3*n^2+4*n+1)/4。

至此这个问题完满解决了。

有点6