将柱子从左到右依次编号为A、B、C
设将n个盘子从一端移动到另一端的最少步数为f(n)
则f(n)和f(n-1)的递推关系为：f(n) = 3 × f(n-1) + 2
初始状态A柱子上面有n个盘子，将上面的n-1个移到C柱子上需要f(n-1)，然后将最下面的盘子移动到B柱子1步
再将n-1个移回到A柱子上也需要f(n-1)，将最下面的盘子移到C柱子1步，最后将A柱子上的移到C上面f(n-1)
通项公式也很容易归纳出来：f(n) = 3n - 1
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; unsigned long long a[]; int main(void)
{
#ifdef LOCAL
freopen("2064in.txt", "r", stdin);
#endif a[] = ;
for(int i = ; i <= ; ++i)
a[i] = a[i - ] * + ;
int n;
while(scanf("%d", &n) == )
cout << a[n] << endl;
return ;
}
代码君