当二进制遇见汉诺塔

xio计算机的怎么能不知道递归嘞？

学习递归思想怎么能不拿汉诺塔问题练手呢？（紧紧抱住弱弱的自己）

呐，先来讲讲汉诺塔是啥子

#汉诺塔问题

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

首先我们简化一下问题，把圆盘的数量设为3，这个问题就变得很简单了。

首先将最小的3号放在终点柱子上
再把中间小的2号放在缓冲区（第二根柱子）上
把3号放到2号上
把1放到终点柱子上
把3放到起点柱子上
把2放到1上
把3放到2上

于是，通过七步就将这个问题解决了

那我们将问题复杂化一下，盘子变成四个，这又该怎么解决呢？

假如我们不考虑这个多的第四个盘子，当它不存在，只看它头上的三个盘子，刚才提到的方法依旧可以完美的使用

（可以大脑过一遍）

于是我们得到了这样的结果：

那么我们可以非常鸡贼地把第二根柱子和第三根柱子替换，结果为：

然后把冒出来的盘子放到第三根柱子上，你会发现，这不就和3个盘子是一样的了吗？

4个盘子的挪动次数一共是

“3个盘子汉诺塔” + “4盘子移动到第三根柱子” + “3个盘子汉诺塔”

文字有点麻烦，快拿朕的数学公式来！

当问题是3个盘子的时候：

$A_3= 7$

当问题是4个盘子的时候：

$A_4 = A_3 + 1 + A_3$

换一种形式就是：

$A_4 = 2A_3 + 1$

如果对于任意个盘子，我们都使用这种方法

5个盘子，就先解决挪4个的问题

6个盘子，就先解决挪5个的问题

·······

n个盘子，就先解决挪n-1个的问题

所以移动次数的递推公式为

$A_n = 2A_{n-1} + 1$

数为n的汉诺塔问题通项公式为

$A_n = 2^n -1$

实际上我们把这个n个盘子的问题拆解了，分成了一步一步思路重复的工作

不断重复的流程是：

把n-1号盘子移到缓冲区柱子上
把n号盘子从起点柱子移到终点根柱子上
把n-1号盘子从缓冲柱子移到n号盘子上

py代码：

def move(n,from,buffer,to): # n为盘子总数，from为起点柱子，buffer为缓冲区柱子，to为终点柱子
    if n==1:
        print('Move',n,'from',from,'to',to)
    else:
        move(n-1,from,to,buffer) #  把n-1号盘子移到缓冲区柱子上

        move(1,from,buffer,to)  # 把n号盘子从起点柱子移到终点根柱子上

        move(n-1,buffer,from,to)    #   把n-1号盘子从缓冲柱子移到n号盘子上Copy