经典汉诺塔游戏

香川群子

汉诺塔的数学分析：


我们先来讲故事：

汉诺塔（Hanoi塔）问题是印度的一个古老的传说。

在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。
印度教的主神梵天(开天辟地的神勃拉玛) 在创造世界的时候，
在其中一根针上从下到上地穿好了由大到小的64片金片，
最大的一个金片放在最底下，其余一个比一个小，依次叠加上去。
这就是所谓的汉诺塔。

不论白天黑夜，庙里总有一个僧侣在按照下面的法则移动这些金片：
1、可以把任何一根针上的金片移动到其它另外两根针中的一个针上去；
2、但一次只能移动最上面的那一片金片；
3、不管在哪根针上，小片必须放在大片上面。

……当所有的金片都从梵天穿好的那根针上（A针）移到第3根针(C针)上时，
世界就将在一声霹雳中消灭，梵塔、庙宇和众生都将同归于尽。

后来，这个传说就演变为汉诺塔游戏。

我们把金片的数量叫做阶，那么64个金片就叫做64阶汉诺塔。

经数学计算，64阶汉诺塔移动圆片的次数=2^64-1=18446744073709551615，
以每次移动耗时1秒来计算，大约需要5850亿年。
看来，即使到地球毁灭，众僧们也不可能完成金片的移动。


为了方便说明，我们将从3阶汉诺塔游戏开始说起。

liulang0808

嵌套吗，这个原来看着就 有点晕的

guzhen9315

坐下听“香川群子”讲课。

香川群子

归纳法证明：

首先，规定起始针叫做A、目标针叫做C、中间B针作为过渡。
设 函数 f(x)

1.
1阶汉诺塔只需要移动 1次
A → C 完成

即 f(1)=1


2.
2阶汉诺塔只需要移动 3次
金片1： A → B  (过渡)
金片2： A → C  (金片2到位)
金片1： B → C  (金片1从过渡B针到目标C针、完成)

即 f(2)=3


3.
3阶汉诺塔只需要移动 7次
金片1： A → C  (过渡)
金片2： A → B  (过渡)
金片1： C → B  (金片12到达过渡B针)

金片3： A → C  (金片3到位)
金片1： B → A  (过渡)
金片2： B → C  (金片2到位)

金片1： A → C  (全部完成)

即 f(3)=7


…………
下面证明，f(k+1)=f(k)*2+1

对于第k+1阶汉诺塔，有：
第一步骤，把A针上所有1-k的金片全部移动到过渡B针上去。
相当于把k阶汉诺塔，从A针开始，以C针为过渡，以B针为目标进行转移，
转移次数为已知的 f(k)次

第二步骤，直接把第k+1个金片从A针移动到目标C针，需要1步

第三步骤，把过渡B针上所有1-k的金片全部移动到目标C针上去。
相当于把k阶汉诺塔，从B针开始，以A针为过渡，以C针为目标进行转移，
转移次数为已知的 f(k)次

这样就完成了所有K+1个金片的转移。
总数 f(k+1)= f(k)+1+f(k)

即 f(k+1)=f(k)*2+1


那么，已知f(1)=1 （或者按照f(0)=0记忆亦可）
那么代入即可得到：
f(2)=1*2+1=3
f(3)=3*2+1+7
…………

[f(k+1)-1]/f(k)=2 存在2^n关系。

而f(1)=1 （或f(0)=0）
所以假设f(1)=2^1+c （或f(0)=2^0+c）时，c=-1

因此最后有：
f(K)=2^k-1

香川群子

这个游戏和我们熟知的九连环游戏一样，很多步骤都是简单重复的。

因此，引入递归概念以后，可以非常方便地得到游戏的每一个移动步骤解。


……
事实上，学习递归时，汉诺塔往往被作为最基本的一个递归练习题来介绍、学习。

香川群子

首先我们先来看一下这个例子：

用递归方法计算自然数的阶乘：

1. Sub test()
   
2.     MsgBox Fct(5)
   
3. End Sub
   
4. Function Fct(n)
   
5.     If n = 1 Then Fct = 1 Else Fct = Fct(n - 1) * n
   
6. End Function

复制代码

本来，如果使用For……Next循环，也可以轻松地计算出自然数的阶乘结果：
Function Fct2(n)
    s = 1
    For i = 1 To n
        s = s * i
    Next
    Fct2 = s
End Function

用递归计算阶乘，未必是一个好主意，但这个例子，却提供了理解递归算法思路的一个很好的切入点。

（有人不认为递归是一种算法……但大部分人认可递归可以作为算法归类，因为递归肯定不能当做是数据结构）

香川群子

回过头，继续通过解析阶乘的递归算法来 进一步介绍递归思路。

首先，递归必须是一种相同计算过程的重复。（即可归纳的算法）

例如，5的阶乘= 1*2*3*4*5  或者也可以理解为 = 5*4*3*2*1

那么，阶乘的数学计算必须是分步进行的，
借用变量s，我们观察结果如下：

s=1
s=s*2=1*2=2
s=s*3=2*3=6
s=s*4=6*4=24
s=s*5=24*5=120 结束。


总结一下上述过程，把上述过程倒过来看，就可以发现：
每一步的计算过程= s * n （n为当前序号）
到最后（第1行时）是 s=1 (n=1 时)


