這題的主文使用英文，因此這邊附上個人大致的翻譯，不會完全按照原文翻：
內容：
河內塔問題在電腦科學是有名的問題之一，簡單說就是有3根柱子，在A柱上有大小若干圓盤，要將全部圓盤從A柱藉由B柱這暫存柱移到C柱，移動過程大圓盤都不能在小圓盤上面，目標是求移動的最小次數。
初學者在圓盤只有3個或4個時可以很輕鬆就了解其移動過程，使用簡單的程式也能找出更多圓盤數的移動過程，這裡我們讓題目增加一點靈活性來提升難度，題目一開始的圓盤可以在任一柱上。
題目一開始時若某柱有2個以上的圓盤，那一定是「合法」的順序(即較大的圓盤一定在較小的圓盤下面)，
題目將給你2種圓盤狀態，你的任務是找出從初始狀態到結束狀態時移動圓盤的最少次數，想當然移動過程必須符合大圓盤都不會壓在小圓盤上面。
輸入說明：
輸入測資有多筆測資點，每筆測資點有3行
第1行為一個正整數 n，1 <= n <= 30，為圓盤的數量
第2行及第3行分別為圓盤的初始狀態與結束狀態，每個狀態有 n 個數字，其值為 1、2、3 任一個，分別代表該圓盤放在A柱、B柱、C柱，舉例來說若第 i 個圓盤 ( 1 <= i <= n ) 的值為 1，代表第 i 個圓盤在A柱，例如以下測資：
4
1 1 1 1
1 2 2 1
代表這題有4個圓盤，初始狀態第1、2、3、4號圓盤都在A柱，結束狀態第1、4號圓盤在A柱；第2、3號圓盤在B柱。(圖略)
輸入測資為 0 代表結束，請不要讓程式做任何操作。
輸出說明：
每筆測資點請輸出一個數字(一行一個)，代表河內塔從初始狀態到結束狀態時所需要的最少移動次數。
-----------------------------------------------------------------------------------------------------------------------------------
在初次學習各種程式語言的時候，只要到遞迴的部分一定會學到河內塔
所以基礎的部分這邊完全不會說，如果還沒學到基礎版，請先去學習了解後再看這篇
由於範例太簡單，難以說明我的思路歷程，以下是我自己想的範例
9
1 2 3 1 2 3 1 2 3
1 1 1 2 2 2 3 3 3
範例有9個圓盤，初始狀態如下：
而目標狀態如下：
這題我在網上搜尋時有看見使用DP(動態規劃)的技巧來解題，但我看好幾遍都看不懂，所以決定自製複雜範例，並一步一步去構築整個程式架構，最終使用遞迴來解。
一：思路歷程
原本的河內塔玩法是將A柱上的所有圓盤都移到C柱，而這題則是指定初始狀態與目標狀態，不論狀態如何，大圓盤一定不能放在小圓盤上，那如果大圓盤要移動到它的目標，這個大圓盤一定只能是這根柱子的頂端盤，並且目標柱上不能有比這個大圓盤還小的盤子，換句話說，將大圓盤從當前所在柱移動到目標柱，比它小的所有圓盤都只能放在沒使用到的第3根柱子上。
例如這題範例，最大號盤為9號，它剛好不用移動，因此我們可以完全忽略它。那我們就從8號開始，它要從B柱移動到C柱，那麼1~7號盤都必須離開B柱與C柱，才能移動8號盤並且不會讓8號盤放在這些小盤上，那唯一的方法就是把1~7號盤集中到A柱，這樣才能搬8號，如同一般河內塔玩法。當1~7號都在A柱，那它為了符合規則，一定會形成一座完整、編號連續的塔，當8號移動過去之後，接下來第3大的盤子是7號，它要搬到C柱，此時只要1~6號搬到B柱，7號就能從A柱移動到C柱，依此類推。
由上可知，把大的圓盤移動到目標，在整理過程較小的圓盤一定會形成完整子塔，在移動完大圓盤後，就把自然形成的完整塔由大到小逐一安排進圓盤各自目標，因此主程式我們使用一個迴圈，從最大號圓盤開始，比對圓盤的當前位置與目標位置，如果位置相同代表不用移動，直接檢查小一號圓盤，但如果位置不同，就呼叫另一個方法遞迴處理。
| for(i=n ; i>0 ; i--) { if(當前柱 == 目標柱){ continue; } // 移動第i盤 } |
只要移動了最大盤，剩餘小盤一定會形成完整子塔，那我們就需要一個監控的 boolean 變數，這樣進入下一個迴圈後，完整塔的最大盤想要移動，只要使用原本的河內塔解法 "搬走" 上方的子盤，最大盤再移動一步就搞定了。
| firstArbitrarilyToSubTower = false;//一個監控"初次調整"的變數 for(i=n ; i>0 ; i--) { if(當前柱 == 目標柱){ continue; } // 移動第i盤 if(!firstArbitrarilyToSubTower){ //如果還沒有"初次調整"，需要遞迴處理 } else { //只要調整過第一次，一定形成完整的塔 //那只要使用一般河內塔解法，就能求得最少步數 } } |
二：程式實作細節
(一) 首先建立2個 int 陣列，第一個陣列power2[]儲存2的次方的數字，第二個陣列plates[]儲存盤子，這裡的盤子我使用一個class Disc來生成，每個Disc物件代表一個盤子，記錄自己的當前柱(now)與目標柱(goal)。
(二) 接著讀取測資，在儲存盤子的位置時為了讓盤子編號與陣列索引一一對應，儲存時索引從1開始。
(三) 接下來建立變數，int ans 代表這題答案，int temp 代表暫存柱，int subTower 代表 1~subTower 的完整子塔，接著初始化變數值，其中 subTower 進行如下處理：
| ans = 0; subTower = 1; while(subTower < 測資最大值 && plates[subTower].now == plates[subTower+1].now) { subTower++; } |
(四) 接著建立迴圈如上，從最大盤開始檢查，我們就用剛剛的範例，此時 n 等於 9，9號因為不用移動
直接跳過，從8號繼續。
(五) 8號因為當前柱(B)與目標柱(C)不同，必須移動，因此我們要求出1~7號的暫存柱 temp，補充一下，這裡將柱子編號使用數字儲存，令 A柱 = 1、B柱 = 2、C柱 = 3，求出
temp = 6 - plates[i].now - plates[i].goal，因為3柱編號加起來等於6，用6扣掉盤子當前柱與目標柱就是暫存柱編號，1~7號盤的暫存柱 temp = 6-2-3 = 1，即A柱，接著遞迴求解：
| if(!firstArbitrarilyToSubTower) { if(subTower > i-1) subTower = i-1 ; ans += hanoiArbitrarily(i-1, temp, (subTower == i-1) ); firstArbitrarilyToSubTower = true; }else { if(i!=1) { for(j=i-1 ; j>0 ; j--) plates[j].moveTo(plates[i].now); //這裡等同於 plates[j].now = plates[i].now; ans += hanoiArbitrarily(i-1, temp, true); } } |
4
1 1 1 1 <- 此時1~4號都在A柱，完整子塔 subTower 等於 4，
1 2 2 1 <- 迴圈處理3號盤時，變更 subTower 值為 2
判斷是否存在完整子塔，可以直接使用一般河內塔解 2^n-1 來加速程式求解，因此"初次調整"前，
(subTower == i-1) 判斷完整子塔的存在。回到剛剛範例，8號盤要移動，將1~7號盤移動到暫存柱，但是目前還不知道要移動幾步，因此呼叫 hanoiArbitrarily()，這方法輸入要調整的子盤數、暫存柱編號、以及是否完整子塔作為參數，回傳最少步數作為答案，由 ans 獲得答案，設定"初次調整"為 true。下一個迴圈開始要處理的當前盤子與其子盤一定是完整子塔，為了避免求解時因為子盤位置錯誤而求出錯誤答案，在else 跑一個for迴圈設定子盤位置與當前盤位置相同，設定完就可以呼叫 hanoiArbitrarily()方法求解了。
(六) 調整完子盤位置，最後別忘了，當前迴圈的盤子要移動，我們只要一行程式：ans++ ;
| for(i=n ; i>0 ; i--) { if(plates[i].now == plates[i].goal) { ...... } temp = 6 - plates[i].now - plates[i].goal; if(!firstArbitrarilyToSubTower) { ...... }else { ...... } ans++; } |
迴圈進行到6、5、4號時，因為這些盤子都不用移動，所以跳過，而跳過之前要設定子盤位置與當前盤位置相同：
| if(plates[i].now == plates[i].goal) { if(firstArbitrarilyToSubTower && i!=1) { for(j=i-1 ; j>0 ; j--) plates[j].moveTo(plates[i].now); } continue; } |
(七) 主要部分處理完了，接著是遞迴的部分，剛剛在移動8號盤之前我們要求1~7號盤移到暫存柱的答案，
呼叫 hanoiArbitrarily(7, 1, (subTower == 7) ) 開始遞迴(subTower是1)，首先是遞迴式的停止條件：
| public static int hanoiArbitrarily(int subDiscs, int target, boolean isSubTower) { if(subDiscs == 0) return 0; if(subDiscs == 1) { if(plates[1].now != target) { plates[1].moveTo(target); return 1; } else return 0; } ...... |
如果調整子盤 subDiscs 等於 1，代表呼叫方法時只剩2個盤子，1號盤可能在或不在要過去的暫存柱。
停止條件說完了，接下來是核心流程：
(1) 1~7號盤需要移到暫存柱 target，對這些盤子而言就是要從當前位置 now 移動到 target，但是不同測資下這些盤子可能在同一柱上也可能在不同柱上，因此需要 isSubTower 判斷，如果是 true，就可以使用一般解 2^ subDiscs -1，如果是 false，往下一個 if 判斷。這裡 isSubTower 由上可知是 false。
(2) 1~7號盤要移動，初始位置各不相同，但最大盤 7號要從"當前"柱(now)移動到"目標"柱(target)，其餘1~6號一定要移到剩下的"暫存"柱(temp)，那對於7號而言，1~6號要先"搬走"，7號才能"移動一步"，然後1~6號才能"搬回"，因此總移動步數 = "搬走" + "1" + "搬回"，對於"搬走"我們既然仍不知道答案，就繼續遞迴，然後7號"移動一步"，最後"搬回"時1~6號一定是完整子塔，套用一般解即可。
(3) 但是題目要求"最少"步數，能不搬就不搬，在搬7號盤之前先判斷7號要不要移動，如果
plates[7].now 不等於 target，我們才需要"搬走" 跟 "搬回"，反之如果相等，7號盤此時只要遞迴呼叫方法，接收1~6號盤從各自位置搬到 target 的答案。這裡的範例從開始到現在都還沒搬任何盤子，因此此時的 7號盤的 now = 1 (A柱)，而 target 也是 1，所以我們直接呼叫 hanoiArbitrarily(6, 1, false); 等答案。
| int steps = 0, substep = 0; int temp = 0; if(isSubTower) { ...... } else if(plates[subDiscs].now != target) { temp = 6 - plates[subDiscs].now - target ; substep = hanoiArbitrarily(subDiscs-1, temp, isSubTower); // "搬走" plates[subDiscs].moveTo(target); // "一步" steps = substep + 1 + (power2[subDiscs-1]-1); // 最後是"搬回" } else { steps = hanoiArbitrarily(subDiscs-1, target, isSubTower); } return steps; |
(八) 遞迴部分大致上處理好了，if( isSubTower ) 這裡還需要單獨拉出來說明：
(1) 因為測資有任意可能的狀態，在迴圈裡單純判斷 (subTower == i-1) 會有盲點，例如以下測資：
4
1 1 1 2
1 1 1 3
這題在迴圈判斷，(subTower == 3) 結果是 true，而另一個測資：
4
1 1 1 1
1 1 1 2
(subTower == 3) 結果也是 true，但很明顯第一個測資答案 = 1，第二個測資答案一定不是 1，因此在遞迴方法的 if( isSubTower ) 部分，使用以下的判斷：
| if(isSubTower) { boolean isfinish = true; for(int i=subDiscs ; i>0 ; i--) { if(plates[i].now != target) { isfinish = false; break; } } if(isfinish) { steps = 0; } else { plates[subDiscs].moveTo(target); steps = power2[subDiscs]-1; } } else if(plates[subDiscs].now != target) { ...... |
(1、2號不用設定新位置，因為下一個迴圈處理3號時會修正他們的位置)
三：範例流程
還是使用一開始我舉的範例跑整個流程：
9
1 2 3 1 2 3 1 2 3
1 1 1 2 2 2 3 3 3
(一) 主迴圈 i = 9：因為 plates[9] 的 now(C) == goal(C)，跳過處理 (continue )，答案 ans = 0
(二) 主迴圈 i = 8：因為 plates[8] 的 now(B) != goal(C)，要移動，求出 temp = 6 - 2 - 3 = 1，遞迴呼叫(a)
(1) hanoiArbitrarily(7, 1, false) ---(a)
首先1~7號盤不是完整子塔，接著 plates[7] 的 now(A) == target (A)，遞迴呼叫(b)等答案
(2) hanoiArbitrarily(6, 1, false) ---(b)
1~6號盤不是完整子塔，plates[6] 的 now(C) != target (A)，要移動，
求出 temp = 6 - 3 - 1 = 2，先"搬走"，遞迴呼叫(c)等答案
(3) hanoiArbitrarily(5, 2, false) ---(c)
1~5號盤不是完整子塔，plates[5] 的 now(B) == target (B)，遞迴呼叫(d)等答案
(4) hanoiArbitrarily(4, 2, false) ---(d)
1~4號盤不是完整子塔，plates[4] 的 now(A) != target (B)，要移動，
求出 temp = 6 - 1 - 2 = 3，先"搬走"，遞迴呼叫(e)等答案
(5) hanoiArbitrarily(3, 3, false) ---(e)
1~3號盤不是完整子塔，plates[3] 的 now(C) == target (C)，遞迴呼叫(f)等答案
(6) hanoiArbitrarily(2, 3, false) ---(f)
1~2號盤不是完整子塔，plates[2] 的 now(B) != target (C)，要移動，
求出 temp = 6 - 2 - 3 = 1，先"搬走"，遞迴呼叫(g)等答案
(7) hanoiArbitrarily(1, 1, false) ---(g)
此時 subDiscs 等於 1，因為 plates[1] 的 now(A) == target (A)，不用移動，回傳答案 0 給 (f)
(8) 回到(f)，"搬走" = 0，移動 2號到 target (C)，總步數為 0 + 1 + ( 2^(2-1) -1 ) = 2
回傳答案 2 給 (e)
(9) 回到(e)，此時 1~3號已到 C柱，回傳答案 2 給 (d)
(10) 回到(d)，"搬走" = 2，移動 4號到 target (B)，總步數為 2 + 1 + ( 2^(4-1) -1 ) = 10
回傳答案 10 給 (c)
(11) 回到(c)，此時 1~5號已到 B柱，回傳答案 10給 (b)
(12) 回到(b)，"搬走" = 10，移動 6號到 target (A)，總步數為 10 + 1 + ( 2^(6-1) -1 ) = 42
回傳答案 42 給 (a)
(13) 回到(a)，此時 1~7號已到 A柱，回傳答案 42
( i = 8 )
答案 ans += 42，"初次調整" 設為 true，移動 8號，ans ++，迴圈結束
(三) 主迴圈 i = 7：(現在1~7號都在 A柱)，
因為 plates[7] 的 now(A) != goal(C)，要移動，求出 temp = 6 - 1 - 3 = 2，已"初次調整"，設定1~7號盤當前位置為 A柱，遞迴呼叫(a1)
(1) hanoiArbitrarily(6, 2, true) ---(a1)
1~6號盤是完整子塔，1~6號都在 A要移動，移動 6號到 B，答案為 2^6 -1 = 63，回傳答案 63
( i = 7 )
答案 ans += 63，移動 7號，ans ++，迴圈結束
(四) 主迴圈 i = 6：(現在1~6號都在 B柱)，
因為 plates[6] 的 now(B) == goal(B)，不用移動，已"初次調整"，設定1~5號盤當前位置為 B柱，迴圈結束
(五) 主迴圈 i = 5：(現在1~5號都在 B柱)，
因為 plates[5] 的 now(B) == goal(B)，不用移動，已"初次調整"，設定1~4號盤當前位置為 B柱，迴圈結束
(六) 主迴圈 i = 4：(現在1~4號都在 B柱)，
因為 plates[4] 的 now(B) == goal(B)，不用移動，已"初次調整"，設定1~3號盤當前位置為 B柱，迴圈結束
(七) 主迴圈 i = 3：(現在1~3號都在 B柱)，
因為 plates[3] 的 now(B) != goal(A)，要移動，求出 temp = 6 - 2 - 1 = 3，已"初次調整"，設定1~2號盤當前位置為 B柱，遞迴呼叫(a2)
(1) hanoiArbitrarily(2, 3, true) ---(a2)
1~2號盤是完整子塔，1~2號都在 B要移動，移動 2號到 C，答案為 2^2 -1 = 3，回傳答案 3
( i = 3 )
答案 ans += 3，移動 3號，ans ++，迴圈結束
(八) 主迴圈 i = 2：(現在1~2號都在 C柱)，
因為 plates[2] 的 now(C) != goal(A)，要移動，求出 temp = 6 - 3 - 1 = 2，已"初次調整"，設定1號盤當前位置為 C柱，遞迴呼叫(a3)
(1) hanoiArbitrarily(1, 2, true) ---(a3)
此時 subDiscs 等於 1，因為 plates[1] 的 now(C) != target (B)，要移動，移動 1號到 target (B)
回傳答案 1
( i = 2 )
答案 ans += 1，移動 2號，ans ++，迴圈結束
(九) 主迴圈 i = 1：(現在1號在 B柱)，
因為 plates[1] 的 now(B) != goal(A)，要移動，求出 temp = 6 - 2 - 1 = 3，已"初次調整"，因為 i == 1，結束 if，答案 ans ++，迴圈結束
主迴圈結束，輸出答案 ans = 0 + (42+1) + (63+1) + 0 + 0 + 0 + (3+1) + (1+1) + 1 = 114
四：完整程式
上面的範例流程一定很難懂，所以在看的過程請配合下面程式
| import java.io.*; public class b592{ static BufferedReader buf = new BufferedReader(new InputStreamReader(System.in)); static final int DISC_MAX = 31;// DISC_MAX : 測資最大盤子數+1 static Disc_b592[] plates = new Disc_b592[DISC_MAX]; static int[] power2 = new int[DISC_MAX]; public static void main(String[] args) throws IOException { PrintWriter prt = new PrintWriter(new BufferedOutputStream(System.out)); int i, j; for(i=0 ; i < DISC_MAX ; i++) { plates[i] = new Disc_b592(-1, -1); power2[i] = 1 << i; } int n = nextInt(); int ans, temp, subTower; // subTower: 由 1~subTower的完整子塔，盤子連續無缺 boolean firstArbitrarilyToSubTower; // 經過第一次調整後存在最大子塔 => true while(n > 0) { for(i=1 ; i<=n ; i++) plates[i].now = nextInt(); for(i=1 ; i<=n ; i++) plates[i].goal = nextInt(); ans = 0; subTower = 1; // subTower要小於最大值減一，因最大值是測資最大盤子數加一 while(subTower < DISC_MAX-1 && plates[subTower].now == plates[subTower+1].now) { subTower++; } firstArbitrarilyToSubTower = false; for(i=n ; i>0 ; i--) { if(plates[i].now == plates[i].goal) { if(firstArbitrarilyToSubTower && i!=1) { for(j=i-1 ; j>0 ; j--) plates[j].moveTo(plates[i].now); } continue; } temp = 6 - plates[i].now - plates[i].goal; if(!firstArbitrarilyToSubTower) { if(subTower > i-1) subTower = i-1 ; ans += hanoiArbitrarily(i-1, temp, (subTower == i-1) ); firstArbitrarilyToSubTower = true; }else { if(i!=1) { for(j=i-1 ; j>0 ; j--) plates[j].moveTo(plates[i].now); ans += hanoiArbitrarily(i-1, temp, true); } } ans++; } prt.println(ans); n = nextInt(); } prt.flush(); } public static int hanoiArbitrarily(int subDiscs, int target, boolean isSubTower) { if(subDiscs == 0) return 0; if(subDiscs == 1) { if(plates[1].now != target) { plates[1].moveTo(target); return 1; } else return 0; } int steps = 0, substep = 0; int temp = 0; if(isSubTower) { boolean isfinish = true; for(int i=subDiscs ; i>0 ; i--) { if(plates[i].now != target) { isfinish = false; break; } } if(isfinish) { steps = 0; } else { plates[subDiscs].moveTo(target); steps = power2[subDiscs]-1; } } else if(plates[subDiscs].now != target) { temp = 6 - plates[subDiscs].now - target ; substep = hanoiArbitrarily(subDiscs-1, temp, isSubTower); plates[subDiscs].moveTo(target); steps = substep + 1 + (power2[subDiscs-1]-1); } else { steps = hanoiArbitrarily(subDiscs-1, target, isSubTower); } return steps; } public static int nextInt() throws IOException { int c = buf.read(); if(c == -1) return -1; while(c <= 32) c = buf.read(); int ans = 0; while(c > 32) { ans = ans*10 + c-'0'; c = buf.read(); } return ans; } } class Disc_b592 { int now; int goal; Disc_b592(int now, int goal){ this.now = now; this.goal = goal; } public void moveTo(int target) { now = target; } } |
----------------------------------------------------------------------------------------------------------------------------------------
我在建構程式流程時，腦袋很容易被混亂河內塔狀態搞暈，要親手把範例流程畫在紙上，一步一步去思考，從迷霧中探索道路，我的方法可能不是最好的，或許還有能進步的空間，但就目前為止我應該想不到遞迴以外的方法了。下面是類似題，核心思路不變。
這題要列印過程，所以每次遇到需要移動盤子的時機都要輸出，即便是搬完整塔也需要
這題只會輸入偶數盤，起點都在A柱，奇數編號盤都去B柱，偶數編號盤都去C柱，因此goal 自己設定
這題有一萬盤，遞迴有機會讓記憶體堆疊爆掉，因此不建議使用遞迴(反正我是通過了~)
達人
