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

更好的阅读体验可访问这里。

规则

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

方法

当a上有一个盘子时，直接把该盘子移动到c。
当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个盘子的实例

先把a上的2个移动到b

先把a上的1个移动到c

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

再把c上仅有的一个移动到b
再把a上最后一个移动到c
再把b上的两个移动到c

先把b上的一个移动到a

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

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

也就是：

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

4个盘子的实例

先把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
再把a上最后一个移动到c
再把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

先把a上的1个移动到b
再把a上最后1个移动到c
再把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下实现汉诺塔

巴特西

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

规则

方法

代码实现

3个盘子的实例

4个盘子的实例

总结

最新文章

热门文章