那么，上述相同的计算过程中的s，我们可以把它看作是一个递变变量s，
即每次的计算结果都会更新，且其计算结果依赖于下一次计算过程。（相同的计算过程）
直至计算至条件底部（n=1时），可以返回一个定值。（s=1）

然后，再把上述过程逐层退回（回归），就能得到最终计算结果。

这个一层一层把变量计算过程(s=s*n)传递下去，
到条件底部(s=1)时再逐层返回计算结果的计算方法，
就称之为 递归过程 （或称迭代递归过程）

具体如下：
s=s*5
s=(s*4)*5
s=((s*3)*4)*5
s=(((s*2)*3)*4)*5
s=(((1*2)*3)*4)*5
s=(((2)*3)*4)*5
s=((6)*4)*5
s=(24)*5
s=120

就是这样一个过程。

香川群子

递归算法的结构：

1. 一个封装为递归函数（Function）或递归过程（Sub）的代码过程
2. 该函数有参数（递归变量，例如 n）的传递，以及相同的处理过程（例如 s*n）
3. 进入下一递归过程以后计算中有变量的改变（递增、递减或其它变化）
4. 存在底部条件（即退出、返回条件，例如 n=1）
5. 最终递归结果是收敛的（可以逐层退出直至结束）


按照高手的概括性总结，还可以描述为：
1. 过程中存在入口和出口
2. 进行规则相同的过程计算
3. 可以收敛退出

只要满足这些条件，就是一个合格的递归过程了。

香川群子

下面我们回到汉诺塔问题：


但是，首先再次回顾一下阶乘的递归算法：
1. 参数 n
2. 递归过程计算规则：
    f(k) =f(k-1)*n
3. 底部条件 n=1 时 s=1

于是就有：
Function f(n)
   If n=1 Then
     f=1
   Else
     f=f(n-1)*n
   End If
End Function

……明白了吧。

那么，对于汉诺塔有：
1. 参数 n ，以及3根针的状态（源针A、过渡针B、目标针C）

2. 递归过程计算规则：
    f(k) =f(k-1) [1~n-1金片作为整体全部： A→B,C过渡]+[n金片： A-C直接]+f(k-1)[1~n-1金片作为整体全部：B→C,A过渡]

3. 底部条件 n=1 时 f(1)=1[A-C直接]

因此有：

1. 
   
2. 
   
3. 
   
4. Sub Hanoi()'汉诺塔解法过程
   
5.     Call dg_Hanoi2(5, "A", "C", "B") '以5阶塔为例计算，以"A"针起始，目标"C"针，以"B"针过渡
   
6. End Sub
   
7. 
   
8. Sub dg_Hanoi(n, a, c, b) '汉诺塔递归计算过程
   
9.      '参数为： n阶塔，以a针起始，目标c针，以b针过渡
   
10.     '需要注意的是：在递归过程中随着参数变化，
    
11.     '这时候的a针并非一定等于"A"针，同样b针/c针也并非一定是等于"B"针/"C"针
    
12. 
    
13. 
    
14.     If n = 1 Then
    
15.         Debug.Print "Move " & n & ": " & a & "→" & c
    
16.         '到n=1时为底部退出条件，并将第1个金片从a针移动到c针（不需要过渡）
    
17.         '需要注意的是：这时候的a针并非一定等于"A"针，同样c针也并非一定是等于"C"针
    
18. 
    
19.     Else
    
20.         Call dg_Hanoi(n - 1, a, b, c)
    
21.         '过程1： 模拟把全部n-1个金片，全部从a针移动到b针（c针过渡）
    
22.         '同样a针/b针/c针 并非一定是等于"A"针/"B"针/"C"针
    
23. 
    
24.         Debug.Print "Move " & n & ": " & a & "→" & c
    
25.         '过程2： 然后把第n个金片，直接从a针移动到目标c针（不需要过渡）
    
26.         '同样这里的a针/c针 并非一定是等于"A"针/"C"针
    
27.         
    
28.         Call dg_Hanoi(n - 1, b, c, a)
    
29.         '过程3： 然后模拟把全部n-1个金片，从过渡b针再移动到目标c针（以a针为过渡）
    
30.         '同样a针/b针/c针 并非一定是等于"A"针/"B"针/"C"针
    
31. 
    
32.     End If
    
33. End Sub

复制代码

…………
需要注意的是：
a、b、c 3个针参数，并非固定的（如果固定就不需要把参数作为变量传递了）
而是根据目前的状态而确定哪个针是源针、哪个针是目标针，哪个针是过渡针。


这一点，可能是很多人无法直接理解的原因吧。

香川群子

不加注释的话，代码看上去非常简洁：

1. Sub Hanoi2()
   
2.     Call dg_Hanoi2(5, "A", "C", "B")
   
3. End Sub
   
4. 
   
5. Sub dg_Hanoi2(n, a, c, b)
   
6.     If n = 1 Then
   
7.         Debug.Print "Move " & n & ": " & a & "→" & c
   
8.     Else
   
9.         Call dg_Hanoi2(n - 1, a, b, c)
   
10.         Debug.Print "Move " & n & ": " & a & "→" & c
    
11.         Call dg_Hanoi2(n - 1, b, c, a)
    
12.     End If
    
13. End Sub
    

复制代码