Python实现汉诺塔（详细解释）_汉诺塔python

1、背景

神话故事，具体的故事太长，就不扯了，简单讲就是关于一场游戏玩到世界毁灭的故事。

游戏规则：

有N个从上到下依次增大的圆盘，共有三个柱子，A，B，C，起初所有的盘子都在A上，将所有的盘子从A移动到C，这个过程中，必须保持大盘子在下，小盘子在上的原则。

如下是这个游戏的动画演示（小程序地址：汉诺塔游戏）。

 2、规则拆解

想要将A上的盘子都按照规则，移动到C，那么离不开如下的步骤

1）将最下面的盘子之上的N-1个盘子从A柱借助C柱移动到B柱。

2）再将最后一个盘子从A柱移动到C柱。

3）最后将B柱上面的N-1个盘子借助A柱移动到C柱。

这个时候肯定有些童鞋会问了，第二个盘子并没有经过A柱才移动到C柱的呀，注意，前面描述的是借助A柱移动到C柱，并不是必须每个盘子都要再经历从B柱到A柱再到C柱，实际上是当N-2个盘子都已经移动到A柱，B柱上面再无阻碍，那么剩下的一个盘子会直接移动到目标柱子上（注意这里不要混了要分清楚不同阶段，目标柱子是谁），所以我这里讲的是‘借助’。为了这个过程更加清晰明了，下面演示下四个盘子的移动方式。

 3、代码编写

理解了上述逻辑之后，采用python实现，需要用到函数的递归，如上所说，虽然有三根柱子，但是三根柱子的运动逻辑是肯定的，即：当自己身上只有一个盘子，而且自己之上的小盘子不在目标柱子上的时候，直接将自己这个盘子移动到目标盘子。在代码编写的时候要注意，递归容易迷糊很多时候是自己没有理清楚递归的规则，以及什么时候结束递归。

而对于Python而言，Python就像是人的思考一样，写代码可以将自己的思考转化为代码，逻辑要能够一一对应的上。

def hanoi_game(N, A, B, C):
    """
    汉诺塔游戏过程展示。
    :param N: 起始柱子上总共有几个盘子
    :param A: 起始柱子
    :param B: 需要借助的柱子
    :param C: 目的柱子
    :return:
    """
    if N == 1:  # 如果起始柱子上只有一个盘子，那么直接移动到目的盘子
        print(f'{A}移动到{C}')
    else:
        hanoi_game(N - 1, A, C, B)  # 如果盘子大于一个，那么需要将剩下的N-1个盘子，先借助C，移动到B 传入参数跟着思路变
        print(f'{A}移动到{C}')  # 将剩下的那一个盘子，从A移动到C
        hanoi_game(N - 1, B, A, C)  # 将在B上的N-1个盘子，借助A，移动到C 传输参数跟着思路变
 
 
hanoi_game(3, 'A', 'B', 'C')

可以看到python的代码就是将我们上述的思路一对一的转换成了代码。如下是N=3的情况下代码运行的结果：

 希望上述理解能够对学习递归的你有所帮助。