[C 語言 遞迴練習.思考] 河內塔 (Towers of Hanoi)

上圖來源:師範大學 某網站

上圖來源:https://ctfork12.ice.ntnu.edu.tw/conception.html
n為河內塔總數,在書上看到河內塔的簡介要寫程式來表現時,只覺得頭腦不夠用...需要整個寫出來才能思考...和發現規律(我自己是找不太出來規律...看別人講解和自己話圖才:哇!天阿!,雖然書中也有步驟,可是還是看不太懂別人怎麼歸納出來的想法跟程序的轉換...(雖然我畫了n=4的河內塔,可是還是想不出來解法...只能按照正常情況一一寫出的移動步驟並裡解程式它的寫法 ...與感嘆別人的腦子

n=1 
1.n1.A->C

n=2 
|    1.n1.A->B     (把1~1(1~n-1))的盤子從A搬到B)
2.n2.A->C        (把第n(2)的盤子 從A搬到 C)
|    3.n1 B->C     (把1~1(1~n-1))的盤子從B搬到C)

n=3
|    1.n1.A->C     2.n2.A->B     3.n1.C->B (把1~2(1~n-1))的盤子從A搬到B)
     上方可以拆解為 n=2時的情況,只是B與C互換
4.n3.A->C                                             (把第n=3的盤子 從A搬到 C)
|    5.n1.B->A     6.n2.B->C     7.n1.A->C (把1~2(1~n-1))的盤子從B搬到C)
      上方可以拆解為n=2,A與B互換

n=4  從A經B到C
{    1~n-1從A藉由C到B  從A經C到B
|    {    (1~n-2)從A藉由B搬到C,要讓n-1(3)可以放到B    從A經B到C
|    |     {    (1~n-3)從A搬到B,要讓n-2(2)可以放到C    從A經C到B
|    |     |    1.n1.A->B     n1 從A到B
|    |     }
|    |    2.n2.A->C          n2 從A到C
|    |    {    (1~n-3)從B搬到C,要讓n-1(3)可以放到B    從B經A到C
|    |    |     3.n1.B->C     n1 從B到C
|    }
|    4.n3.A->B              n3   從A到B
|    {    (1~n-2)從C搬到B,要讓n(4)可以放到C    從C經A到B
|    |    {    (1~n-3)從C搬到A,要讓n(3)可以放到B    從C經B到A
|    |    |    5.n1.C->A     n1 從C到A
|    |    }
|    |    6.n2.C->B          n2  從C到B
|    |    {    (1~n-3)從A搬到B,要讓n(4)可以放到C    從A經C到B
|    |    |    7.n1.A->B     n1  從A到B
|    |    }
|    }
}
8.n4.A->C                   n4  從A到C
下方就不再多用 { }表示...不然太長  下方是把1~n-1從B經A到C的過程,可以看縮排來得知在哪層
|    |    |    9.n1.B->C     n1
|    |    10.n2.B->A        n2
|    |    |    11.n1.C->A   n1
|    12.n3.B->C            n3
|    |    |    14.n1.A->B  n1
|    |    15.n2.A->C       n2
|    |    |    16.n1.B->C  n1

總共是可以分為三個步驟
1.把(1~n-1)的盤子從A搬到B  (從A藉由C到B)
2.把第n的盤子 從A搬到 C      (從A到C)
3.(1~n-1)的盤子從B搬到C      (從B藉由A到C)
void Honi(int n,char from,char by,char to)
{
    if(n>0){
        Honi(n-1,from,to,by);
        printf("no %d move from %c to %c",n,from,to);
        Honi(n-1,by,from,to);
    }
}