//先求出移動(dòng)的總步數(shù)
1，假設(shè)g（n）表示n個(gè)圓盤時(shí)的移動(dòng)總的步數(shù)，當(dāng)n=1時(shí)，g(1)=1;

2.現(xiàn)在可以把g(n)進(jìn)行細(xì)分為三步：
  1>先將n-1個(gè)圓盤從A通過C移動(dòng)到B上面，相當(dāng)于將n-1個(gè)圓盤從A移動(dòng)到C，因此需要g(n-1)步；
  2>然后將剩下的最大的圓盤從A移動(dòng)到C，需要1步；
  3>最后再將n-1個(gè)圓盤從B通過A移動(dòng)到C上面，相當(dāng)于將n-1個(gè)圓盤從A移動(dòng)到C，因此也需要g(n-1)步；
因此可以得出遞歸關(guān)系式：g(n) = 2*g(n-1)+1;

//現(xiàn)在我們?cè)趤?lái)求出移動(dòng)的過程
1.假設(shè)hm(m,a,b,c)表示將m個(gè)圓盤從a通過b移動(dòng)到c的過程，假設(shè)mv(a,c)輸出一次a到c的過程，即print a-->c

2.初始化hm，當(dāng)m=1時(shí)，hm(1,a,b,c)=mv(a,c);
2.可以把hm(m,a,b,c)進(jìn)行細(xì)分為三步：
  1>先將n-1個(gè)圓盤從A通過C移動(dòng)到B，此時(shí)b和c進(jìn)行互換，也就是 hm(m-1,a,c,b);
  2>然后將剩下的最大的圓盤從A移動(dòng)到C，也就是hm(1,a,b,c);
  3>最后將n-1個(gè)圓盤從B通過A移動(dòng)到C，此時(shí)b和a進(jìn)行交換，也就是 hm(m-1,b,a,c);
最終得到過程的遞歸關(guān)系式：hm(m,a,b,c) = hm(m-1,a,c,b)+1+hm(m-1,b,a,c);

public class test{
  public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    test t = new test();
    //獲取總的步數(shù)
    System.out.println("需要移動(dòng)的總步數(shù)為:" +t.getSum(n));
    //獲取移動(dòng)的過程
    t.hm(n,'a','b','c');
  }
  //獲取總步數(shù)
  public int getSum(int n){
    if(n == 1) 
      return 1;
    return 2 * getSum(n-1) +1 ;
  }

  //獲取移動(dòng)的過程
  public void hm(int m,char a,char b,char c){
    if(m == 1)
      move(a,c);
    hm(m-1,a,c,b);
    move(a,c);
    hm(m-1,b,a,c);
  }

  //輸出一次移動(dòng)的過程
  public void move(char a,char c){
    System.out.print(a + "-->" + c + "  ");
  }
}