编程题：双汉诺塔问题

双Hanoi塔问题是Hanoi塔问题的一种推广：有三根A、B、C三根柱子，现有$$n$$对直径大小不同的圆盘（同一对的两个圆盘直径相同），这些圆盘按照直径从大到小的次序从下到上放在A柱上，如果把1个圆盘从从一根柱子移动到另外一根柱子称作1次移动，在移动过程中允许借用B柱子，但不允许大圆盘放在小圆盘上面，每次只能移动一个圆盘。现在要用最少的步数把这些圆盘全部移到C柱，请设计一个算法求出最少移动次数。


### 输入格式:

一个正整数$$n(1\leq n \leq 200)$$，表示有$$n$$对圆盘。

### 输出格式:

输出最少的移动次数。

### 输入样例:

in
2


### 输出样例:

out
6







答案：若无答案欢迎评论

汉诺塔问题是难解问题，当$$n$$很大时不能通过找出移动步骤方式计算总的移动次数，而是设法找出递推方程，即移动$$n$$对圆盘的次数$$T(n)$$与移动n-1对圆盘的次数$$T(n-1)$$之间的关系。由于数值很大，约有一半的测试用例的结果不能用内置基本数据类型来表示，需要考虑特殊方法来处理。