#993. 汉诺塔问题

题目背景

传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题（Tower of Brahma puzzle）。但不知道是数学家卢卡斯自创的这个传说，还是他受他人启发。

题目描述

有三根杆子A，B，C。A杆上有 个 (>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

1. 每次只能移动一个圆盘
2. 大盘不能叠在小盘上面

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：最少要移动多少次？

共一行一个整数，表示

一个数，表示最少要移动多少次。

样例输入 1

3

样例输出 1

7

样例输入 2

4

样例输出 2

15

样例解释

请在附加文件中下载压缩包，查看样例解释

数据范围与约定

对于所有的数据,保证 。

出题人留言

我记得这题在今年早些时候，长郡中学、郑州外国语和杭州二中的联考中出现过。