干货–汉诺塔游戏解法完整版

这个游戏大家想必都不陌生:

干货——汉诺塔游戏解法完整版

当然,游戏是有规则的,否则把所有的圈圈们连根拔起,一下扔过去就结束了。。。

规则一:每次操作只能移动一个圈圈,把它从一个柱子移到另一个柱子上;

规则二:大圈圈不能架在小圈圈的上面。

今天咱们就来说说这个游戏。

游戏的名字,最通俗的叫法是汉诺塔,英文名Tower of Hanoi。

Hanoi在英文里是河内(越南首都)的意思,所以,其实还是叫河内塔更准确些。

神话故事

这是一个古印度的游戏,源自古印度神话:

干货——汉诺塔游戏解法完整版

印度教的主神梵天创造世界时,做了三根金刚石的柱子,并在其中的一根柱子上按照大小顺序依次放置了64个黄金圆盘。

梵天神告诉侍奉他的婆罗门(祭司),要借助一根柱子做中介,来把这64个圆盘一起移动到另一根柱子上;规则和上面说的一样,在三根柱子间一次只能移动一个圆盘,而且大圆盘不能放在小圆盘之上。

梵天大神说了,只要你们能实现最终的目标,世界就会在一个闪电中毁灭。

据说,这个婆罗门和他的后人从此就开始一刻不停的挪圆盘,以愚公移山的精神,为世界的最终毁灭贡献自己的力量。

让 他 们 先 挪 一 会 !

解法概述

我们来看看解法。

对于河内塔游戏而言,无论是64个盘子,还是8个盘子,或是3个盘子,盘子的数量只会影响具体操作的复杂度,和方法本身关系不大。

要讲清楚解谜的方法,盘子数太多了没意义,太少了又不典型,因此咱们采用8个盘子为例,把这个问题说明白:

有ABC三根棒子,其中在A棒上有8个从大到小排列好的盘子。现在要以B棒为过渡和中转,把这8个盘子最终都移到C棒上。

干货——汉诺塔游戏解法完整版

学过计算机编程基础的小盆友们都知道,解决河内塔问题大体有两种思路:迭代非迭代

迭代的解法

迭代的方法非常简单,也很好玩。

记得那个经典的笑话吗:

把大象放进冰箱要几步?

分三步:

1、把冰箱门打开;

2、把大象塞进去;

3、把冰箱门关上。

嗯,跟这个笑话类似:

你不是想要找一个办法把8个盘子都移到C棒吗?

分三步:

1、假设有了一个办法,把前7个盘子一起都移到B棒。

2、把最大的盘子移到C棒。

3、再用想象中的办法,把B棒上那7个盘子都移到C棒那个最大的盘子上。

问题就解决了。

干货——汉诺塔游戏解法完整版

图中深黄色的盘子可视为任意数量:对任何N个盘子的情况,都可以简化为将N-1个盘子先移到中转棒,将最大的盘子移到目标棒,再将N-1个盘子移到目标棒

那么如何完成第一步和第三步里,把7个盘子整体移动呢?

继续迭代:先把前6个盘子都移到C棒,再把最大的那个移到B棒,再把C棒上那6个盘子移回B棒上来。

每一次迭代,都使得需要移动的盘子数减少了1;一直迭代下去,直到最原始的情况:把一个盘子移到另一根棒子上。

这个原始情况解决了,那么依次倒回去,所有的问题都解决了。

仍然用大象和冰箱的例子作比,那就是:

中间的第二步,如何把大象塞进去呢?

先把大象头塞进去;

再把大象身体塞进去;

再把大象腿和尾巴塞进去。

大象的头如何塞进去呢?

先把鼻子塞进去;

再把脸塞进去;

再把后脑勺一股脑塞进去。

大象鼻子怎么塞进去呢?

先把第一段鼻子塞进去;

再把第二段鼻子塞进去;

……

迭代法,就是这么简(bao)单(li)而且易(liu)行(mang)

正因为如此,这个方法也成为大学里教授计算机编程思想的必修内容之一:几乎所有的计算机专业的大学生都遇到过这个问题和解法。

程序是解决了,但这其实并不是一个正常人类能看懂和操作的方法;你能写出这样的程序让计算机给出答案,可是当你实际遇到8个盘子叠起来时,还是一样抓瞎没辙,并没有实际的指导意义。

有没有直观的、操作性强的统一解法呢?

当然有。

这就是所谓非迭代的解法。


以下慎入,因为当你看完后,你会发现此游戏的所有乐趣都被剥夺殆尽,只剩下了极其简单和无聊的解谜过程


非迭代的解法

同样以8个盘子为例:

干货——汉诺塔游戏解法完整版

