HDU 2064 (递推) 汉诺塔III

将柱子从左到右依次编号为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) = 3ⁿ - 1

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 unsigned long long a[40];
 8 
 9 int main(void)
10 {
11     #ifdef LOCAL
12         freopen("2064in.txt", "r", stdin);
13     #endif
14 
15     a[0] = 0;
16     for(int i = 1; i <= 35; ++i)
17         a[i] = a[i - 1] * 3 + 2;
18     int n;
19     while(scanf("%d", &n) == 1)
20         cout << a[n] << endl;
21     return 0;
22 }

代码君