0 背景

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

不管这个传说的可信度有多大，如果考虑一下把 64 片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢？这里需要递归的方法。假设有 n 片，移动次数是 f(n)。显然 f(1)=1,f(2)=3,f(3)=7，且 f(k+1)=2*f(k)+1，此后不难证明 f(n)=2^n-1。假如每秒钟移动 1 次金片，当 n=64 时，移完这些金片需要 5845.42 亿年以上，而地球存在至今不过 45 亿年，太阳系的预期寿命据说也就是数百亿年。真的过了 5845.42 亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

汉诺塔 | 百度百科

1 源码

  • Python 汉诺塔源码（无注释）
  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Wed Oct 16 13:01:11 2019
  5. @author: yangzyu
  6. """
  7. def hanoi(n, a, b, c):
  8.     if n == 1:
  9.         print(a, '-->', c)
  10.     else:
  11.         hanoi(n-1, a, c, b)
  12.         print(a, '-->', c)
  13.         hanoi(n-1, b, a, c)
  15. n = input()
  16. hanoi(n, 'a', 'b', 'c')

2 理解

下面我们来逐步分析汉诺塔问题的求解步骤：

想象有三根无限等长的圆柱（代替传说中的金针），分别记为 A、B、C 柱。我们的目标是通过在三根柱子上来回移动圆盘，从而将 A 柱上所有的大小不一的圆盘（代替传说中的金片）全部移动到 C 柱上，并始终保持圆盘上小下大的顺序，这里我们使用 n 来表示 A 柱上最初有的圆盘数量。

汉诺塔问题是一个经典的递归问题，一个递归过程必须有递归基例和结束递归的条件。

首先，当 n = 1 时，即仅有 A 柱有 1 个圆盘时： 我们只需要将 A 柱上的圆盘移动到 C 柱上即可完成任务，我们用下面这条语句来表示这个过程。这就是我们的递归基例，下一步我们需要找到结束递归的条件。

  1. # 当n为1时
  2. print(a, '-->', c)  # 将 A 柱上的圆盘移动到 C 柱

接着，考虑 n = 2 的情况，此时 A 柱上从上到下有一小一大两个圆盘，我们需要先将 A 柱上的小圆盘移动到 B 柱，然后 A 柱就回到了n 为 1 的情况了，我们只需要和之前一样，将 A 柱上的大圆盘移动到 C 柱上，然后再将 B 柱上的小圆盘移动到已经有一个大圆盘的 C 柱上即可，移动的过程如下：

  1. # 当n为2时
  2. a -> b  # 将 A 柱上的小圆盘移动到 B 柱
  3. a -> c  # 将 A 柱上的大圆盘移动到 C 柱
  4. b -> c  # 将 B 柱上的小圆盘移动到已经有一个大圆盘的 C 柱

下面，我们来思考 n = 3 的情况，这个时候 A 柱上从上到下有小中大三个圆盘，本次移动过程如下：

  1. # 当n为3时
  2. a --> c
  3. a --> b
  4. c --> b
  5. a --> c
  6. b --> a
  7. b --> c
  8. a --> c

可以发现，当 n = 3 时，步骤已经比较多了，但还是可以用大脑（或手和笔）去跟踪函数运行每一步的执行过程。然而，当 n 更大时呢？比如 n = 5 时:

  1. # 当n为5时
  2. a --> c
  3. a --> b
  4. c --> b
  5. a --> c
  6. b --> a
  7. b --> c
  8. a --> c
  9. a --> b
  10. c --> b
  11. c --> a
  12. b --> a
  13. c --> b
  14. a --> c
  15. a --> b
  16. c --> b
  17. a --> c
  18. b --> a
  19. b --> c
  20. a --> c
  21. b --> a
  22. c --> b
  23. c --> a
  24. b --> a
  25. b --> c
  26. a --> c
  27. a --> b
  28. c --> b
  29. a --> c
  30. b --> a
  31. b --> c
  32. a --> c

此时，如果我们继续用大脑（或手和笔）去跟踪函数运行每一步的执行，我们很难保证一步不错地跟下来。而理解汉诺塔（递归问题）的关键就在于放弃用大脑（或手和笔）去跟踪函数每一步的执行过程的习惯，转而利用抽象和自动化的思想解决问题。

以 n = 3 为例，此时 A 柱上从上到下共有有小中大三个圆盘。这里我们首先将 A 柱上的小盘和中盘视作一个整体，我们现在所需要的是将这个整体借助 C 柱，移动到 B 柱上；接着，将 A 柱上的最底层的大圆盘一步到位移动到 C 柱上；最后，借助 A 柱将 B 柱上的两个圆盘分布移动到 C 柱。

事实上，我们可以将 A 柱最底层的圆盘之上的 n-1 个圆盘抽象为一个整体，借助 C 柱将其转移到 B 柱上；接着，我们便可以将 A 柱最底层的圆盘直接移动到 C 柱；然后，对于此时 B 柱上的 n-1 个圆盘，我们又可以将最底层的圆盘以上的 n-2 个圆盘抽象为一个整体，借助 C 柱将其移动到 A 柱；随后，将最底层的圆盘从 B 柱移动的 C 柱上，完成这一轮操作后，我们继续对 A 柱上的剩余的 n-2 个圆盘重复类似的操作。

顺着这个思路，可以推出：我们总有办法将初始柱（最开始是 A 柱）上的 n-1 个圆盘作为一个整体，借助目的柱（最开始是 C 柱）而移动到中间柱（最开始是 B 柱）上，进而我们就回到了最简单的 n 为 1 的情况。 将这些步骤转化为程序语句，就可以得到以下的代码（含注释）：

  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Wed Oct 16 13:01:11 2019
  5. @author: yangzyu
  6. """
  7. def hanoi(n, a, b, c):
  9.     # 当n为1时 (递归基础)
  10.     if n == 1:
  11.         print(a, '-->', c) # 将A柱最底层的圆盘移动到C柱
  13.     # 当n大于1时
  14.     else:
  15.         hanoi(n-1, a, c, b) # 借助C柱，将n-1个圆盘从A柱移动到B柱
  16.         print(a, '-->', c) # 将A柱最底层的圆盘移动到C柱
  17.         hanoi(n-1, b, a, c) # 借助A柱，将n-1个圆盘从B柱移动到C柱
  19. #调用hanoi函数，这里设置了n为5的情况
  20. hanoi(5, 'a', 'b', 'c')

大功告成！