圖翻拍自網路

故事起源：

1883 年，一位法國的數學家 Edouard Lucas 教授在歐洲的一份雜誌上介紹了一個相當吸引人的難題──迷人的智力遊戲。這個遊戲名為河內塔(Tower of Hanoi)。

源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令和尚們把圓盤從下面開始按大小順序重新擺放在另一根柱子上。

不過在移動時，有兩項規則：第一：較大的金盤不能放在較小的金盤上。第二、一次只能移動一個金盤。

直到，和尚們能將 64 片的金屬圓盤依規則從指定的柱子上全部移動至另一根柱子上，那麼，世界末日即隨之來到。

抽象為數學問題

如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數。

問題分析

當n == 1時，

1. A—->C sum = 1 次

當n == 2時，

1. A—->B

2. A—->C

3. B—->C sum = 3 次

當n == 3時，

1. A—->C

2. A—->B

3. C—->B

4. A—->C

5. B—->A

6. B—->C

7. A—->C sum = 7 次

不難發現規律：移動次數為：2^n – 1

遞歸算法

實現這個算法可以簡單分為三個步驟：

1. 把n-1個盤子由A 移到 B；
2. 把第n個盤子由 A移到 C；
3. 把n-1個盤子由B 移到 C；

python解河內塔語法撰寫：[注意實參和形參]

用python方法調用，實現輸入圓盤數，列印移動的過程

程序執行的結果：

程序分析：

涉及到遞歸函數，理解起來會容易凌亂，我們以3個盤子為例，進行執行步驟分析。

希望本文所述對大家Python程序設計有所幫助！

到訪人數：(777)