The Tower of HANOI – 我的经验分享

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

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

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

先考虑一下”小”问题

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

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

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

然后考虑”大”一点

按照前面的经验,

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

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

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

然后重复这个过程

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

当然还有一个T₀ = 0的情况

写成公式就是

T_n = 0 ( n=0)

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

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

T_n=2ⁿ-1

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

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

先带入刚才T₀那个公式, T₀=2⁰-1 显然是对的结果是 0

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

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

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

所以T_n = 2*(T_n-1 )+1 = 2*(2^(n-1) -1) + 1 = 2ⁿ-1

所以n=100时, 你需要 2¹⁰⁰-1 = 1267650600228229401496703205375

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

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

print(countStep(100));

1267650600228229401496703205375