OLD SCHOOL游戏-汉诺塔是怎么运行的？

公号许久未更新

最近在学习过程中遇到一点小问题，遂研究了下里面的道道

然后分享出来，当然看这篇文章的人少之又少

但我还是要写

为什么

因为头铁

言归正传，关于Python的递归函数，而汉诺塔游戏正是利用了递归函数的原理。自己重新整理了一下里面的内容，重新学习之后真是恍然大悟，现在在反思自己遗漏的基础内容。

说一点前序，在函数内部，可以调用其他函数。如果一个函数在内部调用自己本身，这个函数就是递归函数。

举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * ... * n，

用函数 fact(n)表示，可以看出：

fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n

= (n-1)! * n = fact(n-1) * n

所以，fact(n)可以表示为 n * fact(n-1)，只有n=1时需要特殊处理。

于是，fact(n)用递归的方式写出来就是：

def fact(n):

if n==1:

return 1

return n * fact(n - 1)

那我们来用这个原理来尝试去解决汉诺塔的问题。

这个游戏相比大家都玩过， 一款OLD SCHOOL益智游戏，但是它的游戏原理是什么？又是怎样去实现的呢？

图片取自知乎酱紫君

要实现此功能只需三步：

把 n-1 号盘子移动到缓冲区

把1号从起点移到终点

然后把缓冲区的n-1号盘子也移到终点

通俗易懂点解释来说就是怎么把大象装进冰箱？

把冰箱门打开

把大象装进去

把门关上

两个问题的思路都是一样的，关于运行过程我做了一个思维图，作为过程的解答：

def move(n,a,b,c):

if n == 1:

print(a,'->',c)

else:

move(n-1,a,c,b)

move(1,a,b,c)

move(n-1,b,a,c)

move(3,'A','B','C')

n=3

执行else语句

move(2,A,C,B)

n=2

执行else语句

move(1,A,B,C)A->C

move(1,A,C,B)A->B

move(1,C,A,B)C->B

move(1,A,B,C)

move(2,B,A,C)

n=2

执行else语句

move(1,B,C,A) B->A

move(1,B,A,C) B->C

move(1,A,B,C) A->C

IT'S OVER.

LOVE&PEACE.