河內塔

河內塔（中國大陸：漢諾塔，港台：河內塔）（Tower of Hanoi）是根據一個傳說形成的數學問題：

有三根杆子A，B，C。A杆上有 N 個 (N>1) 穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至 C 杆：

每次只能移動一個圓盤；
大盤不能疊在小盤上面。

提示：可將圓盤臨時置於 B 杆，也可將從 A 杆移出的圓盤重新移回 A 杆，但都必須遵循上述兩條規則。

問：如何移？最少要移動多少次？

這裏有河內塔在線頁面，可以來體驗河內塔，可以設置不同層數，也可以獲取最優移動提示解。該在線遊戲支持從任意初始狀態獲取最佳移動路徑。

傳說

最早發明這個問題的人是法國數學家愛德華·盧卡斯。

傳說越南河內某間寺院有三根銀棒，上串 64 個金盤。寺院裏的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要 $2^{64}-1$ 步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。

這個傳說有若干變體：寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜，其中一說是位於越南的河內，所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。

解答

如取 N=64，最少需移動 2⁶⁴−1 次。即如果一秒鐘能移動一塊圓盤，仍需 5849 億年。目前按照宇宙大爆炸理論的推測，宇宙的年齡僅為 137 億年。

在真實玩具中，一般 N=8；最少需移動 255 次。如果 N=10，最少需移動 1023 次。如果N=15，最少需移動32767次；這就是說，如果一個人從 3 歲到 99 歲，每天移動一塊圓盤，他最多僅能移動 15 塊。如果 N=20，最少需移動 1048575 次，即超過了一百萬次。

算法求解

解法的基本思想是遞迴。假設有 A、B、C 三個塔，A 塔有 $N$ 塊盤，目標是把這些盤全部移到 C 塔。那麼先把 A 塔頂部的 $N-1$ 塊盤移動到 B 塔，再把 A 塔剩下的大盤移到 C，最後把 B 塔的 $N-1$ 塊盤移到 C。

如此遞迴地使用下去，就可以求解。

遞迴解

在 Java語言中：

public class HW {
	public static java.util.Scanner sc = new java.util.Scanner(System.in);
	public static void Towers(int n,char a,char b,char c){
		if(n==1){
			System.out.println("移動"+n+"從"+a+"到"+c);
		}
		else{
			Towers(n-1,a,c,b);
			System.out.println("移動"+n+"從"+a+"到"+c);
			Towers(n-1,b,a,c);
		}
	}

	public static void main(String[] args) {
		int n = sc.nextInt();
		Towers(n,'A','B','C');
	}
}

以 C++ 語言實現：

#include <iostream>
using namespace std;

void Towers(int n,char a,char b,char c){
	if(n==1){
		cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
	}
	else{
		Towers(n-1,a,c,b);
		cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
		Towers(n-1,b,a,c);
	}
}
int main(int argc, char *argv[]) {
	int n;
	cin>>n;
	Towers(n,'A','B','C');
	cout<< endl;
	
	
}

以 Python 語言實現：

def hanoi(n, a, b, c):
	if n == 1:
		print(a, '-->', c)
	else:
		hanoi(n - 1, a, c, b)
		hanoi(1    , a, b, c)
		hanoi(n - 1, b, a, c)
# 调用
if __name__ == '__main__':
	hanoi(5, 'A', 'B', 'C')

以 Erlang 語言求解：

-module(hanoi).
-export([hanoi/1]).
hanoi(N) when N>0 ->
	do_hanoi({N, 1, 3}).

do_hanoi({0, _, _}) ->
	done;
do_hanoi({1, From, To}) ->
	io:format("From ~p, To ~p~n", [From, To]);
do_hanoi({N, From, To}) ->
	do_hanoi({N-1, From, by(From, To)}),
	do_hanoi({1, From, To}),
	do_hanoi({N-1, by(From, To), To}).

by(From, To) ->
	[Result|_] = [1, 2, 3] -- [From, To],
	Result.

以 Haskell 語言實現：

