2211: 宝典2第八章双塔问题

【问题描述】双塔问题(hanoi2.cpp/c/pas)

楚继光：“防御系统还真有用，修罗王的魔法炮阵的火力果然减弱了，但好像还差一点点啊？”

墨老师：“哦，是吗，那试试双塔防御体系吧。”

如图所示，给定A，B，C三根足够长的细柱，在A柱上放有2n个中间有空的能量圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的，图为n=3的情形。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。每次只能移动一个圆盘，每个柱子的圆盘保持上小下大的顺序。要求输出最少移动次数。

【输入格式】

输入文件hanoi2.in为一个正整数，表示A柱上有2n个圆盘。

【输出格式】

输出文件hanoi2.out仅一行，包含一个正整数，为最少移动次数。

【输入样例１】

1

【输出样例1】

2

【输入样例2】

2

【输出样例2】

6

【数据范围】

对于50%的数据，1≤n≤25;

对于100%数据，1≤n≤200。