There is only one problem to solve——汉诺塔问题

汉诺塔问题的描述如下,汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从上往下从小到大顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘,只能移动在最顶端的圆盘。

那么这里我们也先来思考最简单的情况(变量当然是盘子的个数\(n\)啦),那么最简单的就是\(n=1\)了(当然,\(n=0\)也可以算是一种情况,不过没必要分析了)

不妨假设原始的柱子为\(A\),目标柱子为\(C\),

hanoi-tower-1

此时直接将盘子从\(A\)柱移动到\(C\)柱即可。

再来看\(n=2\)的情况,此时我们分三步走,一是将大盘子上的小盘子移动到别的柱子上,二是将大盘子移动到作为目标的柱\(C\)上,最后把小盘子也移动到柱\(C\)上。

hanoi-tower-2

那么对于更一般的情况呢?总的来说,我们的策略也没有改变,仍然是是先将大盘子上的小盘子移动到别的柱子上,接着是将大盘子移动到作为目标的柱\(C\)上,最后把移动过的小盘子也移动到柱\(C\)上。

不妨这样想,我们的目标是将原始柱子\(A\)上,最大的那个盘子移动到目标柱子\(C\)上,此时,在最大的盘子之上的,都是比它小的盘子,那么根据规则,要移动(仅仅是移动)这个最大的,我们就必须先将这些小的都移开;接下来,要将这个最大的放在目标柱子\(C\)上的话,由规则可知,在目标柱子\(C\)上必须没有比它小的盘子。

那么,我们的移动过程中必有一个状态是这样的:所有的小盘子都在柱\(B\)上,最大的盘子在柱\(A\)上,且柱\(C\)上没有比它小的盘子。

hanoi-tower-n-1

只有这样,我们才能将最大的那个盘子移动到柱\(C\)上。

那接下来,这些小的盘子怎么办?

事实上,我们可以忽略柱\(A\)和柱\(B\)的区别,将柱\(B\)看作是新的柱\(A\),那么对于柱\(B\)上最大的盘子来说,在它之上的,都是比它小的盘子,与刚才类似的,我们又必然经过如下状态才能将柱\(B\)上最大的盘子移动到目标柱\(C\)上。

所有的小盘子都在柱\(A\)上,最大的盘子在柱\(B\)上,且柱\(C\)上没有比它小的盘子。

hanoi-tower-n-2

看到这里,或许会问柱\(C\)上已有的大盘子会不会对这个过程有所影响?实际上,我们若是稍微修改一下规则,规定只要某个盘子移动到柱\(C\)上以后,其余的所有盘子,没有比这个盘子更大的话(事实上这就是我们的目标),这个盘子就可以被扔掉了。这意味着我们完成了一次对最大的盘子的移动,然后我们将这个最大的盘子从游戏中消除了。又或者可以考虑为,当我们在处理有\(n=i\)个盘子时,第\(i+1\)大的盘子已经被正确移动到了柱\(C\)上,然后被扔掉了,由于第\(i+1\)大的盘子被扔掉的条件是,当第\(i+1\)大的盘子移动到目标柱\(C\)上时,其余的所有盘子,没有比这个盘子更大的,所以这又意味着第\(i+2\)大的盘子也被正确移动到了柱\(C\)上,然后被扔掉了……

若以一开始的\(n=1\)时的盘子作为例子的话,若要移动它到柱\(C\),并且这次移动之后即完成汉诺塔问题的话,那么意味着所有比它大的盘子都已经正确的移动到了柱\(C\),假如我们没有扔掉那些大盘子的话,则如下图所示,如是扔掉了的话,则会和一开始的图一样。

hanoi-tower-n-3

于是对于汉诺塔问题,我们唯一要解决的问题就是,看准最大的那个盘子,将在它之上的其他小盘子都移动到非目标柱之上,然后移动最大的那个盘子到柱\(C\)。

声明: 本文为0xBBC原创, 转载注明出处喵~

《There is only one problem to solve——汉诺塔问题》有2个想法

  1. 在啃严奶奶的数据结构,用python跑了下:

    s = 0
    def hanoi(n,x,y,z):
    	if n==1:
    		move(x,1,z)
    	else:
    		hanoi(n-1,x,z,y)
    		move(x,n,z)
    		hanoi(n-1,y,x,z)
    def move(x,n,z):
    	global s
    	s = s + 1
    	print("Move disk " + str(n) + " from "+ x + " to " + z)
    	print("Step " + s)
    
    hanoi(3,"a","b","c")
    

发表评论

电子邮件地址不会被公开。 必填项已用*标注