漢諾塔IV

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 15105    Accepted Submission(s): 10425

Problem Description

還記得漢諾塔III嗎？他的規(guī)則是這樣的：不允許直接從最左(右)邊移到最右(左)邊(每次移動一定是移到中間桿或從中間移出)，也不允許大盤放到小盤的上面。xhd在想如果我們允許最大的盤子放到最上面會怎么樣呢？（只允許最大的放在最上面）當然最后需要的結(jié)果是盤子從小到大排在最右邊。

Input

輸入數(shù)據(jù)的第一行是一個數(shù)據(jù)T，表示有T組數(shù)據(jù)。
每組數(shù)據(jù)有一個正整數(shù)n(1 <= n <= 20)，表示有n個盤子。

Output

對于每組輸入數(shù)據(jù)，最少需要的擺放次數(shù)。

Sample Input

2
1
10

Sample Output

2
19684

漢諾塔問題....找規(guī)律...觀察發(fā)現(xiàn)，先是小的移動到B，然后大的移動到C（兩步），然后小的移動到C，完成。剛開始就以為是f(n)=2f(n-1)+2..然而，小的移動一步是需要f(n)=3f(n-1)+1..

代碼：

#include<stdio.h>
long long a[20];
int main()
{
    int i,b,T;
    a[0]=0;
    for(i=1;i<22;i++)
        a[i]=3*a[i-1]+1;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
        scanf("%d",&b);
        printf("%lld\n",2*a[b-1]+2);
    }
    return 0;
}