Sha——中国传统游戏集 2.3:闯关游戏——汉诺塔

这是本博客介绍BSoftMiner公司的一款iPhone/iPad游戏软件Sha!的系列文章之一。

Sha!是一款趣味性和益智性都很强的“多合一”免费游戏软件,汇集了中国具有代表性的各种传统民间游戏。Sha!包含了三类游戏:“对弈游戏”、“闯关游戏”和“智力趣题”。本文介绍其闯关游戏之“汉诺塔”(又称“河内塔”)。

1 游戏背景

最早发明这个问题的人是法国数学家爱德华·卢卡斯。

传说印度某间寺院有三根柱子,上串64个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。

若传说属实,僧侣们需要 (2^64 − 1) 步才能完成这个任务;若他们每秒可完成一个盘子的移动,就需要5846亿年才能完成。整个宇宙现在也不过137亿年。

这个传说有若干变体:寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭,其中一说是位于越南的河内,所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

佛教中确实有“浮屠”(塔)这种建筑;有些浮屠亦遵守上述规则而建。“河内塔”一名可能是由中南半岛在殖民时期传入欧洲的。

2 游戏规则

每次只能移动一个圆盘。大盘不能叠在小盘上面。

游戏的目标是:以最少的步数,将所有的盘子从最左边的塔移到最右边的塔。

3 解法

许多的汉诺塔玩具都有 8 个盘子(disks)。在初学者看起来似乎不太可能有解,然而其算法是相当简单的。对于三塔的汉诺塔,最少移动步数为:(2^n − 1),n是盘子总数。

4 多塔汉诺塔问题

在有3个柱子时,所需步数的公式较简单,但对于4个以上柱子的汉诺塔尚未得到通用公式,但有一递归公式(未得到证明,但目前为止没有找到反例):

令f(n,k)为在有k个柱子时,移动n个圆盘到另一柱子上需要的步数,则:

对于任何移动方法,必定会先将m(1<=m<=n-1)个圆盘移动到一个中间柱子上,再将第n到第n-m个圆盘通过剩下的k-1个柱子移到目标柱子上,最后将m个在中间柱子上的圆盘移动到目标柱子上。这样所需的操作步数为2f(m,k)+f(n-m,k-1)。 进行最优化,易得:

f(n,k)=min(2f(m,k)+f(n-m,k-1)), x在1和n-1之间。

5 游戏级别

Sha!中的“汉诺塔”游戏提供了三塔和四塔,盘子数从两盘直至二十盘的各种组合级别,标准步数从3步,到几十步,到几百步,直至上百万步!够你玩的吧!

6 标准答案和个人纪录

点击“标准答案”图标,您可以观看本级别的标准答案的动画演示过程。您可以连续播放、暂停、单步回退、单步前进或中止退出。

如果您自己闯过了本关,最少步数的闯关过程将称为您的本机纪录而被保存起来。点击“本机纪录”图标,您可以观看本局的本机纪录的动画演示过程。您可以连续播放、暂停、单步回退、单步前进或中止退出。

7 游戏手册

Sha!中的其他游戏一样,“汉诺塔”也有完整的《用户手册》,包括:“游戏规则”、“游戏背景”和“关于Sha!”。

“游戏规则”中对“汉诺塔”游戏进行了基本表述,并阐述了相应的游戏规则和游戏目标。

“游戏背景”中对“汉诺塔”游戏的背景历史进行了介绍。同时,作为公共介绍部分,还对中国传统民间游戏进行了简单的介绍。

“关于Sha!”是对Sha!这个游戏本身进行一般性介绍。

8 选购功能包

Sha!的所有游戏都是免费可玩的,但是如果您希望更多的功能和挑战,Sha!也提供了各种选购功能包。

和“汉诺塔”游戏直接相关地选购功能包是:

  • P303 – 汉诺塔所有级别和答案。您可以免费地玩部分级别,但是如果您想挑战所有的汉诺塔级别并观看其标准答案(当前的级别及将要陆续加入进来的级别),则必须购买本功能包。值得一提的是,本功能包只需要购买一次,就可以玩汉诺塔当前的所有级别及将要陆续加入进来的新级别,并能观看其解答过程。
  • P001 - 不显示广告。请理解本游戏需要广告收入来维持维护。如果您觉得广告扰人,您也可以选购本功能包使得广告不再显示。值得一提的是,本功能包只需要购买一次——无论何时一旦购买,在所有游戏中将不再显示广告。
  • P000 - 一次性买断Sha!。用户只需要一次性花不多的钱,就买断Sha!目前和将来的所有功能,而不需要分别购买多个单个的功能包,绝对超值加保值!

9 多语言支持

Sha!支持多种语言,例如:英语、简体中文、繁体中文、日语、韩语、法语、德语、西班牙语、意大利语等等。根据您的iPhone/iPad中的语言设定,Sha!会自动显示您设定的语言版本。

10 安装地址

您可以在App Store输入关键字sha或者bsoftminer,然后安装Sha!在您的iPhoneiPad设备上。以下是Sha!相应的安装地址:

iPad版:

  • Sha!-HD(免费)
    http://itunes.apple.com/us/app/sha!-hd/id541493099?ls=1&mt=8

iPhone版:

  • Sha!(免费)
    http://itunes.apple.com/us/app/sha!/id534910477?ls=1&mt=8

本系列其他相关文章

Leave a Comment

 
 
 

*

Contact Us

Login / Logout

Categories

Recent Posts

Links