ハノータIII

前言
はい、これは私がハンノタに戻った後の水を理解した文章であることを認めます.真髄は参考にすることができます.http://blog.csdn.net/wzy_1988/article/details/9822995
タイトル

    ：
 19   ，               ，          ，          、         64       。                    ，            ，             。           ，        ( )     ( ) (                  )，             。Daisy                II，        ，          ，       。   N   ，                        ？
  ：
      ，      N (1<=N=35)。
  ：
      ，         。
    ：
1
3
12
    ：
2
26
531440

構想
具体的な実装の詳細は、前のブログを参照してください.
使用するhttp://ac.jobdu.com/problem.php?pid=1458方法はタイムアウトします.ハノータの実現過程をシミュレートするために、時間の複雑さはO(2^n-1)に達します.実は回数だけを求めると、法則をまとめ、forサイクルでO(n)の時間の複雑さの中で実現することができます.
n個の皿がsrcからdstに移動するのにかかる移動回数をf(n)で表し,様々な状態を再分析した.
(1~n,0,0)-->初期状態
(n,0,1~n-1)-->n-1個の皿をsrcからdst(真ん中はsendからbri、さらにsendからdst)に移動 --> f(n - 1)
(0,n,1~n-1)-->n番目の皿をsrcからbri-->1に移動
(1~n-1,n,0)-->dst上のn-1個の皿をsrc-->f(n-1)に戻す
(1~n-1,0,n)-->bri上のn番目の皿をdstに移動 --> 1
(0,0,1~n)-->src上の残りのn-1皿をdstに移動(問題規模減少) --> f(n - 1)
そのため、
f(n) = 3 * f(n - 1) + 2
ACコード

#include 
#include 
 
int main(void)
{
    int i, n;
    long int f[37];
 
    while (scanf("%d", &n) != EOF) {
 
        for (i = 2, f[1] = 2; i <= n; i ++) {
            f[i] = 3 * f[i - 1] + 2;
        }
        printf("%ld
", f[n]);
    }
 
    return 0;
}
/**************************************************************
    Problem: 1458
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:912 kb
****************************************************************/