河內塔 C++範例代碼非遞迴詳細解說

玩法與規則

河內塔的玩法與規則詳細可以簡單看一下這一篇，裡面也有三階如何破關的演示。
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柱] 移動到 [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 "沒有動作";
                }
            }
        }

代碼可以參考我的github
https://github.com/hunandy14/Hanoi

CHG

2020年9月6日星期日