Python用初學者的角度詳解遞回河塔內(Hanoi Tower)
圖翻拍自網路
河內塔是一個經典的益智遊戲,也是算法和遞歸函數的經典範例之一。以下是一個初學者友好的 Python 實現:
def hanoi(n, source, target, auxiliary):
if n > 0:
# 將 n-1 個盤子從源柱移動到輔助柱
hanoi(n-1, source, auxiliary, target)
# 將源柱上最後一個盤子移動到目標柱
print("Move disk", n, "from", source, "to", target)
# 將 n-1 個盤子從輔助柱移動到目標柱
hanoi(n-1, auxiliary, target, source)
這個程式中,hanoi
函數接受四個參數:n 是盤子的數量,source 是源柱,target 是目標柱,auxiliary 是輔助柱。遞迴地調用 hanoi 函數,將 n-1 個盤子從源柱移動到輔助柱,然後將源柱上最後一個盤子移動到目標柱,最後再將 n-1 個盤子從輔助柱移動到目標柱。
讓我們來看一個示例,假設有三個柱子,起始狀態如下(盤子從大到小編號為 1、2、3):
source: [3, 2, 1]
auxiliary: []
target: []
我們可以呼叫 hanoi 函數來解決這個問題:
hanoi(3, 'source', 'target', 'auxiliary')
這會產生以下輸出:
Move disk 1 from source to target
Move disk 2 from source to auxiliary
Move disk 1 from target to auxiliary
Move disk 3 from source to target
Move disk 1 from auxiliary to source
Move disk 2 from auxiliary to target
Move disk 1 from source to target
最終狀態如下:
source: []
auxiliary: []
target: [3, 2, 1]
這段程式碼實現了遞迴算法,因此它非常簡潔、易於理解。如果你需要更多關於河內塔問題的資訊,可以參考維基百科。
到訪人數:(226)