#!/usr/bin/env python
# 24 - 递归 汉诺塔
# Q1:
"""
汉诺塔原型
三个柱子，64块金片
思路：
1. 将x上的63个盘子借助Z移动到Y上
2. 将Y上的63个盘子借助X移动到Z上
问题1： 将x上的63个盘子借助Z移动到Y上。拆解为：
1. 将62个盘子从x移动到Z上
2. 将最底下的第63个盘子移动到y上
3. 将z上的62个盘子移动到Y上
问题2: 将Y上的63个盘子借助X移动到Z上，拆解为：
1. 将62个盘子从y移动到x上
2. 将最底下的第63个盘子移动到z上
3. 将z上的62个盘子移动到Y上
"""
def hanoi(n,x,y,z):
if n == 1:
print(x,'--->',z)
else:
hanoi(n-1,x,z,y)# 将前n-1个盘子从x移动到y上
print(x,'--->',z)#将最底下的最后一个盘子从x移动到x上
hanoi(n-1,y,x,z)#将y上的n-1个盘子移动到z上
n = int(input('请输入汉诺塔的层数: '))
hanoi(n,'x','y','z')
