遞迴經典題目-河內塔

題目說明:

假設有3個塔，其中第一個塔有n個由小到大的圓盤，由上到下依序地疊好，假如要將其中圓盤依元排列方式移到第三個塔，且需依三個規則

1)一次只能搬1個圓盤，且只能搬最上面的圓盤
2)大圓盤不能疊在小圓盤上
3)再搬動過程中，可用第二個塔做中繼站

數學演算法如下:
1)將n-1個圓盤移到中繼塔上
2)將最下面的圓盤移到終點塔
3)再將n-1個圓盤移到終點塔

如下圖
        _                                                                                                          _
      ___                                                                                                       ___ 
     _____                                         轉換為                                               _____

  第一個塔        中繼站     目的塔       =>         第一個塔         中繼站        目的塔

其主要副程式

i=圓盤數量  這邊以2來說明
begin=1  起始塔
mid=2    中繼塔
dest=3    目的塔

1  void hanoi(int i,int begin,int mid,int dest)
2  {
3    if(i==1)  
4     printf("將第%d個盤子從第%d個塔移到第%d個塔\n", i,begin,dest);
5      else
6  {
7    hanoi(i-1,begin,dest,mid);          
8    printf("將第%d個盤子從第%d個塔移到第%d個塔\n", i,begin,dest);
9    hanoi(i-1,mid,begin,dest);
     }
    }

Step1:

    第一次執行時，i=2,begin=1,mid=2,dest=3會直接執行第7行的hanoi(1,1,3,2)
Step2:

    此時會遞迴此副程式並執行至第3、4行，其輸出"將第1個盤子從第1個塔移到第2個塔"

Step3:

   執行完步驟二會再返回步驟一的第8行，切忌此時的i、begin、mid、dest都是原始數值，其數值為i=2,begin=1,mid=2,dest=3，並輸出"將第2個盤子從第1個塔移到第3個塔"

Step4:

   執行第9行，此時hanoi(1,2,1,3)，重新呼叫此副程式進入第3、4行，輸出"將第1個盤子從第2個塔移到第3個塔"

Ref:
[1]最新C程式語言  旗標出版
[2]http://finalfrank.pixnet.net/blog/post/18372611-%E6%B2%B3%E5%85%A7%E5%A1%94-%E9%81%9E%E8%BF%B4
[3]圖解網站可參考
    http://content.edu.tw/senior/computer/ks_ks/book/algodata/algorithm/algo44.htm