#今天要来点数学吗？##算法[超话]#

The Tower of Hanoi 汉诺塔问题

源于一个传说，在越南河内的一座寺院中，有三根银棒，上面串着64个金盘。寺院里的僧侣们依照一个古老的预言，按照特定规则移动这些盘子。

- 一次只能移动一个盘子。
- 只有顶部的圆盘可以转移到另一堆的顶部或空杆上。
- 较大的圆盘不能堆叠在较小的圆盘上。

预言称，当所有盘子都按规则移动完毕时，世界将会终结。

还有一系列梵天寺之塔版（Tower of Brahma puzzle），多个版本。其中一个版本提到，梵天在创世时制造了64片金片，并在贝拿勒斯的圣庙中，从下到上地穿在一根针上。僧侣们不断地按规则移动这些金片，预言着当金片全部移动到另一根针上时，世界将会毁灭。

汉诺塔问题不仅是一个有趣的数学难题，也蕴含着关于宇宙和时间的深刻哲理。如果每秒钟移动一次，将64个盘子从一根针移动到另一根针上，需要的时间将远超过宇宙的年龄。

对它的现代研究最早由法国数学家爱德华·卢卡斯提出，如今这个问题在数学和计算机科学中作为基础的教学习题，用于探讨递归算法和问题解决策略。

对于n个环三柱的汉诺塔，最少移动步数是多少？

2^n-1

证明其最优也不困难，因为当最大的圆环从一个柱子移动到另一柱子时，其它n−1个圆环都必须在第三个柱子上。非常简单的递归。

TOH的自然延伸是将柱子的数量从三个增加到四个或更多，从而情况发生巨大变化。1939 年，Stewart 在文献中首次提出了它的时间复杂度，肯定小于上述2^n-1步，两年后，Stewart 和 Frame 在没有证明的情况下独立提出了他们所谓的“最优”算法。这两种算法被证明是等价的，从那时起，它们就被称为Frame-Stewart算法，其最优性是一个具有挑战性的开放性问题。

Bousch在2014年证明了四柱Frame-Stewart算法的最优性。更多柱子的解决方案仍然悬而未决。因此，TOH的时间复杂度一直是一个热门话题，但没有关于其空间复杂性的文献。从时间复杂性的历史来看，空间复杂性可能同样不平凡。

此外，它还和泊车函数相关（大概后天会讲到~泊车问题）

http://t.cn/A6TtJDMH