汉诺塔问题深度剖析（python实现）

当我们学习一门编程语言的时候，都会遇到递归函数这个问题。而学习递归的一个经典案例就是汉诺塔问题。通过这篇文章，观察移动三个盘子和四个盘子的详细过程，您不仅可以深刻的了解递归，也更加熟悉了汉诺塔的游戏的玩法。

规则

有a、b、c三个柱子，a从上到下，从小到大有n个盘子。要求把a上所有盘子移动到c，一次只能移动一个盘子，且大盘子不能放小盘子上。

方法

1. 当a上有一个盘子时，直接把该盘子移动到c。
2. 当a上有n个盘子时(n > 1)：

   先把a上n-1个盘子移动到b，

   再把a上最后一个盘子移动到c，

   再把b上所有盘子移动到c。

代码实现

def mov(n,a,b,c):
	if n == 1:
		# 如果a上只有一个盘子，直接把a移动到c
		print(a,'-->',c)
	else:
		# 先把a上的n-1个盘子移动到b
		mov(n-1,a,c,b)
		# 再把a上最后一个盘子移动到c
		mov(1,a,b,c)
		# 最后把b上所有盘子(n-1个)移动到c
		mov(n-1,b,a,c)

num = abs(int(input('一共有几个盘子：')))
print('\n移动步骤为：')
mov(num,'A','B','C')

3个盘子的实例

1. 先把a上的2个移动到b

   先把a上的1个移动到c

   再把a上 最后 1个移动到b

   再把c上 仅有的 一个移动到b

2. 再把a上 最后 一个移动到c
3. 再把b上的两个移动到c

   先把b上的一个移动到a

   再把b上 最后 一个移动到c

   再把a上 仅有的 一个移动到c

也就是：

A –> C A –> B C –> B A –> C B –> A B –> C A –> C 

4个盘子的实例

1. 先把a上的三个移动到b（套用上面三个盘子的情况，只不过之前是移动到c，现在是b）

   先把a上的2个移动到c

   先把a上的1个移动到b

   再把a上 最后 1个移动到c

   再把b上 仅有的 一个移动到c

   再把a上 最后 一个移动到b

   再把c上的两个移动到b

   先把c上的一个移动到a

   再把c上 最后 一个移动到b

   再把a上 仅有的 一个移动到b

2. 再把a上 最后 一个移动到c
3. 再把b上的3个移动到c（还是第一步的思路，只是换了个柱子）

   先把b上的2个移动到a

   先把b上的1个移动到c

   再把b上 最后 1个移动到a

   再把c上 仅有的 一个移动到a

   再把b上 最后 一个移动到c

   再把a上的两个移动到c

   先把a上的一个移动到b

   再把a上 最后 一个移动到c

   再把b上 仅有的 一个移动到c

   也就是：

   A –> B

   A –> C

   B –> C

   A –> B

   C –> A

   C –> B

   A –> B

   A –> C

   B –> C

   B –> A

   C –> A

   B –> C

   A –> B

   A –> C

   B –> C

这样就清晰的看出移动的各个步骤。

总结

再反过来分析一下，当移动一个盘子的时候只需一步就能完成，对应于代码中的

if n == 1:
	# 如果a上只有一个盘子，直接把a移动到c
	print(a,'-->',c)

当移动两个盘子的时候，得需要三步才能完成。例如：把a上的两个盘子移动到c

1. 先把a上的1个移动到b
2. 再把a上 最后 1个移动到c
3. 再把b上 仅有的 一个移动到c

当移动三个盘子的时候，就可以分解成先移动两个盘子，再移动一个盘子。

当移动四个盘子的时候，就可以分解为先移动三个盘子，再移动一个盘子。依次类推。。

可见当移动两个或两个以上个数盘子的时候，都只需要三步就可以完成。其中每一步又可以分解为三步，直到只剩下一个盘子的情况。对应于代码中的

else:
   	# 先把a上的n-1个盘子移动到b
	mov(n-1,a,c,b)
	# 再把a上最后一个盘子移动到c
	mov(1,a,b,c)
	# 最后把b上所有盘子(n-1个)移动到c
	mov(n-1,b,a,c)

所以，汉诺塔问题，你了解了吗？

参考： python下实现汉诺塔

本文作者：小friend

本文链接：http://www.hellomao.top/2019/05/14/daily_hannuota/

版权声明：本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！