115 年 國立中山大學資訊工程學系資訊安全碩士班《離散數學與演算法》

核心觀念

題目要求將以 $64$ 為基底表示的正整數，轉換成十進位。核心公式是位值展開：

$$(d_{n-1}d_{n-2}\cdots d_1d_0)_{64} = \sum_{i=0}^{n-1} d_i \times 64^i$$

其中每個符號所代表的數值必須先定義。採用常見的 Base64 字元對應：

字元	數值
0～9	$0$～$9$
A～Z	$10$～$35$
a～z	$36$～$61$
+	$62$
/	$63$

因此，輸入字串從左至右，每讀入一個數字，就將目前結果乘以 $64$，再加上新讀入的數值。

解題方法：Horner 法

直接依照位值展開計算，需要計算 $64^0,64^1,\ldots$。較有效率的方式是使用 Horner 法逐位累積。

若目前已處理的數值為 $value$，下一個字元的數值為 $d$，則更新為：

$$value \leftarrow value \times 64+d$$

例如輸入 2A7：

1. 初始值：

$$value=0$$

2. 讀入 2，其數值為 $2$：

$$value=0\times64+2=2$$

3. 讀入 A，其數值為 $10$：

$$value=2\times64+10=138$$

4. 讀入 7，其數值為 $7$：

$$value=138\times64+7=8839$$

因此：

$$(2A7)_{64}=8839_{10}$$

演算法

輸入一個由 Base64 字元組成的字串 s，依序執行：

1. 將目前結果 value 設為 $0$。
2. 由左至右讀取每個字元。
3. 將字元轉換成 $0$ 至 $63$ 的數值。
4. 執行 value = value * 64 + digit。
5. 所有字元處理完後輸出 value。

關鍵程式碼

核心觀念

1. 笛卡兒積（Cartesian Product）
   設 $A, B$ 為兩集合，其笛卡兒積定義為：
   $A \times B = \{(a, b) \mid a \in A \land b \in B\}$
   若 $|A| = m$ 且 $|B| = n$，則笛卡兒積的元素個數為 $|A \times B| = m \cdot n$。

2. 二元關係（Binary Relation）

   • 從 $A$ 到 $B$ 的二元關係：任何笛卡兒積 $A \times B$ 的子集合 $R \subseteq A \times B$ 均稱為從 $A$ 到 $B$ 的二元關係。其關係總個數為 $2^{|A \times B|} = 2^{m \cdot n}$。
   • 在 $A$ 上的二元關係：當目標集合 $B = A$ 時，任何子集合 $R \subseteq A \times A$ 稱為在集合 $A$ 上的二元關係。其關係總個數為 $2^{|A \times A|} = 2^{m^2}$。

3. 空關係（Empty Relation）與非空關係（Nonempty Relation）

   • 空關係：不包含任何序對的關係，即外延（Extension）為空集合的關係 $R = \emptyset \subseteq A \times B$。在集合論中，空集是唯一的；但在邏輯與離散數學中，可透過不同的謂詞條件（Predicate）來定義出外延皆為空集的空關係。
   • 非空關係：包含至少一個序對的關係，即 $R \subseteq A \times A$ 且 $R \neq \emptyset$。

---

解題方法

已知集合 $A = \{2, 3, 4, 6\}$（元素個數 $|A| = 4$）與集合 $B = \{1, 3, 7, 8\}$（元素個數 $|B| = 4$）。

(a) 設計 4 個從 $A$ 到 $B$ 的空關係

從 $A$ 到 $B$ 的關係定義在笛卡兒積 $A \times B$ 上。
分析元素邊界條件：

• $a \in A \implies 2 \le a \le 6$
• $b \in B \implies 1 \le b \le 8$
• 和的範圍：$a + b$ 最小值為 $2 + 1 = 3$，最大值為 $6 + 8 = 14$。
• 差的範圍：$a - b$ 最小值為 $2 - 8 = -6$，最大值為 $6 - 1 = 5$。
• 積的範圍：$a \cdot b$ 最小值為 $2 \cdot 1 = 2 > 0$。

只要建構 4 個定義於 $A \times B$ 上且沒有任何序對 $(a, b)$ 能滿足的謂詞條件，即可獲得 4 個空關係。

(b) 設計 4 個在 $A$ 上的非空關係

