2659：汉诺塔

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。

大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着$$64$$片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门还在一刻不停地搬动着圆盘。

问：把$$n$$片黄金圆盘从一根柱子移动到另一根柱子至少需要操作多少次。

第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \leq T \leq 64$$）

每组案例是一个正整数$$n$$表示待移动的圆盘数量。（$$1 \leq n \leq 64$$）

针对每组案例，输出把$$n$$片圆盘从一根柱子移动到另一根柱子至少需要操作的次数。

2

1

2

1

3

题单#18（递推与记忆化搜索）