網頁

2013年12月29日 星期日

UVa 10017 The Never Ending Towers of Honoi

想法:
  河內塔問題可先簡化成只有一個,那麼只要將它從A移到C,而如果有兩個的話,那就把上面那個移到B,再把下面那個移到C,B再移到C即完成,因此如果有n個,先把上面(n-1)個從A移到B,再把下面那個移到C,最後把(n-1)個從B移到C。
  • Honoi(n,a,b,c) 表示將"n"個從A移到C(從第二個參數移到第四個參數)
  • Move(a,c) 表示將最下面一個從A移到C
因此可寫成遞迴式:

Hanoi(n,a,b,c)   //將"n"個從A移到C
{
    if(n==1) Move(a,c);  //只有一個,直接移到C
    else{
        Hanoi(n-1,a,c,b);  // 將"n-1"個從A移到B
        Move(a,c);  //將最底下那個從A移到C
        Hanoi(n-1,b,a,c); //最後將"n-1"個從B移到C
    }
}


注意本題output的要求:

  • 如果A=>之後沒有數字必須沒有空格
  • 每個問題後面都要有一個換行(包含最後一個問題)