河內塔 C++範例代碼 非遞迴詳細解說
玩法與規則
河內塔的玩法與規則詳細可以簡單看一下這一篇，裡面也有三階如何破關的演示。
https://sites.google.com/a/g2.nctu.edu.tw/unimath/2017-11/Hanoi
https://sites.google.com/a/g2.nctu.edu.tw/unimath/2017-11/Hanoi
非遞迴解解法
再來直接進入主題，這個解法是直接看規則得出來的可能跟其他正規的解法不太一樣。
首先把這三個柱子分成 0 1 2 編號，並且制定的一些規則。
這張圖先看一眼，下面會解說上面的含意。
這張圖先看一眼，下面會解說上面的含意。
移動相關的說明
先說明移動的規則，這也是整個代碼最核心的部分。
以下的說明如果提到
以下的說明如果提到
無法移動 就是違反這些規則了。- 只能把小的疊在大的上面遊戲本身的規則。不一定要差1，可以把1疊到3上面。
- 不要重複上一步驟這很直覺的別做沒有意義的行為，犯傻進入無限迴圈。
發牌
指從 [0柱] 移動到 [1柱] 或 [2柱] 的意思。
具體移動到哪個一個依據下面的情況 ，依據階層有不同的順序。
階層指的時候一開始的時候玩幾個盤子。
階層指的時候一開始的時候玩幾個盤子。
先發哪一柱會影響最後完成的柱在哪裡。依照底下規則可以保證完成柱在[2柱]
- 奇數階層：每一次發牌的時候優先發[2柱]
- 偶數階層：每一次發牌的時候優先發[1柱]
如果
無法移動才發到另一柱，比如說奇數階層的時候，發牌無法發到2柱，那就往1柱發。
然後這裡有一點要注意的規則
- <收牌>後不可以再<發牌>
就是說你發的時候要檢查一下，上一步有沒有收過牌
不管是從 [1柱] 或 [2柱] 收回來的都算。
不管是從 [1柱] 或 [2柱] 收回來的都算。
收牌
指從 [1柱] 或 [2柱] 移動到 [0柱] 的意思。
組牌
當 [1柱] 和 [2柱] 最頂層的絕對差值等於1的時候，把小的疊到大的上面去。
核心算法
有了前面的理解之後接下來是如何解題的算法，如果你把它看懂了可以嘗試實際去玩玩，我也建議實際玩過幾輪再開始寫，可以更深刻的理解。照著下面的規則走，可以走出最少步驟。
最少步數
最小步數是 2的N次方-1，如果是只玩3層那就是 2的三次方-1=7，依此類推。
知道最多走幾步，也就是什麼時候結束，這可以用來設置迴圈上限。
知道最多走幾步，也就是什麼時候結束，這可以用來設置迴圈上限。
條件
總共就分3個條件走，其中只要有任一個條件成立，移動完畢，就回頭重第一個條件重新跑過。
- 發牌
- 組牌
- 處理1柱和2柱
前兩個很容易，只要注意有沒有採到移動的規則就好。
第三個比較麻煩一點以下詳細說明
第三個比較麻煩一點以下詳細說明
先知道當前1柱和2柱最層的大小，兩個大小的差值是基數還有偶數
基本這個數會大於1因為步驟2組起來了，但也有等於1的時候 (如底下實例中的第[10]步)
發生在組牌的時候正好踩到移動的限制，重複上一步驟。
基本這個數會大於1因為步驟2組起來了，但也有等於1的時候 (如底下實例中的第[10]步)
發生在組牌的時候正好踩到移動的限制，重複上一步驟。
如果差值是奇數
- 把1柱和2柱中，小的那個收回0柱。
- 如果上面步驟重上一步，複無法移動，則把大數收回。
如果差值是偶數
- 把小的疊到大數上
- 如果上面步驟重複上一步，無法移動，則把大數收回。
就照這幾個條件一直走下去，可以破關了。
實際演示
這是跑出來的實際步驟，可以對照著看上面的規則。
[0] 4, 3, 2, 1,
[1]
[2]
[step:0]--------init
---------------------------
[0] 4, 3, 2,
[1] 1,
[2]
[step:1]--------發牌
---------------------------
[0] 4, 3,
[1] 1,
[2] 2,
[step:2]--------發牌
---------------------------
[0] 4, 3,
[1]
[2] 2, 1,
[step:3]--------組牌
---------------------------
[0] 4,
[1] 3,
[2] 2, 1,
[step:4]--------發牌
---------------------------
[0] 4, 1,
[1] 3,
[2] 2,
[step:5]--------牌值差雙
---------------------------
[0] 4, 1,
[1] 3, 2,
[2]
[step:6]--------組牌
---------------------------
[0] 4,
[1] 3, 2, 1,
[2]
[step:7]--------發牌
---------------------------
[0]
[1] 3, 2, 1,
[2] 4,
[step:8]--------發牌
---------------------------
[0]
[1] 3, 2,
[2] 4, 1,
[step:9]--------牌值差單
---------------------------
[0] 2,
[1] 3,
[2] 4, 1,
[step:10]--------牌值差單
---------------------------
[0] 2, 1,
[1] 3,
[2] 4,
[step:11]--------牌值差雙
---------------------------
[0] 2, 1,
[1]
[2] 4, 3,
[step:12]--------組牌
---------------------------
[0] 2,
[1] 1,
[2] 4, 3,
[step:13]--------發牌
---------------------------
[0]
[1] 1,
[2] 4, 3, 2,
[step:14]--------發牌
---------------------------
[0]
[1]
[2] 4, 3, 2, 1,
[step:15]--------組牌
---------------------------
程式碼解析
基本上就是把上面的文字寫成代碼而已，可以注意看if else的階層，判斷邏輯會比較清楚。
for (int i = 0; i < step_min; ++i) {
int step = i+1;
// 發牌
if (sent()) {
print("發牌", step);
// 組牌
} else if (defrag()) {
print("組牌", step);
} else {
int diff = abs(p[1] - p[2]);
// 牌值差雙
if (diff % 2 == 0 and adju_even()) {
print("牌值差雙", step);
}
// 牌值差單
else if (diff % 2 == 1 and adju_odd()) {
print("牌值差單", step);
} else {
throw "沒有動作";
}
}
}
代碼可以參考我的github
https://github.com/hunandy14/Hanoi
https://github.com/hunandy14/Hanoi
