汉诺塔（加强版）

有一个故事讲述了有64个不同大小的圆盘, 这些圆盘堆叠在寺庙的塔柱子上.当所有圆盘以相同顺序重新堆放到另一根柱子上时, 世界将终结.

以下是移动圆盘的规则：

1.一次只能移动一个圆盘. 2.每个步骤都包括从一座塔中取出上部圆盘并将其放在另一座塔的顶部或空的柱子上. 3.不能将较大的圆盘放置在较小的圆盘上.

不过, 好消息是, 即使有人每秒移动一个圆盘, 也要花费超过5,000亿年才能完全移动这座圆盘塔！

数学家爱德华·卢卡斯（ÉdouardLucas）根据这个故事发明了这个谜题, 今天我们将其称为“汉诺塔”（有时称为梵天塔或卢卡斯塔）.

让我们看一个简单的“汉诺塔”谜题, 以更好地理解可能的解决方案, 并将解决方案推广到64个圆盘的情况.

先考虑两个圆盘的情况.通过将小圆盘移动到空柱上, 将大圆盘移动到第三根空柱上, 然后将小圆盘放在大圆盘上可以解决这个问题, 这样共有次移动. 三个圆盘会使事情变得更加复杂.让我们看看是否可以使用两块圆盘的情况来帮助找到解决方案.我们已经知道3次移动是将两个较小的圆盘的微型塔移动到另一个柱子的最快方法.这样做之后, 我们有了一个空柱, 该柱子现在可以放置最大的圆盘, 到目前为止, 总共进行了次移动.由于三步移动是将较小圆盘的微型塔移动到另一个柱子的最快方法, 所以再次将两个圆盘移动到已经被较大圆盘占用的柱子上.因此对于三个圆盘的情况, 总共进行了了次移动. 继续这种推理, 我们可以找到针对四个圆盘情况的最佳解决方案.将三个较小的圆盘的微型塔移动到另一个柱子需要7次移动, 将最大的圆盘移动到空柱子需要1次移动, 然后再用7次移动将其他三个圆盘重新堆叠到最大圆盘上.总共次移动.

此“递归”策略适用于任何正数的圆盘, 因此解决64圆盘难题的最小移动数为次移动.

我们将汉诺塔谜题改编一下, 添加与现有圆盘之一大小相同的圆盘, 那么最佳策略将如何改变？