Python如何解決Hanoi塔問題

# Python如何解決Hanoi塔問題

## 引言

漢諾塔（Hanoi Tower）是經典的遞歸算法問題，源自法國數學家愛德華·盧卡斯在1883年提出的一個數學謎題。它不僅是一個有趣的智力游戲，更是計算機科學中遞歸思想的經典案例。本文將詳細介紹如何使用Python解決漢諾塔問題，并深入探討其背后的算法原理。

## 漢諾塔問題描述

漢諾塔問題包含以下要素：
- **三根柱子**：通常標記為A（起始柱）、B（輔助柱）、C（目標柱）
- **n個圓盤**：大小各不相同，最初全部疊放在柱子A上
- **規則**：
  1. 每次只能移動一個圓盤
  2. 移動時，大圓盤不能放在小圓盤上面
  3. 所有圓盤最終要移動到柱子C

## 遞歸解法原理

### 基本思路
當圓盤數量為n時，解決步驟可分為三個階段：
1. 將前n-1個圓盤從A移動到B（借助C）
2. 將第n個（最大的）圓盤從A直接移動到C
3. 將n-1個圓盤從B移動到C（借助A）

### 數學證明
移動次數滿足遞推關系：  
T(n) = 2T(n-1) + 1  
其解為T(n) = 2^n - 1，說明漢諾塔問題的時間復雜度為O(2^n)

## Python實現

### 基礎遞歸實現
```python
def hanoi(n, source, target, auxiliary):
    """
    :param n: 圓盤數量
    :param source: 起始柱
    :param target: 目標柱
    :param auxiliary: 輔助柱
    """
    if n == 1:
        print(f"移動圓盤 1 從 {source} 到 {target}")
    else:
        hanoi(n-1, source, auxiliary, target)
        print(f"移動圓盤 {n} 從 {source} 到 {target}")
        hanoi(n-1, auxiliary, target, source)

# 示例：3個圓盤的情況
hanoi(3, 'A', 'C', 'B')

可視化改進版

def hanoi_visual(n, source, target, auxiliary, tower_states):
    if n > 0:
        # 移動n-1個圓盤到輔助柱
        hanoi_visual(n-1, source, auxiliary, target, tower_states)
        
        # 執行移動
        disk = tower_states[source].pop()
        tower_states[target].append(disk)
        print(f"移動圓盤 {disk} 從 {source} 到 {target}")
        print_state(tower_states)
        
        # 移動n-1個圓盤到目標柱
        hanoi_visual(n-1, auxiliary, target, source, tower_states)

def print_state(towers):
    for pole in towers:
        print(f"{pole}: {towers[pole]}")
    print("---")

# 初始化塔狀態
towers = {'A': [3, 2, 1], 'B': [], 'C': []}
hanoi_visual(3, 'A', 'C', 'B', towers)

算法優化與變種

非遞歸實現（棧模擬）

def hanoi_iterative(n, source, target, auxiliary):
    stack = [(n, source, target, auxiliary)]
    while stack:
        n, s, t, a = stack.pop()
        if n == 1:
            print(f"移動圓盤 1 從 {s} 到 {t}")
        else:
            # 注意壓棧順序與遞歸調用相反
            stack.append((n-1, a, t, s))
            stack.append((1, s, t, a))
            stack.append((n-1, s, a, t))

最少步數驗證

def validate_hanoi(n):
    expected = (2 ** n) - 1
    count = [0]  # 使用列表實現可變對象的引用
    
    def wrapped_hanoi(*args):
        count[0] += 1
        hanoi(*args)
    
    wrapped_hanoi(n, 'A', 'C', 'B')
    assert count[0] == expected
    print(f"驗證通過！總步數：{count[0]}（預期：{expected}）")

validate_hanoi(4)

教學應用建議

1. 理解遞歸：通過漢諾塔問題演示函數調用棧
2. 算法分析：
   • 時間復雜度：O(2^n)
   • 空間復雜度：O(n)（遞歸深度）
3. 擴展思考：
   • 如果增加柱子數量如何優化？
   • 限制特定移動規則時的解法變化

常見問題解答

Q1：為什么必須使用遞歸？

A：遞歸天然符合問題分解的特性，但也可以用棧結構實現非遞歸解法。

Q2：n較大時程序會卡死嗎？

A：當n>20時，移動次數超過百萬，確實會消耗大量時間，這是指數時間復雜度的典型特征。

Q3：如何記錄移動路徑？

def hanoi_with_path(n):
    path = []
    def _hanoi(n, s, t, a):
        if n == 0: return
        _hanoi(n-1, s, a, t)
        path.append(f"{s}->{t}")
        _hanoi(n-1, a, t, s)
    _hanoi(n, 'A', 'C', 'B')
    return path

print(hanoi_with_path(3))  # 輸出：['A->C', 'A->B', 'C->B', ...]

結語

漢諾塔問題通過簡單的規則展現了遞歸算法的精妙之處。Python憑借清晰的語法特性，成為展示這一經典問題的理想語言。理解這個算法不僅有助于掌握遞歸思想，更能培養計算思維中的問題分解能力。讀者可以嘗試進一步實現圖形化界面或探索多柱漢諾塔等變種問題。

知識擴展：漢諾塔問題與格雷碼、二叉樹遍歷等算法存在深刻聯系，在計算機科學數學基礎中具有重要意義。 “`