在 $A$ 上的關係定義在笛卡兒積 $A \times A$ 上，其中 $|A \times A| = 4 \times 4 = 16$。
在 $A$ 上的非空關係共有 $2^{16} - 1 = 65,535$ 種。可選取 4 個具備明確數學特徵且互不相同的非空子集作為範例。

---

子題詳細分析

(a) 從 $A$ 到 $B$ 的 4 個空關係分析

1. 關係 $R_1 = \{(a, b) \in A \times B \mid a + b > 14\}$

   • 說明：在 $A \times B$ 中，$a$ 的最大值為 $6$，$b$ 的最大值為 $8$，兩者相加最大值僅為 $14$。沒有任何序對 $(a, b) \in A \times B$ 滿足 $a + b > 14$，故 $R_1 = \emptyset$。

2. 關係 $R_2 = \{(a, b) \in A \times B \mid a = b + 10\}$

   • 說明：由於 $a \le 6$ 且 $b \ge 1$，$a - b$ 的最大差值僅為 $5$，不可能等於 $10$。沒有任何序對滿足此條件，故 $R_2 = \emptyset$。

3. 關係 $R_3 = \{(a, b) \in A \times B \mid a \cdot b = 0\}$

   • 說明：集合 $A$ 與集合 $B$ 均不包含 $0$，任意 $a \in A, b \in B$ 的乘積最小為 $2 > 0$。

核心觀念

1. 算術基本定理（Prime Factorization）：任一大於 1 的正整數均可唯一表示為質因數的次方乘積：
   $N = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$
2. 正因數個數公式：正整數 $N$ 的正因數總個數為：
   $d(N) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$
3. 二因子無序分解（Two-Factor Unordered Factorization）：將 $N$ 表示為 $a \times b$（其中 $a, b > 1$ 且不計順序 $\{a, b\} = \{b, a\}$）。若 $N$ 非完全平方數，則因子均大於 1 的二因子無序分解數為：
   $\frac{d(N)}{2} - 1$
4. 乘法分割／無序因子分解（Multiplicative Partitions / Unordered Factorizations）：將正整數 $N$ 分解為若干個大於 $1$ 的因子相乘，且不考慮因子的排列順序。無序因子分解的總數量僅取決於其質因數次方的重集（Exponent Signature $(e_1, e_2, \dots, e_k)$），與具體的質數基底無關。

---

解題方法

1. 質因數分解：
   對 $N = 22,069,649$ 進行質因數分解：
   $22,069,649 = 7^3 \times 37^2 \times 47^1$
   質因數次方的重集結構（Exponent Signature）為 $(3, 2, 1)$。

2. (a) 小題求解切入點：
   計算 $N$ 的正因數總數 $d(N)$。由於 $N$ 不是完全平方數，所有正因數可兩兩配對成相乘等於 $N$ 的因數對 $\{a, b\}$。扣除含有 1 的平凡因數對 $\{1, N\}$ 後，即為所求。

3. (b) 小題求解切入點：
   設 $F(e_1, e_2, \dots, e_k)$ 表示質因數次方重集為 $(e_1, e_2, \dots, e_k)$ 之正整數分解為大於 1 之因數（包含單一因子 $N$ 本身）的不計順序分解數。
   當次方重集包含 1（即 $47^1$）時，利用降維定理：任何分解中包含 47 的因子必唯一，故可將包含 47 的因子提出，轉化為其餘指數 $(u, v)$ 的無序分解數之和：
   $F(3, 2, 1) = \sum_{u=0}^3 \sum_{v=0}^2 F(u, v)$
   建立 $F(u, v)$ 表格後求和，最後扣除單一因子（$N = N$）的 1 種情況，即得分解為「兩個或更多個因子」的解法總數。

---

選項分析

本題為非選擇題（計算問答題），以下針對 (a)、(b) 兩小題進行詳細推導與分析：

(a) 小題：分解為兩個大於 1 的因子

1. 正整數 $N = 22,069,649 = 7^3 \times 37^2 \times 47^1$。
2. $N$ 的正因數總個數為：
   $d(N) = (3 + 1)(2 + 1)(1 + 1) = 4 \times 3 \times 2 = 24$
3. 由於次數包含奇數（3 與 1），$N$ 非完全平方數，故不存在 $a = b$ 使得 $a^2 = N$。
4. 24 個正因數可恰好配對成 $\frac{24}{2} = 12$ 組無序因數對 $\{a, b\}$ 滿足 $a \times b = N$。
5. 題目限定「每個因子均大於 1」，因此必須扣除包含 1 的因數對 $\{1, 22,069,649\}$。
6. 故二因子無序分解數為：
   $12 - 1 = 11$