A棒上的8个盘子要全部移到目标C棒,

所以:

最大的8号盘的目标是C棒。

次大的7号盘的目标就应该是B棒。

以此类推,6号盘的目标又是C棒。

5号盘的目标是B棒。

4号盘的目标是C棒。

3号盘的目标是B棒。

2号盘的目标是C棒。

最小的1号盘,目标是B棒。

总而言之:

1、3、5、7号盘的目标是中转棒B;

2、4、6、8号盘的目标是目标棒C。

这8个目标把整个问题分成了8步,而且和刚刚迭代法那不负责任的3步比起来,这8步的指导意义是很强的:

第一个目标,就是将最小的1号盘移到中转棒B棒上。——这个目标当然一步就能实现:

干货——汉诺塔游戏解法完整版

然后将2号盘移到目标棒C棒上。——也是一步就可以实现:

干货——汉诺塔游戏解法完整版

下一个目标,就是把3号盘移到B棒。这时由于1号盘占上了B棒的坑位,所以要先把它挪到C棒,腾出B棒的位置,再把3号盘移过来:

干货——汉诺塔游戏解法完整版

下面类似:1号移回A,2号移上B,1号移上B,4号移到C:

干货——汉诺塔游戏解法完整版

后面的思路都一样,不再赘述:总之,8个目标是分别让1、2、3、4、5、6、7、8号盘依次就位:

干货——汉诺塔游戏解法完整版

干货——汉诺塔游戏解法完整版

干货——汉诺塔游戏解法完整版

干货——汉诺塔游戏解法完整版

当8号盘在C棒就位以后,下面就是要让7号去C棒。

要实现这一点,6号要去A,5号去C,4号去A,3号去C,2号去A,1号去C。

也就是说,接下来的一步是让1号盘移到C棒。

再重复一下问题的关键:对于8个盘的情况,其实盘子们分别要去的目标是唯一的——

1、3、5、7号盘去中转棒B,

2、4、6、8号盘去目标棒C。

不仅如此!

在操作中的每一步,你想要移动的目标盘和你实际移动的盘之间,保持间隔始终为偶数,就一定没问题。

举例来说,在某一个中间状态,12345号盘一起堆在C棒上,你想把它们一起弄到B棒;这时1、3、5号盘的目标就是B棒,2、4号盘的目标是A棒。所以此时要做的第一步就是把1号盘移到B棒。

嗯,你已经获得了这个游戏的精髓。

这么一来,这个游戏还有什么乐趣可言呢??

没有了。

即使是64个盘子,我们也能一下得到所有的中间状态:把所有盘子从小到大编号,所有的奇数号盘子(1,3,5,7,…)一律去中转棒,所有的偶数号盘子(2,4,6,8,…)一律去目标棒;当第64个盘子就位以后,再将所有的奇数号盘子的目标定为目标棒,把剩下的偶数号盘子的目标定为中转棒,直至第63个盘子就位;然后再继续重复这一过程,直至所有盘子就位。

好枯燥,好简单,好无聊!

复杂度

那么我们来看看这个话题里最后一个有点意思的内容:

操作开销和时间开销。

要实现64个盘子移位的终极目标,要做多少次有效的移动?

——所谓有效移动是指,假设这些婆罗门和后代们把其中的算法和过程都研究得很清楚,奇偶数的盘子都没有数错,老眼昏花、头昏脑胀,移的过程乱七八糟等等,所有这些意外统统不出现:

那么一共至少要多少步呢?

很好算。

1个盘子就位需要1步,

2个盘子都就位需要3步,

从3个盘子开始,就需要先用3步使前2个盘子都移到中转棒,再来1步使第三个盘子就位,再来3步使前2个盘子都移到目标棒,一共就是3+1+3=7步。

4个盘子全部就位,需要7+1+7=15步。

按照归纳法进行简单的计算,容易知道:

n个盘子全部就位,需要总步数为:2的n次方-1。

也就是说,对于梵天神64个盘子的完整版,婆罗门和后人们一共只需要移动2的64次方-1步,就可以就位啦!

这个过程其实很快的,只要他们能做到并且维持每秒移动1个盘子的速度,那么一共只要2的64次方-1秒,合5800亿年,就能把64个盘子正确就位,使得宇宙在闪电中毁灭!

不过,据科学家分析,宇宙的寿命也就在150亿年左右……

好吧梵天还是你赢了!!~



本文链接地址:http://www.xysx.org/archives/506

你也许会喜欢与本文相关的:

数学益智小游戏系列介绍之汉诺塔问题

数学益智小游戏系列介绍之汉诺塔问题

文章

来源:百度百科 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘...

xysx.org 欢迎您!

Leave a Reply