当二进制遇到汉诺塔

当二进制遇见汉诺塔

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号盘子上

这个问题就完美滴解决了

下面就要讲如何用二进制解决汉诺塔问题

#二进制与汉诺塔

解决方法来自用二进制解决汉诺塔问题-3brown1blue
(我在b站学习系列orz)

首先我们看二进制的一些特别的地方

拿从0记到十进制15为例

0000

-> 0001 -> 0010 -> 0011 -> 0100 -> 0101 -> 0110 -> 0111

-> 1000

-> 1001 -> 1010 -> 1011 ->1100 -> 1101 -> 1110 -> 1111

1000是数字8,我们可以发现从0记到15的过程其实是对称的

  • 从0记到7,一共经加了七次(可以数一下第一行的箭头数)
  • 加一,实现了由7加到8
  • 再从8记到15,同样加了七次(数一下最后一行的箭头数)

是不是隐隐感觉有点儿不对了?好像这个流程和我们之前讲到的汉诺塔递归很相似啊!

他们是不是有什么联系呢?

答案是有的,如果我们依旧拿4个盘子的汉诺塔问题举例,二进制数起始为0000

0000 -> 0001 即把0从第一根柱子移到右边的柱子上

0001 -> 0010 就将1号盘移动到剩余的柱子上

0010 -> 0011 个位数加一,将0号盘移动到右边柱子上

0011 -> 0100 我们的数字又加了一位,将2号盘向右移动

0100 -> 0101,又是个位数字加一,可是0号盘子没有可以继续右移的柱子了,那就把它放到起始柱子上

0101 -> 0110 应该移动1号盘子,可是既没有可以右移的柱子,起始的柱子又挪不了,就放在中间柱子上吧

0110 -> 0111 又是个位数由0加1,将它移动到右边的柱子

0111 -> 1000 从7数到8了,将3号盘子右移

接下来的过程,就和刚才的一样,实质上是抛弃“千位”,从000记到111

我们可以惊奇的发现,这个流程真的和我们正常做汉诺塔问题完全一致

实际上,这个做法是规定了二进制数加一时,应该进行什么样的模拟操作

我们规定“移动”为向右移动一根柱子,检查条件,无法放下就换下一根,且末尾柱子的下一根,是起始柱子

另外,某一位数,由0变为1,就挪动代表该位的盘子,比如“个位” 00 -> 01 则移动0号盘子

在这样的规则下,非常奇异地,它符合了汉诺塔最优解的流程

我们可以说,二进制的计数与汉诺塔问题的步骤具有某种相似性

(是不是很神奇啊哈哈哈哈,感觉两个八竿子打不着的东西居然如此相关)

更多的内容和应用,在这个视频中有提到哦:

用二进制解决汉诺塔问题-3brown1blue

一起来b站学习吧ヽ( ̄ω ̄( ̄ω ̄〃)ゝ


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!