Python中如何利用递归解决汉诺塔问题

简单来讲，汉诺塔问题是这样的：

​ 给定三根柱子，记为 ABC ，其中 A 柱子上有 n个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A柱上的盘子经由 C柱移动到 B柱最少需要多少次？

​ 移动时应注意：① 一次只能移动一个盘子

​ ②大的盘子不能压在小盘子上

解决汉诺塔问题，重点是递归方法（思路）与“柱子”之间的转换（编程）

先放代码

count = #count统计步数用

def hanoi(n, A, B, C）:#（第n个，出发地，目的地，中间站/工具人）    

    global count    

    if n == 1 :      

        print("{}:{}->{}".format(1,A,B)        

        count += 1    

    else :         

        hanoi(n-1, A, C, B) #第一步

        print("{}:{}->{}".format(n,A,B)) #第二步       

        count += 1   #第二步     

        hanoi(n-1, C, B, A)#第三步

hanoi(3, "A", "B", "C")

print(count)

一   

首先是递归：假设有n个盘子，n>=2，将最下面的盘子和其他盘子看成两部分，可以得知需要三步：

1 上面盘子（视作整体），转移到C柱

2 最下面盘子，转移到B柱

3 将C柱上的盘子通过A柱转移到B柱上

也就是———转移n个盘子

首先，把n-1个盘子转移到C柱

然后，再移动第n个盘子（最下面）到B柱

最后，再把n-1个盘子一道C柱

如下图，不断的套娃，直到n=2为止（n=1就不能再套娃力）

二

思路是有了，但到了编写代码的时候有要怎么做呢

要怎么样才能表达出步骤呢

首先，如果只有一个盘子

那肯定是1 A->B

如果有两个盘子

则是1 A->C   2 A->B  1 C->B

这里两个盘子的思路也是整个递归的基础

（一） 有两个盘子的时候，一开始它们是叠放在A柱上的，目的地是B，然后要借助C柱子

因此我可以理解为，A是出发点，B是目的地，而C就是停靠站（工具人）了

（二）函数hanoi（n，A,B,C)

也就可以看成为hanoi（n，出发地，目的地，工具人）了，然后来看eles后面的语句：

1，else后面的第一步hanoi（n-1，A,C,B)意思就是其他盘子从A出发去C,给最下面的盘子留给去B的空间，当然B也充当上方盘子的根据人了（笑）

2，第二步没什么好说的，就是最底盘去最后的目的地B柱，然后把这一步骤的内容用文字打印出来

3，第三步hanoi（n-1，C,B,A）按照1的思路就很好理解了

C出发，通过B，到达A

（三）最后说一下count，参照上面树状图和代码，每一条横线其实对应一次count，也就是第二步还包含了count++

当然，树状图的分叉到了最后一定是横线

                                           / 转移一个—— 转移一个（count++）

可以理解为转移两个——   转移第二个（count++）

                                           \再转移一个——转移一个（count++)

截图来源：BV1Zh411y7XB

作者：水上由岐~