#! usr/bin/env python3
# -*- coding:utf-8 -*-

"""
递归算法分析
我们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法分析。
到目前为止，求解汉诺塔问题最简单的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，
我们说的简单点就是自己是一个方法或者说是函数，但是在自己这个函数里有调用自己这个函数的语句，而这个调用怎么才能调用结束呢？
这里还必须有一个结束点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，一直到第一次调用的这个函数能返回一个确定的值。

实现这个算法可以简单分为三个步骤：

把n-1个盘子由 A 移到 B；

把第n个盘子由 A 移到 C；

把n-1个盘子由 B 移到 C；

从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步：

中间的一步是把最大的一个盘子由A移到C上去；

中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，

中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；
"""

# 将n个盘子由A柱先移动到B柱，然后再移动到C柱
def move(n, a, b, c):

	#如果只有一个盘子时
	if n == 1:
		print(a, "----->", c)
	else:
		#将n-1个盘子由A柱移动到B柱
		move(n-1, a, c, b)

		#将第n个盘子由A柱移动到C柱
		move(1, a, b, c)

		#将n-1个盘子由B柱移动到C柱
		move(n-1, b, a, c)

n = int(input("请输入汉诺塔层数："))
#输入层数后，调用函数move()，让其开始执行
move(n, 'A', 'B', 'C')

"""
1. 将A柱上的n-1个盘子移动到B柱：move(n-1, a, c, b)
2. 将A柱上的第n个盘子（最大的一个）移动到C柱：move(1, a, b, c)
3. 将B柱上的n-1个盘子移动到C柱：move(n-1, b, a, c)

重复以上步骤，直到n=1时，print()

实际上，为何只有一个print()，但是最终结果是打印出了所有的路线？
原因是：move()函数不断的在内部调用自身，就会得到很多次n=1的状态，然后根据move()中的参数顺序打印出来（参数顺序不一定会是a,b,c）
"""