问题简介

汉诺塔问题是算法经典问题，一般使用分治的思想来求解这个问题。

汉诺塔问题由三根柱子（起始柱、目标柱、辅助柱）和n个圆盘组成。开始时，在起始柱上有n个圆盘，这些圆盘自下而上，由大到小地放置在一起。各圆盘从小到大编号为1,2,…,n。要求将起始柱上的这些圆盘移动到目标柱上，并仍然按照同样的顺序放置。在移动圆盘时要遵守以下移动规则：

• 规则1：每次只能移动1个圆盘；
• 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
• 规则3：在满足移动规则1和2的前提下，可将圆盘移至起始柱、目标柱、辅助柱中任一柱子上。

求解思想

当n=1时，是最简单的，这1个圆盘直接从起始柱移动到目标柱。

当n=2时，1号圆盘需要先从起始柱移动到辅助柱，然后2号圆盘可以从起始柱移动到目标柱上，最后1号圆盘再从辅助柱移动到目标柱。

以此类推……

代码实现 Python 3

当有了求解的思想了以后，代码实现还是比较简单的。

def hanoi(n, a, b, c):
    """
    求解汉诺塔问题。
    例如，当n=3时，盘子的移动过程如下：
    盘子1从a移动到b
    盘子2从a移动到c
    盘子1从b移动到c
    盘子3从a移动到b
    盘子1从c移动到a
    盘子2从c移动到b
    盘子1从a移动到b
    :param n: 盘子的数量
    :param a: a柱的名称
    :param b: b柱的名称
    :param c: c柱的名称
    """
    if n == 1:
        print(f'盘子{n}从{a}移动到{b}')
    else:
        hanoi(n-1, a, c, b)
        print(f'盘子{n}从{a}移动到{b}')
        hanoi(n-1, c, b, a)