僅憑前五項無法唯一決定生成函數；依相鄰差為 $1,2,3,4,\ldots$ 的自然規律，設 $a_0=1$，則

$$a_n=1+\sum_{k=1}^{n}k =1+\frac{n(n+1)}{2}.$$

其普通生成函數為

設兩品牌分別為 $A,B$，六位調查員可區分，同品牌巧克力棒視為相同。使用隔板法：將 $n$ 個相同物品分給 $6$ 人的方法數為 $\binom{n+5}{5}$。

(a) 每人至少獲得兩品牌各 $4$ 根。各品牌先分出 $6\times4=24$ 根，剩餘 $12$ 根任意分配：

$$\binom{12+5}{5}^2 =\binom{17}{5}^2 =38,\!291,\!344.$$

核心觀念

本題考查**指數生成函數（Exponential Generating Function, EGF）**在多重集合（Multiset）字母排列問題中的應用。

1. 排列問題與指數生成函數：
   當問題要求從多重集合中選取 $n$ 個元素進行「有順序的排列」（arrange）時，須使用指數生成函數。序列 $a_n$ 的指數生成函數定義為：
   $f(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$
   其中 $a_n$ 代表由該單字中選取 $n$ 個字母進行排列的方法數，$x^n/n!$ 的係數即為 $a_n$。

2. 多項式因子的建構原則：
   若某個字母在單字中最多出現 $k$ 次，則該字母可被選取的個數為 $0, 1, 2, \dots, k$ 個。其對應的指數生成函數多項式因子為：
   $1 + \frac{x}{1!} + \frac{x^2}{2!} + \dots + \frac{x^k}{k!}$
   根據計數的乘法原理，將所有相異字母的多項式因子相乘，即為整體排列數的指數生成函數。

---

解題方法

(a) BOOKKEEPER

1. 統計字母頻率：
   單字 BOOKKEEPER 共有 10 個字母，各字母出現次數如下：

   • 出現 1 次的字母：B, P, R（共 3 種）
   • 出現 2 次的字母：O, K（共 2 種）
   • 出現 3 次的字母：E（共 1 種）
     （驗算總數：$1 \times 3 + 2 \times 2 + 3 \times 1 = 10$ 個字母）

2. 建立各字母之生成函數因子：

   • 字母 B, P, R：各有 1 個，因子為 $(1 + x)$，共有 3 個此類因子。
   • 字母 O, K：各有 2 個，因子為 $\left(1 + x + \frac{x^2}{2!}\right)$，共有 2 個此類因子。
   • 字母 E：有 3 個，因子為 $\left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)$，共有 1 個此類因子。

3. 組合生成函數：
   將上述所有因子相乘，得到 (a) 的指數生成函數 $f(x)$：
   $f(x) = (1 + x)^3 \left(1 + x + \frac{x^2}{2!}\right)^2 \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)$

---

(b) ACCOMMODATIONIST

1. 統計字母頻率：
   單字 ACCOMMODATIONIST 共有 16 個字母，各字母出現次數如下：
   • 出現 1 次的字母：D, N, S（共 3 種）
   • 出現 2 次的字母：A, C, M, T, I（共 5 種）
   • 出現 3 次的字母：O（共 1 種）
     （驗算總數：$1 \times 3 + 2 \times 5 + 3 \times 1 = 16$ 個字母）

核心觀念

**二元搜尋樹（Binary Search Tree, BST）**為資工系研究所演算法與資料結構考試的核心考點。

1. BST 定義與基本性質

設 $T$ 為一棵二元搜尋樹，對於樹中任意節點 $x$：

• 若 $y$ 為 $x$ 左子樹中的任意節點，則其鍵值滿足 $y.key \le x.key$（若不允許重複鍵值則為 $y.key < x.key$）。
• 若 $y$ 為 $x$ 右子樹中的任意節點，則其鍵值滿足 $y.key \ge x.key$（若不允許重複鍵值則為 $y.key > x.key$）。
• 中序走訪（In-order Traversal）一棵二元搜尋樹可獲得非遞減順序的排序序列。

2. 時間複雜度的決定因子

BST 的所有動態操作（搜尋、插入、刪除、求極值、前驅與後繼者）之時間複雜度皆正比於樹的高度 $h$，即 $O(h)$：

