博客

不得不说，比起预想的真是出奇的简单(⊙ˍ⊙)，一个递推解决。

设目标柱为Z，盘子开始时全在X上，中间还有一根空的Y柱。当只有两个盘子时，要将小盘移到Y上，再将大盘移到Z上，再移动小盘到Z上。

以此类推，若有N个圆盘，就要先将上面N-1个先移到辅助柱（Y）上，将最下层盘子移到目标柱上，然后忽略已经移好的最大的盘子。此时辅助柱变为X，将上面N-2个盘子移动到X上，再将最下面的大盘移到目标柱上。

第一次看感觉难的一批，但其实只有辅助柱为X/Y两种情况。

count = 0    # 计步器
def hanoi(n, x, y, z):
    global count                  # 全局变量
    if n == 1:
        count += 1
        print(x, '-->', z)         # x指盘子所在的柱子，不一定是X
    else:
        hanoi(n - 1, x, z, y)     # 上面n-1个盘子从X移到Y，Z为辅助柱
        count += 1
        print(x, '-->', z)         # x指盘子所在的柱子，不一定是X
        hanoi(n - 1, y, x, z)     # 最大的盘子移到Z后，将Y上的盘子移到Z上
hanoi(int(input('输入汉诺塔层数：')), 'X', 'Y', 'Z')
print('总步数为：', count)

也可去掉计数器，移动次数为2^(层数)-1。