haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中英语初中英语

有趣的老马识途

发布时间:2014-01-14 15:53:18  

有趣的老马识途

老马识途又叫马的旅途,它是一只马在标准棋盘任意格上出发,连走64步,要求每一步都不重复落脚一个格子、也就是每个格子只落脚一次,这样走满整个棋盘所有格子。如图:

最早的老马识途例子出现在公元九世纪,当时提出了两种走法,就是上两图,作者一知名一不知名。当时国际象棋刚成型。

其中有种形式叫“回环旅途”,意思就是马走到最后一格正是它出发第一步所跳到的那格,也就是再走一步就可以走回原地,其它条件不变。如图:

两个图都很有美感,左图呈轴向对称,右图呈四角对称。

对这个谜题的第一次正式研究是1759年的柏林数学家Euler。到了1823年有个叫H. C. Warnsdorff的人提出了一种推演方法,它的主旨就是要避开绝路--即那些马立在上面如果不重复跳已到达过的地方就没有去路的格子。为了避开绝路,在每走一步前都要检查下一步所可能到达的格子,方法是分别统计每一个下一步可能到达的格子它本身有多少条符合规定的可选路线,把这个数字标记在相应每个格子里,然后就跳到数字最小的那个格子;如果全部格子数字相同,就随便到一个。如图:

比如上述第八横线标记数字3的那个格子(不是有圆圈框住的那个3,那只是步数序列),马在这个格子上有四个点可去,可是有一个已经到过,所以它有三条路线符合规定,标记的数字就是3;余类推。 Chessbase网站提供两个小程序能够帮你实践老马识途,前一个简单,适合一般解法;后一个复杂些,还能解回环旅途。

http://www.chessbase.com/columns/images/kt-tour.zip

http://www.delphiforfun.org/Programs/Download/KnightsTour.zip

如果熟悉电脑程序设计语言的,想必可以编程求解这个问题,甚至归纳出算法。

老马识途是怎么样又提出来的呢?原来在最近德国一个娱乐性观众上台参与的电视节目里,有个来自巴伐利亚的9岁男孩,在电视上表演只凭脑袋想,不借助棋盘,从任意一格出发完成老马识途--应该说是“少马识途”了。这项本事引起媒体轰动,因为一个9岁的孩子闭目去解这个谜题实在有点不好想像,尽管他肯定做过大量演习准备。 那么老马识途究竟有多难呢?

Chessbase网站于是邀请新任18岁以下组世界女子冠军Elizabeth Pahtz来表演,她说:“我小孩时就可以解这个题目,但现在忘记了。”于是请她再次学习。她用了40分钟花了一番功夫完成了一次旅程。 那么如果是不那么专业的人去做呢?又邀请一位20岁的已放弃下棋6年的年轻程序员来试验,他可是有着数学算法的头脑。结果过了12分钟的研究他宣布能解,只用空棋盘而不摆棋子。检查证明他的走法是非常正确的。

再努力一番,他就能够不用看着棋盘只凭指示完成一次旅程。他

样做只能从一个格子出发,不过他打赌说只需半小时练习就能做到从任意格子出发完成回环旅途,大概练习一小时就能闭目什么都不看来完成。

所以,这才看出闭目完成并不那么神秘,大家也可以花些时间玩玩老马识途,使用上面提供的小程序辅助,准备享受成功乐趣吧。哪怕你上不了电视,也可以在众人面前露一手。

下图是那个9岁的德国男孩在电视上闭目完成的回环旅途路线记录:

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com