往届 ACM 队训练题 (参考)

1021. Hanoi Tower II

单点时限: 2.0 sec

内存限制: 256 MB

经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往上按大小顺序摞着 64 片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一回只能移动一个圆盘。有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩,当然这个传说并不可信,如今汉诺塔更多的是作为一个玩具存在。Gardon 就收到了一个汉诺塔玩具作为生日礼物。

partychen 想了一个新的规定 , 如果所有移动一定是顺时针方向 , 也就是说 , 从 A 到 B, 或从 B 到另一个杆 , 或从另一个杆到 A. 现在 partychen 想知道一次游戏种使用 N 个盘子时 , 他最少需要多少次移动才能把他们从 A 转移到 B. 很显然,在没有限定只能顺时针时,问题的解是 2^N-1,但现在有这个要求,又该是多少呢?

输入格式

包含多组数据,每个数据一行,是盘子的数目 N(1<=N<=40)。

输出格式

对于每组数据,输出一个数,到达目标需要的最少的移动数。

样例

Input
1
5
Output
1
119
不限期开放

题目列表