【百题千解】题解 P1242 【新汉诺塔】

Anye
Anye
发布于 2019-10-20 / 3 阅读
0
0

【百题千解】题解 P1242 【新汉诺塔】

看了楼上大佬的解法,应该都没有想到汉诺塔二进制还有一层微妙的关系,所以我来介绍一种二进制解汉诺塔的思想。

找规律

我们可以观察到这样一种规律:

二进制:需要前面全都变成1才能进位

汉诺塔:需要上面的盘子全都移走才能移动。

而这有相似之处。所以我们就可以想,可不可以用二进制来模拟圆盘的移动? 我们先来考虑一种简单的情况

KPDxAO.png

来我们观察一下,假设汉诺塔的圆盘都在A柱上,我们从0数起(0000)

KPDzND.png

当我们把末位数从0变成1时,就把0号盘移动到右边的柱子上(如下图)

KPDjHK.png

如果0已经在C柱上了,

KPsRoT.png

就把它移回A柱

KPsvfe.png

要是在二进制计数中

KPyt1J.png

已经进到了二位,也就是把末尾的两位数从01变成10的话,

KPyYp4.png

就移动1号圆盘

KPyGhF.png

然而显然不能把它移到B柱上,所以就剩下C柱可以

KPy8tU.png

当数到11,只需要个位加一,所以只需移动0号圆盘

KP6S4U.png

然后二进制中进到四位,所以移动2号圆盘

KP6Qvd.md.png

接下来以此类推:

个位加一,移动0盘;

二位加一,移动1盘;

三位加一,移动2盘;...

gif.gif

动画演示就像这样

证明

我们来证明一下这种思路的可行性。

汉诺塔的最少移动数的方案可以看作是要先把A柱上,最底面的圆盘以上的塔先移开,倒数第二盘要移动就要先把以上的圆盘移开,也就是一个递推的过程,而二进制的进位就是一个最简的递推方案。所以我们完全可以用二进制来模拟圆盘的移动。

关于此题

我们会发现,其实每一种汉诺塔的排列都会对应一个二进制数,二进制数转换成十进制数就是从0000推到现在这种排列的最少步数,那么这道题我们就可以先把给定初始状态的A,B,C柱上的圆盘转换成二进制数,然后模拟二进制数一直加1的过程,得到目标状态。我们就可以很简单的解决这道题了。

提醒

A,B,C三柱其实可以认为是不固定的,所以完全可以将初始状态的A,B,C柱上的圆盘进行交换以获取一个二进制数。

更新

2019/10/21题解已发布,但是排版甚是难看,返工。


评论