汉诺塔的递归算法

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟

一、 起源

  传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是卢卡斯自创的这个传说，还是他受他人启发。

二、 移动规则

20241217_r6H7Rh

  1.每次只能移动一个盘子；

  2.大盘不能放在小盘上面；

  3.在三根柱子之间一次只能移动一个盘子。

三、 问题抽象

  我们要利用抽象思维去思考汉诺塔这个问题，把 A 柱上的盘子看成两份，就是上面的盘子（可能是一个或者多个）和最底下的盘子，不需要关心上面的盘子到底有几个，每次操作就是把最底下的盘子通过缓冲区 B 柱移动到 C 柱。

  举例：从左到右有 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 n 个圆盘，现要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

  • n == 1 ( sum = 1 次 )

    • 第1次 1号盘 A ----> C

  • n == 2 ( sum = 3 次 )

    • 第1次 1号盘 A ----> B
    • 第2次 2号盘 A ----> C
    • 第3次 1号盘 B ----> C

  • n == 3 ( sum = 7 次 )

    • 第1次 1号盘 A ----> C
    • 第2次 2号盘 A ----> B
    • 第3次 1号盘 C ----> B
    • 第4次 3号盘 A ----> C
    • 第5次 1号盘 B ----> A
    • 第6次 2号盘 B ----> C
    • 第7次 1号盘 A ----> C

规律如下：
  1个圆盘的次数 2的1次方减1
  2个圆盘的次数 2的2次方减1
  3个圆盘的次数 2的3次方减1
  …………………………
  n个圆盘移动次数为：2^n - 1

四、 算法分析（递归算法）

  到目前为止，求解汉诺塔问题最简单的算法还是通过递归方式，递归简单而言就是某个方法或函数，但是在这个函数里有调用自己这个函数的语句，在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值，也就是最初需要有一个确定的值作为递归结束的条件。

  实现这个算法可以简单分为三个步骤：
    1. 把n-1个盘子由 A 移到 B；
    2. 把第n个盘子由 A 移到 C；
    3. 把n-1个盘子由 B 移到 C；

五、 代码实现

1
2
3
4
5
6
7
def hanoi(n, a, b, c):
    if n == 1:
        print(f"Move disk 1 from {a} to {c}")
        return
    hanoi(n-1, a, c, b)
    print(f"Move disk {n} from {a} to {c}")
    hanoi(n-1, b, a, c)
1
hanoi(3, 'A', 'B', 'C')

输出结果：

1
2
3
4
5
6
7
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

代码中的移动流程解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
  3个盘子的汉诺塔全部通过代码演示，按缩进原则，每一个缩进即进一个递归函数，每打印一次即中止当前递归,也就是每个print
说明:
    1.n = 3, n = 2, n = 1是每次执行if(n == 1)的结果，这里就不写判断了，相信大家也能看懂，也就是n不等与1时就减1进入递归
    2.请注意a,b,c柱每次进入函数的顺序，不要被形参带错路了，看准每次函数参数的实参 
**/

move(3, "a", "b", "c")
n=3:
    //开始从a上移动n-1即2个盘子通过c移动到b,以腾出c供a最后一个盘子移动
    move(2, "a","c","b")
    n=2:
    //开始进行n=2的一个递归，把当前a('a')柱上的n-1个盘子通过c('b'）移动到b('c')
        move(1, "a", "b", "c")
        n=1:
        //n=2的第一个递归完成,打印结果，执行当前子函数剩余代码
            print("a", "->", "c") 
        move(1, "a", "c", "b")
        n=1:
            print("a", "->", "b")
        move(1, "c", "a", "b")
        n=1:
            print("c", "->", "b")
    　   //到这里完成了a柱上面的n-1即是2个盘子的移动
        //开始把a柱上最后一个盘子移动到c柱上
        move(1, "a", "b", "c")
        n=1:
            print("a", "->", "c")
    //到这里完成移动a柱上的最后一个盘子到c柱上 
move(2, "b", "a", "c")
n=2:
//开始进行n=2的第二个递归,即把当前b('b')的盘子(n-1个)通过a('a')移动到c('c')上
    move(1, "b", "c", "a")
    n=1:
    //n=2 的第二个递归完成，打印结果并执行当前子函数的剩余代码
        print("b", "->", "a")
    move(1, "b", "a", "c")
    n=1:
        print("b", "->", "c")
    move(1, "a", "b", "c")
    n=1:
        print("a", "->", "c")
        //到这里把b上的盘子通过a移动到c,
//整个代码执行完毕,汉诺塔移动完成

六、 总结

  在学习 python 的时候看到这个汉诺塔问题，被其简洁优雅的代码所震撼，利用递归的方式简单的解决，也让我有了更深入了解算法魅力的想法，感觉算法本质上是在利用数学抽象的方法解决问题，问题就像山顶的旗帜，不同的算法通过不同的路径爬山，有的快有的慢（时间复杂度），有的简单有的复杂（空间复杂度），但是都能到达山顶，这就是算法的魅力所在。

七、 参考资料