hanoi :: Integer -> String -> String -> String -> [(String, String)]
hanoi 0 _ _ _ = []
hanoi 1 from _ to = [(from, to)]
hanoi x from buffer to = 
    hanoi (x-1) from to buffer ++ hanoi 1 from buffer to ++ hanoi (x-1) buffer from to

任意初始結構（arbitrary initial configuration）的解法

為了從任意初始結構中找尋最佳解（optimal solution），其演算法可以一般化（be generalized）如下：

以 Scheme 語言表示：

 ; Let conf be a list of the positions of the disks in order of increasing size.
 ; Let the pegs be identified by the numbers 0, 1 and 2.
 (define (hanoi conf t)
  (let ((c (list->vector conf)))
   (define (move h f t)
    (vector-set! c h t)
    (printf "move disk ~s from peg ~s to peg ~s~n" h f t))
   (define (third-peg f t) (- 3 f t))
   (define (hanoi h t)
    (if (> h 0)
     (let ((h (sub1 h)))
      (let ((f (vector-ref c h)))
       (if (not (= f t))
        (let ((r (third-peg f t)))
         (hanoi h r)
         (move h f t)))
       (hanoi h t)))))
   (hanoi (vector-length c) t)))

在 Java語言中：

    
public class Hanoi {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(hanoiFunc(7));
	}

	public static int hanoiFunc(int i) {
		int sum = 0;

		if (i == 1) {
			sum += i;
		}

		else {
			sum = 2 * hanoiFunc(i - 1) + 1;
		}

		return sum;
	}
}

在 C語言中：

int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */

void move(int d, int t) {
    /* move disk d to peg t */
    conf[d] = t;
}

void hanoi(int h, int t) {
    if (h > 0) {
        int f = conf[h-1];
        if (f != t) {
            int r = 3 - f - t ;
            hanoi(h-1, r);
            move(h-1, t);
        }
        hanoi(h-1, t);
    }
}

圖像解釋

可以用無向圖來表示河內塔，在表示的時候會更加地直觀和清晰，雖然說理解上有一點難度。

現在規定，每一個節點表示盤子的位置一種可能性，每一條邊表示一種移動的方法。

註：這裏不考慮在兩個柱子之間的，沒有意義的，來回移動的情況。

對於只有一個盤子的河內塔，可以表示為：

一個盤子的情況

對於有兩個盤子的河內塔，可以表示為：

相互連接的三個三角形，組成了一個較大三角形的三個角。

每一個節點的第二個字母表示更大的盤子，且最初時沒有被移動。

對於每一個頂端的小三角形，表示兩個盤子的一種移動的方法：

兩個盤子的河內塔

外圍的三角形的每一個節點，表示在一個柱子上盤子的所有分佈可能。

對於 h+1 個盤子，就可以"複製" h 個盤子時候的三角形圖，然後拼成一個新的大三角形圖，稍微改動一下，

這個大的三角形圖就可以用來表示 h+1 個盤子時的情況了。

所以當有三個盤子時，圖形為：

三個盤子的河內塔

a、b 和 c 表示三個柱子

按照從小到大的順序，從左到右地列出的盤子的位置。

最外面的三角形的邊，表示了盤子從一個柱子移動到另一個柱子最快的方式。最大的三角形可以沿着中線分成三個次小的三角形，就是上面由二級的河內塔組成三級的河內塔的逆向操作，次小三角形相互之間的連線，表示着最大的盤子的移動方式。

同理，在這次三角形的也可以沿其中線分割成為三個次次三角形，一樣的，次次小三角形相互之間的連線，表示着次大的盤子的移動方式。繼續下去，也就可以表示出一個河內塔的移動方式。

具有七個盤子的河內塔的圖與七級的謝爾賓斯基三角形的聯繫

