The Tower of HANOI

Submitted by Lizhe on Wed, 05/10/2017 - 15:59

汉诺塔问题经常被用于递归的教学,当然还有一个印度传说

在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。

这里纯粹是无聊重新研究一下

先考虑一下"小"问题

先假设如果有1块disk,当然只需要1步就可以结束整个过程,我们用T1来表示总共需要的步数 T1 = 1

如果有2块disk, 很容易想到是 T2 = 3 (自己脑补一下过程)

3块的时候一共需要7步, T3 = 7 (还是自己脑补)

然后考虑"大"一点

按照前面的经验,

首先需要把除了最大的一个disk之外的所有disk都移动到中间  Tn-1

然后移动最大的一块, T1 ( 也就是1 )

然后把刚才中间的Tn-1这些disk移动到最大那个上面, 又是一个Tn-1

然后重复这个过程

也就是说移动 Tn = 2* (Tn-1) + 1

当然还有一个T0 = 0的情况

写成公式就是

Tn = 0                               ( n=0)

Tn = 2* (Tn-1) + 1        ( n>0)

递归只是帮助让问题变得简单,不过估计没人愿意用递归计算T100, 实际公式是

Tn=2n -1

好吧这又是一个数学归纳法问题, 计算机才不会care计算有多麻烦,所以递归是最好的 ( 愚蠢的程序员和他的无聊程序啊 )

出于好奇这里稍微看一下归纳法是如何做的

先带入刚才T0那个公式, T0=20-1 显然是对的 结果是 0

然后试试n>0的情况, 将递归公式和归纳法得出的公式混合一下

将 Tn = 2* (Tn-1) + 1 [递归公式] 里边的Tn-1用Tn=2n -1 [归纳法公式] 替换 

因为 Tn-1 = 2(n-1) -1  就是把n写成n-1

所以Tn = 2*(Tn-1 )+1 = 2*(2(n-1) -1) + 1 = 2n-1

 

所以n=100时, 你需要 2100-1 = 1267650600228229401496703205375 

用Python写个递归试一下看看结果对不对


def countStep(n):
    if n==0:
        return 0;
    else:
        return 2*countStep(n-1)+1
    
print(countStep(100));
1267650600228229401496703205375
 

221