C2: 海王星深度探索：遞迴與回溯法

海王星的衛星系統極為複雜，有 14 顆已知衛星。探索這些衛星需要系統性地搜索所有可能的路徑。這時候，「遞迴」和「回溯」就是你最強大的工具！

遞迴就像俄羅斯套娃：大問題包含小問題，小問題又包含更小的問題，直到問題小到可以直接解決。

什麼是遞迴？

遞迴是函數呼叫自己的過程。每個遞迴函數都需要：

1. 基礎情況（Base Case）：遞迴的終止條件
2. 遞迴步驟（Recursive Step）：將問題分解為更小的子問題

def countdown(n):
    if n == 0:  # 基礎情況
        print("發射！")
        return
    print(n)
    countdown(n - 1)  # 遞迴步驟

遞迴的思維模式

信念飛躍（Leap of Faith）：相信函數對更小的問題能正確運作。

# 計算階乘：n! = n × (n-1)!
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # 相信 factorial(n-1) 是正確的

什麼是回溯法？

回溯法是一種系統性搜索所有可能解的方法：

1. 做出選擇
2. 遞迴探索
3. 撤銷選擇（回溯）

就像在迷宮中探索：走到死路就退回來，嘗試另一條路。

回溯模板

result = []
def backtrack(path, choices):
    # 1. 檢查是否找到解
    if is_solution(path):
        result.append(path.copy())
        return
    
    # 2. 剪枝（可選）
    if cannot_be_solution(path):
        return
    
    # 3. 嘗試所有選擇
    for choice in choices:
        # 做出選擇
        path.append(choice)
        
        # 遞迴探索
        backtrack(path, new_choices)
        
        # 撤銷選擇
        path.pop()

範例 1：階乘計算（基礎遞迴）

import sys
def factorial(n):
    """計算 n 的階乘"""
    # 基礎情況
    if n == 0 or n == 1:
        return 1
    
    # 遞迴步驟
    return n * factorial(n - 1)
# 任務：計算火箭推進器配置數量
n = int(sys.stdin.readline())
result = factorial(n)
print(f"{n}! = {result}")
print(f"共有 {result} 種配置方式")

範例 2：費波那契數列

import sys
def fibonacci(n):
    """計算第 n 個費波那契數"""
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
# 優化版本：使用記憶化
memo = {}
def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    
    if n <= 1:
        return n
    
    memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
    return memo[n]
# 任務：計算軌道共振週期
n = int(sys.stdin.readline())
print(f"第 {n} 個費波那契數：{fibonacci_memo(n)}")

範例 3：生成所有排列（回溯法）

import sys
def permutations(arr):
    """生成陣列的所有排列"""
    result = []
    
    def backtrack(path, remaining):
        # 基礎情況：沒有剩餘元素
        if not remaining:
            result.append(path.copy())
            return
        
        # 嘗試每個剩餘元素
        for i in range(len(remaining)):
            # 選擇
            path.append(remaining[i])
            new_remaining = remaining[:i] + remaining[i+1:]
            
            # 遞迴
            backtrack(path, new_remaining)
            
            # 撤銷
            path.pop()
    
    backtrack([], arr)
    return result
# 任務：生成太空船編隊的所有排列
n = int(sys.stdin.readline())
ships = list(range(1, n + 1))
all_perms = permutations(ships)
print(f"太空船數量：{n}")
print(f"可能的編隊方式：{len(all_perms)} 種")
print("\n前 10 種編隊：")
for i, perm in enumerate(all_perms[:10]):
    print(f"{i+1}. {perm}")

範例 4：N 皇后問題

import sys
def solve_n_queens(n):
    """解決 N 皇后問題"""
    result = []
    board = [['.'] * n for _ in range(n)]
    
    def is_safe(row, col):
        """檢查在 (row, col) 放置皇后是否安全"""
        # 檢查同一列
        for i in range(row):
            if board[i][col] == 'Q':
                return False
        
        # 檢查左上對角線
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1
        
        # 檢查右上對角線
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1
        
        return True
    
    def backtrack(row):
        # 基礎情況：所有行都放置完成
        if row == n:
            result.append([''.join(row) for row in board])
            return
        
        # 嘗試在當前行的每一列放置皇后
        for col in range(n):
            if is_safe(row, col):
                # 放置皇后
                board[row][col] = 'Q'
                
                # 遞迴處理下一行
                backtrack(row + 1)
                
                # 撤銷
                board[row][col] = '.'
    
    backtrack(0)
    return result
# 任務：在 N×N 的太空站網格中放置 N 個防禦塔
n = int(sys.stdin.readline())
solutions = solve_n_queens(n)
print(f"網格大小：{n}×{n}")
print(f"找到 {len(solutions)} 種配置方案")
if solutions:
    print("\n第一種方案：")
    for row in solutions[0]:
        print(row)

範例 5：子集生成（組合問題）

import sys
def subsets(nums):
    """生成所有子集"""
    result = []
    
    def backtrack(start, path):
        # 每個狀態都是一個有效的子集
        result.append(path.copy())
        
        # 嘗試添加後續元素
        for i in range(start, len(nums)):
            # 選擇
            path.append(nums[i])
            
            # 遞迴（注意：從 i+1 開始，避免重複）
            backtrack(i + 1, path)
            
            # 撤銷
            path.pop()
    
    backtrack(0, [])
    return result
# 任務：選擇要探索的衛星組合
n = int(sys.stdin.readline())
satellites = list(range(1, n + 1))
all_subsets = subsets(satellites)
print(f"衛星總數：{n}")
print(f"可能的探索組合：{len(all_subsets)} 種")
print("\n所有組合：")
for i, subset in enumerate(all_subsets):
    if subset:
        print(f"{i}. 探索衛星 {subset}")
    else:
        print(f"{i}. 不探索任何衛星")

關鍵技術點

1. 遞迴的執行過程

   factorial(3)
   = 3 * factorial(2)
   = 3  (2  factorial(1))
   = 3  (2  1)
   = 3 * 2
   = 6
   

1. 記憶化的重要性

   # 沒有記憶化：fibonacci(5) 會重複計算很多次
   fib(5)
   ├─ fib(4)
   │  ├─ fib(3)
   │  │  ├─ fib(2)  ← 重複
   │  │  └─ fib(1)
   │  └─ fib(2)     ← 重複
   └─ fib(3)        ← 重複
      ├─ fib(2)
      └─ fib(1)
   
   # 有記憶化：每個值只計算一次
   

1. 回溯的「選擇-探索-撤銷」模式

   # 生成 [1,2,3] 的排列
   []
   ├─ [1]
   │  ├─ [1,2]
   │  │  └─ [1,2,3] ✓
   │  └─ [1,3]
   │     └─ [1,3,2] ✓
   ├─ [2]
   │  └─ ...
   └─ [3]
      └─ ...
   

1. 剪枝優化

   # N 皇后問題中的剪枝
   if not is_safe(row, col):
       continue  # 跳過這個選擇，不需要遞迴