通常，對於具有 n 個盤子的圖，有 $3^{n}$ 個節點；每個節點都有三條邊連接着其他節點，但是在頂點的的節點只卻只有有兩條邊連接着其他節點。所以說總是下都可以將最小的盤子移動到另外兩個柱子中的一個，對於多數情況，是可以在兩個柱子間移動一個盤子，除了所有的盤子都在一個柱子上。邊角的節點表示着所有的盤子都在一個柱子的情況，即可以在 a， b 或 c 柱上堆滿盤子，顯然只要三種。對於 $n+1$ 個盤子的圖，可以通過表示 $n$ 給盤子的圖 "複製" 三份，組合在一起的。因此也就很方便地表示了每一層的河內塔移動方式，每一個次小的三角形表示次小的盤子的所有可能的移動方式和放置狀態，次小的三角形之間的連接表示了大盤子的三種可能的移動方式。所以圖形有 $3^{n}+1$ 個節點，基本都有三個與之相連接的邊，而頂點只有兩個。

在盤子數比較多的時候，河內塔的圖像就會開始和分形圖比較相似了。

如果使用最麻煩的移動方式，即不走重複的路(移動方式)，需要 $3^{64}-1$ 次移動，每秒移動一次，需要的時間超過 $10^{23}$ 年。

在不考慮重複使用路徑的情況下，去除掉沒有經過的邊，就可以表示出當有三個盤子時的最長路徑。

就是沒有去做無意義 (多餘的) 的，將一個盤子在兩個柱子間瘋狂來回移動的情況下，去除沒有使用的移動方法，就可以得到當有三個盤子時的最麻煩的移動方式

三個盤子的河內塔 - 通路

順便一提，這個最長的非重複路徑，可以通過清除掉從 a 到 b 的路徑得到。

也可以得出三個盤子的河內塔圖的哈密頓迴路：

三個盤子的河內塔的哈密頓迴路

該圖較為清楚地表達了：

對於任意的全部盤子在一根柱子的情況下，將所有盤子移動到另一個柱子的最短路徑只有一個。
對於任意的兩個盤子分佈情況之間轉換的時候，只有一個或者兩個不同的最短路徑。
對於任意的盤子分佈情況，都有一個或者兩個將所有盤子移動到任意一個柱子上的最長不相交路徑。
對於任意的兩個盤子分佈情況之間轉換的時候，只有一個或者兩個不同的最長不相交路徑。
設 $N_{h}$ 是將有 $h$ 個盤子的塔，將所有盤子從一個柱子移動到另一個柱子的非相交路徑的數量(一開始盤子都在一個柱子上)。可以得出：
- $N_{1}=1$ N 1 = 2，
- $N_{h+1}=(N_{h})^{2}+(N_{h})^{3}$ 。

這裏的 $N_{h}\in \{2,12,1872,6563711232,....\}$ ，詳細在 A125295上。

多塔河內塔問題

在有 3 個柱子時，所需步數的公式較簡單，但對於 4 個柱子以上時，情形複雜許多。Frame 及 Stewart 在 1941年時分別提出了基本上相同的一套演算法^[1]，Bousch 則在 2014年證明了Frame-Stewart演算法在 4 個柱子時就是最佳解^[2]，但此演算法在 5 個柱子以上是否是最佳解仍是未知。

Frame-Stewart 演算法本質上也是遞迴的，可簡單敘述如下：

令 $f(n,k)$ 為在有 $k$ 個柱子時，移動n個圓盤到另一柱子上需要的步數，則：

對於任何移動方法，必定會先將

m(1\leq m\leq n-1)

個圓盤移動到一個中間柱子上，再將第

n

到第

n-m

個圓盤通過剩下的

k-1

個柱子移到目標柱子上，最後將

m

個在中間柱子上的圓盤移動到目標柱子上。這樣所需的操作步數為

2f(m,k)+f(n-m,k-1)

。

進行最優化，易得：

f(n,k)=\mathrm {min} _{m\in [1,n-1]}\;(2f(m,k)+f(n-m,k-1))

。

流行文化

2011年電影《猿人爭霸戰：猩凶革命》曾出現河內塔以測試猩猩的智商。其後續電影《猿人爭霸戰：猩凶革命2》中也有類似的場景。

參見

參考來源

^ Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268. doi:10.2307/2304268.
^ Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21: 895–912.

外部連結

[1] Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268. doi:10.2307/2304268.

[2] Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21: 895–912.

[1]

[2]