汉诺塔也是经典的算法问题

文章目录

1 汉诺塔问题

法国数学家卢卡斯（Edouard Lucas）在1883年提出了一个数学游戏：

  • 传说在世界中心贝拿勒斯（印度北部）的圣庙里，一块黄铜板上有三根宝石柱。印度教的主神大梵天在创造世界的时候，在其中一根柱上从下到上地穿好了由大到小的64片金盘。大梵天命令僧侣们将圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定， 在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。预言说当这些盘子移动完毕时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

考虑该问题的一般形式：有 n 个圆盘，最初自下而上、自大而小地穿在A柱上， 每次按规则（上述）移动一个圆盘，最终将所有圆盘移动到C柱上。

假如现在有如下图的盘子：

则一共需要移动7次。自己手动画画就知道了。

那么现在盘子有n个，如下图：


该如何移动？实际上这是递归的问题（递归在后面的学习中会学到）

  • 先将A柱上所有其他盘子移到B柱上（这是一个类似于自己的子问题），只留下最下面的盘子，也就是n盘子
  • 接着将最大的盘子从A柱移到C柱，之后不必再管它。
  • 最后再将刚才移到B柱上的盘子移到C柱上（这又是一个子问题） 。

用 T(n) 表示移动 n 个圆盘所需要的步数

根据算法

  1. 先把前面 n-1 个盘子转移到B上；
  2. 然后把第 n 个盘子转到C上（n这个盘子移动了一次）；
  3. 最后再次将B上的 n-1 个盘子转移到C上（这n-1个盘子移动了两次）
  • 得到递推关系 T(n)=2T(n-1)+1

这个公式，足以使用递归的形式写出代码。下面还可以直接求出具体的值：

使用倒推法求解T(n)=2T(n-1)+1, T(1)=1:

回到最初的汉诺塔问题， 要将64片金盘重新摆放在另一根柱子上， 最少需要 264-1 步， 即使僧侣每秒钟移动一步而且每次移动都是正确的方法， 那么也需要 5.8*1011 年， 即5千多亿年！