汉诺塔问题

算法

汉诺塔是一个经典的递归问题,有三根柱子和一系列从大到小叠放的圆盘。目标是将所有圆盘从一根柱子移动到另一根柱子,同时遵循规则:一次只能移动一个圆盘,且不能将大圆盘放在小圆盘上面。

时间复杂度:最佳 O(2^n) | 平均 O(2^n) | 最差 O(2^n)
空间复杂度:O(n)

应用场景/前提条件

  • 递归思想
  • 分治策略

算法讲解

汉诺塔问题

介绍

汉诺塔(Tower of Hanoi)是一个源于印度的古老数学智力游戏。这个问题的核心是将一组按照大小顺序叠放的圆盘从一根柱子移动到另一根柱子,过程中必须遵循特定规则。汉诺塔问题是递归算法的经典应用,也是计算机科学中讲解递归思想的标准案例之一。

这个问题背后隐藏着数学原理,最优解的移动次数是2^n-1(n为圆盘数量),呈指数级增长,所以也常被用来解释为什么某些问题在规模增长时处理难度陡增。

算法步骤

汉诺塔问题的规则如下:

  1. 有三根柱子(通常称为A、B、C),开始时所有圆盘都按照从大到小的顺序叠放在A柱上
  2. 每次只能移动一个圆盘,且只能移动最顶端的圆盘
  3. 任何时刻都不能将大圆盘放在小圆盘上面
  4. 目标是将所有圆盘从A柱按照原有顺序移动到C柱

递归解决汉诺塔问题的思路:

  1. 基准情况:当n=1时,直接将圆盘从源柱(A)移动到目标柱(C)
  2. 递归情况:当n>1时
    • 将n-1个圆盘从源柱(A)移动到辅助柱(B),此时可将目标柱(C)作为辅助
    • 将最大的圆盘(第n个)从源柱(A)移动到目标柱(C)

...