• 節點數為 $n$ 的 BST，其樹高 $h$ 介於 $\lfloor \log_2 n \rfloor \le h \le n - 1$ 之間。
• 樹高 $h$ 的界限直接決定了最佳、最壞與平均狀況的時間複雜度。

---

解題方法

本題需包含兩大部分：演算法詳細描述（描述機制與關鍵操作Pseudocode）與時間複雜度推導（含平均狀況數學推導）。

一、 演算法描述（Algorithm Description）

BST 的三大核心動態操作為：搜尋（Search）、插入（Insert）與刪除（Delete）。

1. 搜尋操作（BST-Search）

從根節點開始比較目標鍵值 $k$：

• 若 $k == x.key$ 或 $x == \text{NIL}$，搜尋結束。
• 若 $k < x.key$，遞迴至左子樹搜尋。
• 若 $k > x.key$，遞迴至右子樹搜尋。

BST-Search(x, k):
    if x == NIL or k == x.key:
        return x
    if k < x.key:
        return BST-Search(x.left, k)
    else:
        return BST-Search(x.right, k)

2. 插入操作（BST-Insert）

給定待插入節點 $z$（$z.key = k$），維護一雙指標以尋找插入位置：

BST-Insert(T, z):
    y = NIL
    x = T.root
    while x != NIL:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == NIL:
        T.root = z        // 樹原本為空
    else if z.key < y.key:
        y.left = z
    else:
        y.right = z

3. 刪除操作（BST-Delete）

刪除節點 $z$ 分為三種情況討論：

• Case 1（無子節點）：直接將其父節點指向 $z$ 的指標置為 $\text{NIL}$。
• Case 2（僅一個子節點）：將 $z$ 的子節點直接提升替代 $z$ 的位置，並更新父節點連結。
• Case 3（有兩個子節點）：
  1. 尋找 $z$ 的後繼者（Successor）$y$（即 $z$ 右子樹中的最小值節點）。
  2. 若 $y$ 不是 $z$ 的直接右子節點，先將 $y$ 從原位置移除（$y$ 至多僅有右子節點），並用 $y$ 的右子節點替代 $y$。
  3. 用 $y$ 替代 $z$ 的位置，並接管 $z$ 原有的左、右子樹。

---

二、 時間複雜度詳細數學推導與分析

二元搜尋樹各項操作的時間複雜度取決於樹高 $h$。設樹中含有 $n$ 個節點。

1. 最壞狀況（Worst-case Complexity）分析

• 樹的形態：當輸入資料為已排序或逆向排序序列時，二元搜尋樹會退化成單鏈串列（Skewed Tree / Degenerate Tree）。
• 樹高：$h = n - 1$。
• 推導：在傾斜樹中搜尋最深處的葉節點或插入新節點，需要經歷從根節點到葉節點的路徑，總比較次數為：
  $T_{\text{worst}}(n) = \sum_{i=1}^{n} 1 = n$
  因此，搜尋、插入與刪除的最壞時間複雜度為：
  $\Theta(n)$

2. 最佳狀況（Best-case Complexity）分析

• 樹的形態：樹保持極度平衡（如完全二元樹 Complete Binary Tree）。
• 樹高：高度為 $h = \lfloor \log_2 n \rfloor$。
• 推導：每次比較皆可排除約一半的節點，遞迴關係式為：
  $T(n) = T\left(\frac{n}{2}\right) + O(1)$
  由主定理（Master Theorem）可知：
  $T_{\text{best}}(n) = \Theta(\log n)$

3. 平均狀況（Average-case Complexity）數學推導

假設 $n$ 個互異鍵值以**均勻隨機排列（Uniform Random Permutation）**的順序依次插入建構二元搜尋樹（Randomly Built Binary Search Tree）。

(a) 內部路徑長（Internal Path Length, $P(n)$）遞迴建構

定義 $P(n)$ 為包含 $n$ 個節點的隨機 BST 中，所有節點到根節點深度之總和。
當根節點為第 $k$ 小的元素時（$k \in \{1, 2, \dots, n\}$，其出現機率均勻皆為 $\frac{1}{n}$）：

• 左子樹包含 $k - 1$ 個節點。
• 右子樹包含 $n - k$ 個節點。
• 除了左右子樹內部的路徑長之外，非根節點（共 $n - 1$ 個）的深度相較於子樹內部皆增加了 $1$。

