汉诺塔问题

问题描述：有三根杆子A，B，C。A杆上有n个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

（1）每次只能移动一个圆盘；

（2）大盘不能叠在小盘上面。

可以将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

解题分析

情况①：A上只有1个盘子的情况，直接将A上的盘子从A移动到C即可。

情况②：A上有2个盘子的情况，将盘子自底向上依次编号为1，2号。移动过程如下：

step 1：将1号盘子从A杆移动到B杆。
step 2：将2号盘子从A杆移动到C杆。
step 3：将1号盘子从B杆移动到C杆。

情况③：A上有三个盘子的情况，将盘子自底向上依次编号为1，2，3号，移动过程如下：

step 1：将1号盘子从A杆移动到B杆。
step 2：将2号盘子从A杆移动到C杆。
step 3：将1号盘子从C杆移动到B杆。
step 1：将3号盘子从A杆移动到C杆。
step 2：将1号盘子从B杆移动到A杆。
step 3：将2号盘子从B杆移动到C杆。
step 1：将1号盘子从A杆移动到C杆。

从上面的情况可以观察到，n个盘子从A杆移动到C杆可以分解为如下三个步骤：

step 1：将n-1通过C杆，从A杆移动到B杆。
step 2：将第n个盘子从A杆移动到C杆。
step 3：将B杆上的n-1个盘子，通过A杆移动到C杆。

总的移动次数为上述三步的移动次数之和， 即：完成step1需要的移动次数 H(n-1) + 移动第n个盘子的1次 + 完成step3需要的移动次数 H(n-1)

即 H(n) = H(n-1) + 1 + H(n-1)

python实现代码如下：

def move(n, a, c):
    print("move {} from {} to {}". format(n, a, c))


def f(n, A, B, C):
    if n == 0:
        return  # 已经结束，直接返回
    else:
        f(n-1, A, C, B)  # 将n-1个盘子通过c，从a移动到b
        move(n, A, C)  # 将第n个盘子从a移动到c上
        f(n-1, B, A, C)  # 将b上的n-1个盘子通过a，移动到c上


f(3, "a", "b", "c")

输出结果

move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c