汉诺塔问题

汉诺塔(Towers of Hanoi)问题来自大梵天创世的一个古老传说。在创世之日，有一座钻石宝塔（塔1），其上有64个金碟，所有碟子从大到小从塔底堆到塔顶，旁边还有另外两座钻石宝塔（塔2和塔3）。从创世之日起，婆罗门一直试图把塔1上的碟子移到塔2上去，不过要借助塔3。由于碟子非常重，所以一次只能移动一个碟子。另外，任何时候大碟子都不能压在小碟子上面。根据这个传说，等到婆罗门把盘子搬完了，世界末日也就到了。

/*
* 设塔 x 有 n 个碟子
*
*         -|-         |           |
*       --|--        |           |
*     ---|---       |           |
*   ----|----      |           |
* -----|-----     |           |
*        x           y           z
*
*
* Idea: 为了把最大的碟子移到塔 y 的底部, 必须把其余 n-1 个碟子移到塔 z
*       然后把最大的碟子移到塔 y. 接下来把塔 z 上的 n-1 个碟子移到塔 y.
*/

Reference:

Sartaj Sahni, Data Structures, Algorithms, and Applications in C++, Second Edition.
[美] 萨特吉.萨尼 著，王立柱、刘志红 译 《数据结构、算法和应用 C++ 语言描述》 机械工业出版社