冒险解谜游戏中文网 ChinaAVG

标题: AVG谜题探索（05）--------------石堆与梵塔 [打印本页]
作者: vexer    时间: 2007-9-1 22:18
标题: AVG谜题探索（05）--------------石堆与梵塔
[attach]6590[/attach]
! q& G4 b) R" V9 I% U
    这次的谜题出自《回声：秘洞之谜》。玩过此作的朋友一定还记得。当主角阿洛克历经波折终于见到老画家克莱姆时。克莱姆要主角先要自己领悟到底该在石壁上画什么。这时克莱姆的助手塔尔告诉主角，可以送给主角一个有趣的东西，或许对主角会有所帮助。但是想让主角帮忙寻找他的牛吼器。而实际上塔尔的牛吼器挂在了一棵高树上，想要上去就需要将树旁的一堆石头堆到树下，如下图：
1 Z9 @7 c- A% H  ?! z6 m5 Z: b
  [attach]6591[/attach]
. m- C' I; H* J8 p7 q* @   
    经过尝试，我们会发现移动过程中有三个限制。其一，只有图中ABC三个位置可以堆放石头。其二，移动过程中，较大的石块只允许放较小的石块在下面。其三，每次只能移动一块石头，不可以一堆一起移动。我们要做的就是把所有石头全都堆到树下的B点，而使得主角阿洛克可以由此爬到树上。 / x0 g6 q" z3 |9 K. S" e; x! a5 \
   
    这个迷题本身并不是十分复杂，我估计大家随便尝试几分钟总是能完成的。之所以选择这个谜题是因为谜题背后有着一个非常有趣的传说。我们不妨先来一起看看这个源自古印度的关于世界末日的古老传说。 1 F* r9 R+ b! A( `; _: x: V
5 `. V, Y3 y8 O: m* m2 L* `
    相传，在世界的中心贝那勒斯（印度北部的佛教圣地）的圣庙里，安放着一块黄铜板，板上插着三根宝针，细如韭叶，高约腕尺。梵天在创造世界的时候，在其中的一根针上，从下到上串上由大到小的四十六片金片。这就是所谓梵塔。当时梵天授言：不论黑夜白天，都要有一个值班的僧侣，按照梵天的不渝法则，把这些金片在三根针上移来移去，一次只能移动一片，并且要求不管在那根针上，小片永远在大片上面。当所有的六十四片，都从梵天创造世界时所放的那根针，移到另外一根针上时，世界就将在一声霹雳中消灭，梵塔、庙宇和众生，都将同归于尽！这便是世界的末日…….。
) l- O( z3 I+ [, e
/ ]) i% q% u) s! H$ u$ s: H    大家此时应该发现了，《回声》中的石堆问题不就是梵塔的简化版么。没错，我们再来看看梵塔的传说。虽然我们知道梵塔与世界末日并没有必然联系，而且现实中的梵塔也早已不存在。但是，我们不妨来算算若是按照传说中所言，世界末日最早到底将会什么时候到来。要知道这个答案，我们就需要先得到把六十四个金片移动到另一个宝针上的最少移动次数。OK!从简单入手，我们还是回到《回声》中只有五片石头的石堆问题。
0 E, O  Y# `0 [1 k; N
1 |/ |, m& S: A: N( s( p6 r    如何设计一种最为快捷的移动方法呢？我们不妨将五块石头从小到大编上号1-5。先来分析最下面的5号大石头，它是最终要从图中C移动到B的。我们不难发现要完成这次移动需要两个先决条件：首先，5号上必须没有其他石头才能移动。同时，由于大石头只能放在下面，那么往B处移动的时候B处显然必须是空的。这样我们先要达到下图中的状态才能完成这次移动： 6 G+ @# C, `# b

% Y: U& b( X6 \1 u
[attach]6592[/attach]

2 Q% g# t+ O) r) Z; G
3 F$ ]* O' `2 v: Y而在完成这次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）。同样的道理我们可以得到：
& X5 Y2 w+ u. i8 T% |N(1)=1
  r3 R( E. i/ M( n( \N(2)=2X1+1=3 - K" C+ F5 y$ u( r8 e
N(3)=2X3+1=7
  g  z# U. {9 \. z% w7 _( n9 F. j2 gN(4)=2X7+1=15
) J  n$ Q1 n* O/ ^$ |; `9 }7 ]0 GN(5)=2X15+1=31 & t1 N5 R3 D) s: G- I# Q# t  \( z
那么，我们由此可以知道将5个一堆的石头完全移到另一堆至少需要31步。当然实际操作过程中我们还需要注意另外一个细节：由于我们是要将石头堆到B而不是A，因此1-4必须先移到A而空出B。同样的道理，1-3必须则必须先到B而不是A；1-2必须先到A；1则先必须处于B；如此交错。搬完5后面的过程也需要注意这个问题。不然所用步骤可能就不是最少。 + v* T6 `# r: |4 }
[attach]6593[/attach]

- ^2 l" U9 Z$ F. C6 J( y$ S! Q% A! o- m
0 ]1 B9 }0 }0 C' g+ ?  U# k    到此为止我们已经完全解决了搬石头的问题。我们再来看看更为复杂的梵塔。前面我们其实已经找到了递推公式：
' V+ I1 I6 m, D3 x2 g+ c8 PN(X)=2XN(X-1)+1 . z! _& k  f3 p0 Y  j1 e$ y
而经过简单的数学归纳，我们可以得到： ' P: A% j1 E) q. R
N(1)=2^1-1=2-1=1 9 i- [; A* Y; P1 N( w  d$ F
N(2)=2^2-1=4-1=3
5 \9 c2 k& m( `# q! u$ u/ {& B. S; yN(3)=2^3-1=8-1=7 + l6 X! O' m, }2 S& L' i: T0 a
… 0 j" _* E+ b5 E5 {3 a* X' z
N(X)=2^X-1
7 C6 L' ]% W( i/ T2 g: }. L/ X由此可见，而梵塔中的六十四个金片搬完则需要大约二的六十四次方步。照此来算，如果一步需要1秒时间那么全部搬完也得要等上2^64/(365x24x60x60)=5800亿年～～那时还有地球么？看来即便梵塔的传说是真有其事，我们也大可不必为世界末日担心了。
作者: vexer    时间: 2007-9-1 22:29
谜题本身并不是十分复杂～但是谜题的思想应该是出自印度的传说   e. X5 Y6 b- ?* f+ h: P
翻翻古老的传说，分析分析谜题，个人觉得也挺有意思的。
; i8 d# \" Y! r$ @% [* J# J& E不知大家对此感兴趣不～
作者: fenmu    时间: 2007-9-1 23:35
这个貌似叫汉诺塔?
作者: 三生石    时间: 2007-9-1 23:36
文章慢慢看，先顶这只乐天的小鼠。
- L! Q2 K4 B0 i& o; N
) S0 }4 M, I) x+ E“整成这样就sb了”旁边石头造型很像小狗狗的。。。
作者: vexer    时间: 2007-9-2 00:30
对～也有叫汉诺塔的，估计语言之间翻译来翻译去的就不同了吧～ 汉诺 梵 音也有些相近嘛～
作者: soring123    时间: 2007-9-2 08:13
以前C语言有编程解这个 已经是往昔岁月了 呵呵
! O7 [1 |5 J3 z5 n不过估计逻辑和数据结构 道理应该是一样的
作者: fenmu    时间: 2007-9-2 22:11
这个东西在计算机编程里面要用到递归~
作者: vexer    时间: 2007-9-2 22:38
分母兄知道得真是多啊~PFPF
作者: 闪光    时间: 2007-9-4 08:44
想起命运之手的最后关头，整了一个这个，七层，而且非常不直观（从底下往上看）
作者: 82593918    时间: 2007-9-21 01:07
原来觉得太简单所以没在意，想不到还有这么个传说 [s:23]
作者: uranus1997    时间: 2008-10-3 12:27
[s:27] 这个谜题其实就是递归算法的经典例题——汉诺塔。。。。- G' j/ u" I9 r/ y0 @4 u" `- j
要是多几层，内存少的计算机会堆栈溢出。。。。死机 [s:23]
作者: bin12345    时间: 2008-10-8 07:14
这个是汗诺塔么..?
作者: wqzss    时间: 2008-10-9 16:46
极其典型的递归算法，如果你多弄几层的话，就会觉得自己简直快要变成机器了 [s:2]
作者: gjg214607    时间: 2008-10-18 00:59
好像在小学奥数里有这种问题了。



欢迎光临 冒险解谜游戏中文网 ChinaAVG (https://www.chinaavg.com/) Powered by Discuz! X3.2