摘要：
大约在19世纪末，一种智力玩具在欧洲的商店里出售。一块铜板上有三根柱子，由64个圆盘组成的塔从上到下，从小到大串在最左边的柱子上。其目的是将最左端的所有磁盘移动到右极，前提是一次只能移动一个磁盘，并且不允许将大磁盘放在小磁盘上。现在我们改变游戏的玩法。不允许从最左（右）侧直接移动到最右（左）侧（每次移动都必须移动到中间极或从中间移出），也不允许将大圆盘放在下圆盘的顶部
Problem Description
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？
Input
包含多组数据，每次输入一个N值(1<=N=35)。
Output
对于每组数据，输出移动最小的次数。
Sample Input
1
3
12
Sample Output
2
26
531440
题解：递归理解，先将n-1个盘从左移到中间再到右，将第n个盘移到中间，然后前n-1个盘移到中间再到左，再将第n个盘移动到右，最后前n-1个盘移到中间再到右。也就是说前n-1个盘要移动三次，第n个盘要移动两次，所以f(n)=3*f(n-1)+2,当n==1的时候，返回2.
#include <cstdio> #include <iostream> #include <string> #include <sstream> #include <cstring> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <map> #define PI 3.1415926 #define ms(a) memset(a,0,sizeof(a)) #define msp memset(mp,0,sizeof(mp)) #define msv memset(vis,0,sizeof(vis)) using namespace std; //#define LOCAL int a[100005],b[100005]; long long fun(int n) { if(n==1)return 2; return 3*fun(n-1)+2; } int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); #endif // LOCAL //Start int n; while(cin>>n) { long long ans=fun(n); printf("%I64d ",ans); } return 0; }