数学  - 讨论区

标题:青蛙过河

2014年07月26日 星期六 19:14

最近微信里很多人在玩青蛙过河这个小游戏,其实会完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。

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

 

2015年05月18日 星期一 21:30

有点6

如下红色区域有误,请重新填写。

    你的回复:

    请 登录 后回复。还没有在Zeuux哲思注册吗?现在 注册 !

    Zeuux © 2020

    京ICP备05028076号