汉诺塔..
本节通过学习汉诺塔这个经典的问题来更加熟练运用递归算法.
问题描述:
圆盘按从大到小的顺序依次排在石柱上,在三根柱子间一次只能移动一个圆盘,如何将全部圆盘从第一根柱子移动到第三根
思路解析:
先从简易问题入手,当a柱上有n个圆盘时,先将第n-1个圆盘当作一个整体,移动到中转石柱b上,再将最大的圆盘移动到石柱c上,最后将石柱b上的n-1个圆盘移动到目标柱c即可完成.那么递归的终止条件就是,当要移动的圆盘个数为1时,只需输出将圆盘从石柱a移动到目标石柱即可.变量如下:
a变量:表示圆盘最初所在的石柱a
b变量:表示中转石柱b
c变量:表示目标石柱c
n变量:表示将n个圆盘从a经过b移动到c
time变量:表示第几步
代码如下:
count=0#计数工具
def hanoi(n,x,y,z):#把n个圆盘从x借助y移动到z上
if n==1:
global count
count +=1
print(count,' : ',x,'-->',z)
else:
#把n-1个盘子由x借助z移动到y
hanoi(n-1,x,z,y)
#把第n个盘子由x移动到z
count += 1
print(count,' : ',x,'-->',z)
#把n-1个盘子由y借助x移动到z
hanoi(n-1,y,x,z)
n=int(input("请输入圆盘个数:"))
hanoi(n,'tower1','tower2','tower3')