請問如何寫出這題河內塔

題目:

    初始狀態下有三根柱子 ,分別為 ABC 三支 ,當中 A 柱擺上將要搬移的碟子 ,碟子由上到下依小到大疊好 ,分別編上號碼 1,2,3,4.... ,需將所有碟子全部搬移到 C 柱 ,規則為大碟不得擺在小碟上 ,也就是數字小者必須在前方
要求:

Input : 有幾個環,由上而下為 1,2,.....,N
Output: 每一步的動作的結果(輸出的要求是列出每一步驟後 ,各個柱子的情形 ,例:第一步由 A 搬 1 號碟到 C ,輸出便是: A(2,3)B()C(1))
三根柱子由左至右為 A,B,C
example:

    Input : 2 (<-- 此數字為測試資料筆數)
              3 (<-- 第一組測試數 ..

訪客只能看到部份內容，免費 加入會員

x0

參考一下，這是我覺得最簡單可以理解的

http://tw.knowledge.yahoo.com/question/question?qid=1608110103848


試試看 高度(設為 h) h = 3, h = 4, h = 5..... 的河內塔你會發現一個規律

就是 h 為奇數時，第一個盤子都一定會先放到最右邊 (假設一開始全部在左邊)

h 是偶數時，第一個盤子一定會先放到中間


那麼，你就可以發現其中的規律，你試著想想看，h = 3 的河內塔將 "最小的盤子" 移到最右邊時

和 h = 4 河內塔將 "最上面的兩個小盤子" 依照規律移動到 最右邊時，把這兩個小盤子 "群組化" 當成是一個小盤子






就會發現，h = 4 移動第三次與 h = 3 移動一次 的感覺是非常像的，這就是上面知識+提到 的想法

當河內塔其中一個桿子是空的時候，要移動比較小的那堆時，可以想像成，整個河內塔要移動的只有 那幾個小盤子 (因為不管怎麼移動這幾個小盤子，都不會違反 小的要在大的上面)

例如，h = 4 時候，如上圖下面的情況，要把最右邊兩個小盤子準備移動到 第二大的盤子(下一步驟 : 移動到中間桿子)


知道這個規律後，就能用 遞迴 (recursive) 或是一般的 迴圈 來跑程式了

x0