三只青蛙互换位置(Frog Chess)的问题应该用什么算法解决

苗哥 发布于 2013/08/17 21:55
阅读 3K+
收藏 1

前几天在网上闲逛看到了壹個小的 FLASH 游戏,游戏内容就是在屏幕上有六只青蛙,左边三只,右边三只,中间还有壹個空格,游戏目标就是通过有限的跳跃次数,让这六只青蛙交换彼此的位置,我试着玩了壹個,大约两三分钟就达成了目标。但是后来我又仔细想了想,三只青蛙的数据不算多,操作起来比较容易。如果不是每边三只青蛙,而是五只、七只或者N(N>=3)只呢,那如果想用最少的次数让这些青蛙交换位置,应该怎么做呢。而且我还发现如果每边的青蛙次数为偶数只时,似乎这個交换位置的问题就是无解的,这是为什么呢?在N只青蛙的情况下,最少需要多少步才能完成这個交换的工作呢?我觉得这里面肯定有什么数学规律,但是百思不得其解,所以发此帖到论坛上让大家壹起来讨论下,如果需要用算法的方式把这個问题解决,应该是什么样的呢?

请大家各抒已见,期待不同观点或者意见。

开始时候的画面:

过关之后的画面:

游戏地址在此:http://s15.photobucket.com/user/hilllynx/media/9242c12c.swf.html

规则:
(1) 用鼠标点青蛙头部向前跳;
(2) 最多每次可以前进壹步;
(3) 最多只能跳过壹個青蛙;
(4) 壹次壹步,不限颜色;
(5) 只能前进,不能后退;
(6) 按红色箭头,游戏复原;
(7) 此题肯定有解,不要怀疑。

目标:两边不同颜色的青蛙互换位置。


加载中
0
f
flyaway12
可以用搜索算法来计算,但是青蛙个数偏大的话,计算量就会变得很大。我写了一篇博客,可以看看: http://zhouyichu.com/%E7%AE%97%E6%B3%95/2013/09/06/Frog-Chess-Problem.html。另外,貌似不存在偶数与奇数的问题,总能找到一个移动序列的。
f
flyaway12
回复 @铂金小熊 : 最开始的时候我也想往汉诺塔的方向上靠,但是找不到合适的递归关系,所以只能选择这种比较“笨”的办法了。
苗哥
苗哥
谢谢,我仔细看了下你的分析思路,确实是壹种解决方法。其实我最初是想参考汉诺塔的解决方式,找出递归条件和终止条件,不过最终没能找出来,在你提供这個思路的基础上,我可以再尝试着找找看。
0
韭零后张子游
韭零后张子游
我半年前做过这个了。过了。当时是一个exl
0
Brokedge
Brokedge
能实现感觉到不是什么问题~等明天算算时间复杂度~
返回顶部
顶部