注册 |登录

随便说说分享 http://blog.sciencenet.cn/u/zhangjiuqing

博文

经典趣味数学—蛙跳问题

已有 10668 次阅读 2009-6-17 22:02 |个人分类:生活点滴|系统分类:科普集锦| 趣味数学, 蛙跳

 
经典趣味数学—蛙跳问题
 
一、问题的描述
网络上流行一个经典的趣味智力游戏—蛙跳游戏（frog leap game）。要求一个人在3分钟内，用最少的步数将左右两边的3只青蛙交换位置。两边的青蛙中间隔着一个空档，每只青蛙的每次跳跃只能跳在空档处，或者跳过一只青蛙后落在空档处。青蛙也不能往回跳。
初始位置
青蛙3
青蛙2
青蛙1
 
青蛙A
青蛙B
青蛙C
完成位置
青蛙A
青蛙B
青蛙C
 
青蛙3
青蛙2
青蛙1
 
 
 
如果你无法在3分钟内完成，就说明你的智商小于75。
提供一个玩这个游戏的网址，http://www.hellam.net/maths2000/frogs.html。
当然，当青蛙数较少时，这是一个非常容易的问题。但是，当两边的青蛙数增多，比如100只时，青蛙该如何跳跃才能交换完位置呢？
现在，我们将问题推广一下：
如果两边的青蛙数分别为n只，双方交换完位置所需要的步数是多少，如何具体实现这些步骤？
更一般地，如果两边的青蛙数分别为n只和m只，双方交换完位置所需要的步数是多少？
 
二、简单的尝试
现在，我们来描述n=1，2，3的青蛙位置的情形。
为了方便，左右两边的青蛙分别标记为F1，F2,F3和Fa，Fb，Fc。空档处用※表示。
我们让左边的青蛙先跳。哪边的青蛙先跳不影响分析结果。
n=1时：
F1
※
Fa
步数
※
F1
Fa
1
Fa
F1
※
2
Fa
※
F1
3
 
 
n=2时：
F2
F1
※
Fa
Fb
步数
F2
※
F1
Fa
Fb
1
F2
Fa
F1
※
Fb
2
F2
Fa
F1
Fb
※
3
F2
Fa
※
Fb
F1
4
※
Fa
F2
Fb
F1
5
Fa
※
F2
Fb
F1
6
Fa
Fb
F2
※
F1
7
Fa
Fb
※
F2
F1
8
 
 
 
n=3时：
 
F3
F2
F1
※
Fa
Fb
Fc
步数
F3
F2
※
F1
Fa
Fb
Fc
1
F3
F2
Fa
F1
※
Fb
Fc
2
F3
F2
Fa
F1
Fb
※
Fc
3
F3
F2
Fa
※
Fb
F1
Fc
4
F3
※
Fa
F2
Fb
F1
Fc
5
※
F3
Fa
F2
Fb
F1
Fc
6
Fa
F3
※
F2
Fb
F1
Fc
7
Fa
F3
Fb
F2
※
F1
Fc
8
Fa
F3
Fb
F2
Fc
F1
※
9
Fa
F3
Fb
F2
Fc
※
F1
10
Fa
F3
Fb
※
Fc
F2
F1
11
Fa
※
Fb
F3
Fc
F2
F1
12
Fa
Fb
※
F3
Fc
F2
F1
13
Fa
Fb
Fc
F3
※
F2
F1
14
Fa
Fb
Fc
※
F3
F2
F1
15
 
三、一般性规律
 
如果你继续尝试，你将得到青蛙的跳跃步数为
3，8，15，24，35，……，
这是一个高阶等差数列。
很容易发现，该数列的通项表达式为（n+1）^2－1。
该表达式的含义为，为完成位置交换，也就是每只青蛙都跳跃了（n+1）步，而最后一只青蛙少跳了一步。
对于两边青蛙数不对称的问题，即左右青蛙数分别为m,n时，完成位置交换所需要的步数为：
（m+1）（n+1）－1。
具体的实现步骤呢？
左右两边轮流跳跃，离开位置后的青蛙相互间隔，即达到最终位置前的途中，都不能与原来本边的青蛙相邻。
    现在，你可以轻松地玩蛙跳游戏了。


https://blog.sciencenet.cn/blog-542-238769.html

上一篇：论文的自我复制算是科研不端行为吗？
下一篇：你可以不信任核心期刊，但你为学术评价做了些什么？
收藏 IP: .*| 热度|

3 刘玉平 曹广福 杨秀海

发表评论 评论 (2 个评论)

数据加载中...
扫一扫，分享此博文

全部作者的精选博文

全部作者的其他最新博文

全部精选博文导读

相关博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-5-16 03:18

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部