漢諾塔雜談（三）——非遞歸演算法

05-19

漢諾塔雜談（三）——非遞歸演算法

來自專欄 Liu言雜記

下面介紹 $n$ 個盤子的漢諾塔的非遞歸演算法：

1. 將三根柱子按順序排成品字型，若 $n$ 為偶數，按順時針方向依次擺放A、B、C；若 $n$ 為奇數，按順時針方向依次擺放A、C、B。

2. 把圓盤1從現在的柱子移動到順時針方向的下一根柱。

3. 接著，把另外兩根柱上可以移動的圓盤移動到新的柱上（事實上只有唯一的選擇）。

4. 如果沒有達到目標要求，則返回步驟2。

例如下圖是 $n=3$ 的情況：

由二進位也可以得到 $n$ 個盤子的漢諾塔的非遞歸演算法：

對於有 $n$ 個盤子的漢諾塔問題，按序寫出所有 $n$ 位普通二進位碼 $B_nB_{n-1}…B_2B_1$ ，自左而右標記為第 $n$ 位、第 $n-1$ 位、…第2位、第1位。則 $min(k|i=B_nB_{n-1}…B_2B_1，B_k=1)$ 表示第 $i$ 步移動 $k$ 號盤子。

對於最小的盤子而言，總是有兩種移動的可能性。若 $n$ 為偶數，最小的盤子的移動次序是A→B→C→A→…；若 $n$ 為奇數，最小的盤子的移動次序是A→C→B→A→…。
對於其他盤子，總是有唯一的移動可能性。

$n=4$ 的情況見下表。

在Mathematica中有一個函數「IntegerExponent」，官方的幫助給出的說明是：

IntegerExponent[n, b] gives the highest power of b that divides n.

就是返回能整除 $n$ 的（大於1的整數） $b$ 的最高次冪。例如：

說明 $3^3|432$ 而 $3^4 mid 432$ 。

於是在Mathematica中，輸入「IntegerExponent [Range[2^n - 1], 2] + 1」可以得到 $n$ 個盤子的漢諾塔問題依次移動的盤子的號碼。

例如：

具體移動方法同前。

由格雷碼也可以得到一個非遞歸演算法，這部分內容我將放在下一篇中介紹。

此外，假設 $m$ 的二進位表示為 $B_nB_{n-1}…B_2B_1$ ，則可以由 $B_nB_{n-1}…B_2B_1$ 得到移動 $m$ 步後 $n$ 個盤子在3個柱的分布情況，這一部分也將在下一篇中介紹。

（注意到格雷碼與普通二進位碼的轉換關係，則可以將 $m$ 的二進位表示轉換為 $m$ 對應的格雷碼）。