河內塔 C++範例代碼 非遞迴詳細解說
玩法與規則
非遞迴解解法
再來直接進入主題,這個解法是直接看規則得出來的可能跟其他正規的解法不太一樣。
首先把這三個柱子分成 0 1 2 編號,並且制定的一些規則。
這張圖先看一眼,下面會解說上面的含意。
移動相關的說明
先說明移動的規則,這也是整個代碼最核心的部分。
以下的說明如果提到 無法移動
就是違反這些規則了。
只能把小的疊在大的上面
遊戲本身的規則。不一定要差1,可以把1疊到3上面。
不要重複上一步驟
這很直覺的別做沒有意義的行為,犯傻進入無限迴圈。
發牌
指從 [0柱] 移動到 [1柱] 或 [2柱] 的意思。
具體移動到哪個一個依據下面的情況 ,依據階層有不同的順序。
階層指的時候一開始的時候玩幾個盤子。
先發哪一柱會影響最後完成的柱在哪裡。依照底下規則可以保證完成柱在[2柱]
- 奇數階層:每一次發牌的時候優先發[2柱]
- 偶數階層:每一次發牌的時候優先發[1柱]
如果無法移動
才發到另一柱,比如說奇數階層的時候,發牌無法發到2柱,那就往1柱發。
然後這裡有一點要注意的規則
就是說你發的時候要檢查一下,上一步有沒有收過牌
不管是從 [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柱中,小的那個收回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 "沒有動作";
}
}
}