EOJ 1820 Hanoi Tower II

http://acm.cs.ecnu.edu.cn/problem.php?problemid=1820

汉诺塔变形：每步都得顺时针。（下图为逆时针）。

记 f[n] 为 把n个盘从 s->t 不经中间节点。如（A->B, B->C, C->A）

记 g[n] 为 把n个盘从 s->t   经中间节点。如（A->C, B->A, C->B）

分析见下图：

 

 

 

 

#include <stdio.h>

int main()
{
    unsigned long long f[45], g[45];
    f[1] = 1, g[1] = 2;
    for(int i=2; i<45; i++)
    {
        f[i] = 2*g[i-1] + 1;
        g[i] = 2*g[i-1] + f[i-1] + 2;
    }
    int n;
    while(scanf("%d", &n) != EOF)
        printf("%llu
", f[n]);
}