汉诺塔Hanoi

gzj137070928

# 汉诺塔问题:将在x柱上从小到大的n个圆盘按照从小到大的顺序移到z柱
# 递归思想：先将n-1个圆盘借助z，移到y上；再将最底下的一个个圆盘移到z上
# 最后将y上的n-1个圆盘移到z上

def hanoi(n, x, y, z):
    global count
    if n == 1:
        print(x, '-->', z)
        count += 1
    else:
        hanoi(n - 1, x, z, y)  # 将n-1个圆盘借助z，移到y上
        print(x, '-->', z)  # 将最底下的一个个圆盘移到z上
        count += 1
        hanoi(n - 1, y, x, z)  # 将y上的n-1个圆盘移到z上


count = 0
n = int(input('请输入汉诺塔的层数：'))
hanoi(n, 'x', 'y', 'z')
print('移动的总次数为：', count)