因此 $P(n)$ 的期望值遞迴式為：
$P(n) = (n - 1) + \frac{1}{n} \sum_{k=1}^{n} \Big[ P(k - 1) + P(n - k) \Big]$

核心觀念

1. 最大堆積 (Max-Heap) 定義：
   最大堆積為一種完全二元樹 (Complete Binary Tree)，滿足 Max-Heap Property：對所有非根節點 $i$，其父節點之鍵值恆大於或等於該節點之鍵值，即 $A[\text{PARENT}(i)] \ge A[i]$。

2. 陣列儲存結構 (Array Representation)：
   採用 1-indexed 陣列儲存完全二元樹時，對於任意索引為 $i$ 的節點：

   • 父節點索引：$\text{PARENT}(i) = \lfloor i/2 \rfloor$
   • 左子節點索引：$\text{LEFT}(i) = 2i$
   • 右子節點索引：$\text{RIGHT}(i) = 2i + 1$

3. 演算法三大核心程序：

   • Max-Heapify：維持局部堆積性質（下沉 Percolate Down），時間複雜度與節點高度 $h$ 成正比，$O(h)$。
   • Build-Max-Heap：由下而上 (Bottom-up) 將無序陣列轉化為最大堆積，時間複雜度為 $O(n)$。
   • Heap-Sort：反複取出堆積頂端最大值放置於陣列尾端，並調整剩餘元素，實現原址排序 (In-place Sort)，時間複雜度為 $O(n \log n)$。

---

解題方法

一、 堆積排序演算法描述 (Algorithm Description)

Heap Sort 包含三個主要步驟與程序：

1. 程序 Max-Heapify(A, i, heap_size)：
   假設以 $\text{LEFT}(i)$ 與 $\text{RIGHT}(i)$ 為根的子樹皆已滿足 Max-Heap 性質，但 $A[i]$ 可能小於其子節點。本程序比較 $A[i]$、左子與右子節點之鍵值，找出最大者 $A[\text{largest}]$。若 $\text{largest} \neq i$，則交換 $A[i]$ 與 $A[\text{largest}]$，並對索引 $\text{largest}$ 遞迴呼叫 Max-Heapify 以維持堆積性質。

2. 程序 Build-Max-Heap(A, n)：
   包含 $n$ 個元素的陣列中，葉節點之索引為 $\lfloor n/2 \rfloor + 1$ 至 $n$。自最後一個非葉節點 $\lfloor n/2 \rfloor$ 開始倒序至第 $1$ 個節點，依次呼叫 Max-Heapify(A, i, n)，由下而上建立 Max-Heap。

3. 程序 Heap-Sort(A, n)：

   • 先呼叫 Build-Max-Heap(A, n) 建立 Max-Heap。
   • 執行 $n-1$ 次迭代：將根節點 $A[1]$（最大值）與目前堆積底部的末端元素 $A[\text{heap\_size}]$ 交換，將堆積大小減 $1$（heap_size = heap_size - 1），再對根節點執行 Max-Heapify(A, 1, heap_size) 恢復堆積性質。

演算法虛擬碼 (Pseudocode)

MAX-HEAPIFY(A, i, heap_size)
    l = 2 * i
    r = 2 * i + 1
    largest = i
    if l <= heap_size and A[l] > A[largest]
        largest = l
    if r <= heap_size and A[r] > A[largest]
        largest = r
    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest, heap_size)

BUILD-MAX-HEAP(A, n)
    heap_size = n
    for i = floor(n / 2) down to 1
        MAX-HEAPIFY(A, i, heap_size)

HEAPSORT(A, n)
    BUILD-MAX-HEAP(A, n)
    heap_size = n
    for i = n down to 2
        exchange A[1] with A[i]
        heap_size = heap_size - 1
        MAX-HEAPIFY(A, 1, heap_size)

---

二、 時間複雜度詳細數學推導 (Time Complexity Derivation)

(1) Max-Heapify 時間複雜度推導

對於大小為 $n$ 的樹，最差情況下（當樹的最底層剛好半滿時），左子樹所含節點數上限為 $\frac{2n}{3}$。其執行時間遞迴關係式為：
$T(n) \le T\left(\frac{2n}{3}\right) + \Theta(1)$

根據主定理 (Master Theorem) 之 Case 2（其中 $a=1, b=3/2, f(n)=\Theta(1)$，滿足 $n^{\log_b a} = n^0 = 1$）：
$T(n) = \Theta(\log n)$

