Python实现汉诺塔_汉诺塔python

汉诺塔介绍

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

我查了一些资料，移完这些金片需要5845.42亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.42亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

​

 废话不多说，直接上代码

这里我们只要知道汉诺塔实现的原理就行，我们选择输入三层进行介绍，更多的层数原理都是一样的。A表示的是左边第一根柱子B表示中间的柱子C表示右边的柱子

def Hanoi(n,x,y,z):
	if n == 1:
		print(x,'-->',z) # 如果只有一层，直接将圆盘从 x 移动到 z
	else:
		Hanoi(n-1,x,z,y) # 将 x 上的 n-1 个圆盘移动到 y
		print(x,'-->',z) # 将最底下的圆盘从 x 移动到 z
		Hanoi(n-1,y,x,z) # 将 y 上的 n-1 个圆盘移动到 z
n = int(input("请输入汉诺塔的层数："))
Hanoi(n,'A','B','C')	

注意 要分清楚形参和实参，变来变去的是实参，也就是我们刚开始传入的'A' , 'B' , 'C'三个值，他们通过形式参数 'x' , 'y' ,'z' 来进行传递。

当我们输入 n = 3 时，程序运行结果如下：

具体步骤如下：

我们开始一行一行的分析代码运行过程
当 n = 3 的时候

因为 n=3 不等于1，所以程序会执行第一次递归中else下面的代码块,具体来说是第一行代码Hanoi(n-1,x,z,y) 

#当n=3时，不满足if的条件所要执行的代码
Hanoi(n-1,x,z,y) 
print(x,'-->',z) 
Hanoi(n-1,y,x,z) 

因为采用了递归，函数自己调用了自己，所以我们会从头开始执行 再次经过 if 语句

   

print(x,'-->',z)                               注意！这里和表格③的变化是根据表格①来的

        

此时的n=2，不等于1所以程序会进行第二次调用，继续执行else下面的代码块也是第一行代码Hanoi(n-1,x,z,y) 

#当n=2时，不满足if的条件所要执行的代码
Hanoi(n-1,x,z,y)
print(x,'-->',z)
Hanoi(n-1,y,x,z)

print(x,'-->',z)                                注意！这里和表格⑤的变化是根据表格②来的

因为此时 n = 1，所以会运行if语句下面的代码

第一步（表格④  第二次调用的Hanoi(n-1,x,z,y)）

程序继续往下运行

第二步（这里的变换是第二次调用时的代码print(x,'-->',z)）

第三步（表格⑤  第二次调用的Hanoi(n-1,y,x,z)）

此时代码已经将

第一次调用的代码 Hanoi(n-1,x,z,y)执行完毕，会接着执行第一次调用的print(x,'-->',z)

第四步（这里的变换是第一次调用时的代码print(x,'-->',z)）

随后程序来到第一次调用时else语句下面的第三行代码Hanoi(n-1,y,x,z)

这里的n=2，不能通过if语句，我们来到第三次调用

#第一次调用时的第三行代码，这是n=2时不满足if的条件所要执行的代码
Hanoi(n-1,x,z,y)
print(x,'-->',z)
Hanoi(n-1,y,x,z)

此时

print(x,'-->',z)                                       注意！这里和表格⑦的变化是根据表格③来的

       

此时 n=1

第五步（表格⑥  第三次调用的Hanoi(n-1,x,z,y)）

第六步（这里的变换是第三次调用时的代码print(x,'-->',z)）

第七步（表格⑦  第三次调用的Hanoi(n-1,y,x,z)）

全部过程如下

递归的含义是等到最底层的代码执行完毕，一层一层的往上面返回，要明白代码的具体执行过程。