我們?cè)O(shè)f(n)為把n個(gè)盤從1移到3所需要的步數(shù)，當(dāng)然也等于從3移到1的步數(shù)。

由上面的圖我們可以看到,要想把第n個(gè)盤從1移到3，需要3個(gè)步驟 :

    1.)      把前n-1個(gè)從1移動(dòng)3  .

    2.)      第n個(gè)盤要從1->2->3經(jīng)歷2步.

    3.)      而前n-1個(gè)盤需要先 3->1  ( 這是為了給 第n個(gè)盤讓路 ),   最后再 1->3。

   ∴f(n) = 3 × f(n-1) + 2;

       f(1) = 2;

      f(n) = 3 × f(n-1) + 2

      f(1) = 2

      =>

      f(n) + 1 = 3 × [f(n-1) + 1]

      f(1) + 1 = 2 + 1 = 3

      =>

      f(n) + 1 = 3n

      =>

      f(n) = 3n - 1

最后貼上代碼 :

//MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋

#include <iostream>
#include <cmath>
using namespace std;
long long myPow ( int n , int e )
{
     long long mlt = 1;
     for ( int i = 1; i <= e ; ++ i )
     {
           mlt *= n; 
     } 
     return mlt;
}
int main ()
{
    int N;
    while ( cin >> N )
    {
          cout << myPow ( 3, N ) - 1 << endl;
    }
    return 0; 
}