AVG谜题探索（05）--------------石堆与梵塔

vexer · 发表于 2007-9-1 22:18

这次的谜题出自《回声：秘洞之谜》。玩过此作的朋友一定还记得。当主角阿洛克历经波折终于见到老画家克莱姆时。克莱姆要主角先要自己领悟到底该在石壁上画什么。这时克莱姆的助手塔尔告诉主角，可以送给主角一个有趣的东西，或许对主角会有所帮助。但是想让主角帮忙寻找他的牛吼器。而实际上塔尔的牛吼器挂在了一棵高树上，想要上去就需要将树旁的一堆石头堆到树下，如下图：

经过尝试，我们会发现移动过程中有三个限制。其一，只有图中ABC三个位置可以堆放石头。其二，移动过程中，较大的石块只允许放较小的石块在下面。其三，每次只能移动一块石头，不可以一堆一起移动。我们要做的就是把所有石头全都堆到树下的B点，而使得主角阿洛克可以由此爬到树上。

这个迷题本身并不是十分复杂，我估计大家随便尝试几分钟总是能完成的。之所以选择这个谜题是因为谜题背后有着一个非常有趣的传说。我们不妨先来一起看看这个源自古印度的关于世界末日的古老传说。

相传，在世界的中心贝那勒斯（印度北部的佛教圣地）的圣庙里，安放着一块黄铜板，板上插着三根宝针，细如韭叶，高约腕尺。梵天在创造世界的时候，在其中的一根针上，从下到上串上由大到小的四十六片金片。这就是所谓梵塔。当时梵天授言：不论黑夜白天，都要有一个值班的僧侣，按照梵天的不渝法则，把这些金片在三根针上移来移去，一次只能移动一片，并且要求不管在那根针上，小片永远在大片上面。当所有的六十四片，都从梵天创造世界时所放的那根针，移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生，都将同归于尽！这便是世界的末日…….。

大家此时应该发现了，《回声》中的石堆问题不就是梵塔的简化版么。没错，我们再来看看梵塔的传说。虽然我们知道梵塔与世界末日并没有必然联系，而且现实中的梵塔也早已不存在。但是，我们不妨来算算若是按照传说中所言，世界末日最早到底将会什么时候到来。要知道这个答案，我们就需要先得到把六十四个金片移动到另一个宝针上的最少移动次数。OK!从简单入手，我们还是回到《回声》中只有五片石头的石堆问题。

如何设计一种最为快捷的移动方法呢？我们不妨将五块石头从小到大编上号1-5。先来分析最下面的5号大石头，它是最终要从图中C移动到B的。我们不难发现要完成这次移动需要两个先决条件：首先，5号上必须没有其他石头才能移动。同时，由于大石头只能放在下面，那么往B处移动的时候B处显然必须是空的。这样我们先要达到下图中的状态才能完成这次移动：

而在完成这次5从C到B的移动后，我们只需要再把1-4从A移动到B就完成了整个移动过程。如果将4个石头完全移动到另外一堆最少需要N(4)步，那么我们可以很容易得到5块石头完全移动需要N(5)=N(4)+1+N(4)步（对应步骤一、1-4从C到A。二、5从C到B。三、1-4从A到B）。同样的道理我们可以得到：
N(1)=1
N(2)=2X1+1=3
N(3)=2X3+1=7
N(4)=2X7+1=15
N(5)=2X15+1=31
那么，我们由此可以知道将5个一堆的石头完全移到另一堆至少需要31步。当然实际操作过程中我们还需要注意另外一个细节：由于我们是要将石头堆到B而不是A，因此1-4必须先移到A而空出B。同样的道理，1-3必须则必须先到B而不是A；1-2必须先到A；1则先必须处于B；如此交错。搬完5后面的过程也需要注意这个问题。不然所用步骤可能就不是最少。

到此为止我们已经完全解决了搬石头的问题。我们再来看看更为复杂的梵塔。前面我们其实已经找到了递推公式：
N(X)=2XN(X-1)+1
而经过简单的数学归纳，我们可以得到：
N(1)=2^1-1=2-1=1
N(2)=2^2-1=4-1=3
N(3)=2^3-1=8-1=7
…
N(X)=2^X-1
由此可见，而梵塔中的六十四个金片搬完则需要大约二的六十四次方步。照此来算，如果一步需要1秒时间那么全部搬完也得要等上2^64/(365x24x60x60)=5800亿年～～那时还有地球么？看来即便梵塔的传说是真有其事，我们也大可不必为世界末日担心了。