若以節點高度 $h$ 表示，Max-Heapify 在高度為 $h$ 的節點上執行時間為 $O(h)$。

(2) Build-Max-Heap 時間複雜度推導

直覺上對 $\lfloor n/2 \rfloor$ 個節點各執行一次 $O(\log n)$ 的 Max-Heapify 會得到 $O(n \log n)$ 的鬆散上限。透過精確分析各高度之節點數量，可導出緊密上限 $O(n)$：

• 包含 $n$ 個節點的完全二元樹，樹的高度為 $\lfloor \log_2 n \rfloor$。
• 高度為 $h$ 的節點最多有 $\left\lceil \frac{n}{2^{h+1}} \right\rceil$ 個。
• 對高度為 $h$ 的節點執行 Max-Heapify 需耗費 $O(h)$ 時間。

核心觀念

本題旨在考察遞迴（Recursion）、分治法（Divide and Conquer）以及演算法時間複雜度之數學推導（Asymptotic Analysis & Recurrence Relations）。

1. 河內塔（Tower of Hanoi）問題定義：
   有三根柱子（設為來源柱 $A$、目標柱 $C$、輔助柱 $B$）以及 $n$ 個大小各不相同的圓盤。初始時所有圓盤由大到小堆疊於柱子 $A$。目標是將所有圓盤移至柱子 $C$，移動過程必須遵守以下規則：

   • 每次只能移動一個圓盤。
   • 任何圓盤都不能疊放在比它小的圓盤之上。
   • 只能移動位於柱子最頂端的圓盤。

2. 核心演算法設計概念：
   將求解 $n$ 個圓盤的問題，遞迴分解為解決兩次 $n-1$ 個圓盤的子問題以及一次基礎移動操作。

3. 複雜度分析核心定理／工具：

   • 遞迴關係式（Recurrence Relation）之建立。
   • 代換法／展開法（Substitution / Unrolling Method）求階乘級數與等比級數和。

---

解題方法

1. 河內塔演算法描述（Algorithm Description）

求解將 $n$ 個圓盤從來源柱 $A$ 搬移至目標柱 $C$（經由輔助柱 $B$）的遞迴分治步驟如下：

1. 基本情況（Base Case）：
   當 $n = 1$ 時，直接將唯一的圓盤從來源柱 $A$ 移動至目標柱 $C$。
2. 遞迴情況（Recursive Step）：
   當 $n > 1$ 時：
   • Step 1：遞迴地將上面的 $n-1$ 個圓盤從來源柱 $A$ 移動至輔助柱 $B$（此時目標柱 $C$ 作為輔助）。
   • Step 2：將第 $n$ 個（最大的）圓盤從來源柱 $A$ 直接移動至目標柱 $C$。
   • Step 3：遞迴地將 $n-1$ 個圓盤從輔助柱 $B$ 移動至目標柱 $C$（此時來源柱 $A$ 作為輔助）。

虛擬碼（Pseudocode）實作：

def Hanoi(n, source, target, aux):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    # Step 1: 將 n-1 個盤子從 source 移到 aux
    Hanoi(n - 1, source, aux, target)
    # Step 2: 將第 n 個盤子從 source 移到 target
    print(f"Move disk {n} from {source} to {target}")
    # Step 3: 將 n-1 個盤子從 aux 移到 target
    Hanoi(n - 1, aux, target, source)

---

2. 時間複雜度之詳細數學推導（Mathematical Derivation）

設 $T(n)$ 表示搬移 $n$ 個圓盤所需要的最少移動次數（Basic Operation Count）。

(1) 建立遞迴關係式（Recurrence Relation）

根據演算法的三個步驟：

• 搬移頂層 $n-1$ 個圓盤需 $T(n-1)$ 次移動。
• 搬移底層最大圓盤需 $1$ 次移動。
• 再次搬移 $n-1$ 個圓盤需 $T(n-1)$ 次移動。

因此可得邊界條件與遞迴關係式：
$T(1) = 1$
$T(n) = 2T(n-1) + 1, \quad \forall n \ge 2$

(2) 利用代換法／展開法（Unrolling Method）求解閉合形式（Closed-Form）

將遞迴關係式連續展開：
$T(n) = 2T(n-1) + 1$
$= 2\left[2T(n-2) + 1\right] + 1 = 2^2 T(n-2) + 2 + 1$
$= 2^2\left[2T(n-3) + 1\right] + 2 + 1 = 2^3 T(n-3) + 2^2 + 2 + 1$