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

設四間教室的人數為 $n_1,n_2,n_3,n_4$，其中 $n_i\ge 3$ 且

$$n_1+n_2+n_3+n_4=22.$$

令 $x_i=n_i-3\ge 0$，則

$$x_1+x_2+x_3+x_4=10,$$

故人數分配方式數為

核心觀念

• 歐拉函數（Euler's Totient Function）：設 $n$ 為正整數，歐拉函數 $\phi(n)$ 定義為不超過 $n$ 且與 $n$ 互質（relatively prime, 即 $\gcd(a, n) = 1$）的正整數個數。
• 算術基本定理與質因數分解（Prime Factorization）：任何大於 1 的正整數皆可唯一表示為質數的乘積。若 $n$ 的質因數分解式為：
  $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$
  其中 $p_1, p_2, \dots, p_k$ 為相異質數，$e_1, e_2, \dots, e_k \ge 1$。
• 歐拉函數計算公式：
  $\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right)\cdots\left(1 - \frac{1}{p_k}\right) = \prod_{i=1}^k p_i^{e_i - 1}(p_i - 1)$
  特別地，當 $n$ 為無平方因子數（square-free number，即所有 $e_i = 1$）時，公式簡化為：
  $\phi(n) = (p_1 - 1)(p_2 - 1)\cdots(p_k - 1)$

---

解題方法

本題欲求小於或等於 $188,071$ 且與 $188,071$ 互質的正整數個數，即計算 $\phi(188,071)$ 的值。解題步驟分為「質因數分解」與「帶入歐拉函數公式」兩階段：

1. 對 $N = 188,071$ 進行質因數分解：
   利用試除法（Trial Division）從小質數開始檢驗：
   • 快速排除 $2, 3, 5, 7, 11$（皆無法整除 $188,071$）。
   • 試除質數 $13$：
     $188,071 \div 13 = 14,467$
     得 $13$ 為第一質因數。
   • 對商數 $14,467$ 繼續試除質數：
     • $14,467 \div 13 = 1,112.84\dots$（無法整除）
     • 試除質數 $17$：
       $14,467 \div 17 = 851$
       得 $17$ 為第二質因數。
   • 對商數 $851$ 繼續試除質數：

核心觀念

本題屬於**離散數學中的組合計數（Combinatorics）與生成函數（Generating Functions）**考題，具體考點包含：

1. 重複組合（Combinations with Repetition）與限制條件：在非負整數解的限制下，計算將 $n$ 個相同的物件分給不同種類的分配方式。
2. 一般生成函數（Ordinary Generating Functions, OGF）：將種類選擇的限制條件轉換為級數相乘，再利用部分分式拆解法（Partial Fraction Decomposition）求出 $x^n$ 的係數 $[x^n]$。
3. 二項式定理與負整數次方展開（Binomial Expansion with Negative Exponents）：
   $\frac{1}{(1-x)^{k+1}} = \sum_{n=0}^{\infty} \binom{n+k}{k} x^n = \sum_{n=0}^{\infty} H^{k+1}_n x^n$

---

解題方法

(a) 詳解推導

題目要求從 4 種不同的糖果中挑選 $n$ 顆，其中指定 1 種糖果的數量必須為偶數（$0, 2, 4, \dots$），其餘 3 種無限制（$0, 1, 2, \dots$）。

方法一：一般生成函數法（標準正攻法）
設 4 種糖果分別為 $A, B, C, D$，並設 $A$ 的選取數量必須為偶數。

1. 建立各種類的生成函數：

   • 糖果 $A$（偶數顆）：$1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1 - x^2}$
   • 糖果 $B, C, D$（無限制）：$1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}$

2. 建立整體生成函數 $f(x)$：
   $f(x) = \left(\frac{1}{1 - x^2}\right) \cdot \left(\frac{1}{1 - x}\right)^3 = \frac{1}{(1-x)^4(1+x)}$

3. 進行部分分式拆解（Partial Fraction Decomposition）：
   設 $f(x) = \frac{A}{1+x} + \frac{B}{1-x} + \frac{C}{(1-x)^2} + \frac{D}{(1-x)^3} + \frac{E}{(1-x)^4}$
   解得各項係數為：
   $A = \frac{1}{16}, \quad B = \frac{1}{16}, \quad C = \frac{1}{8}, \quad D = \frac{1}{4}, \quad E = \frac{1}{2}$
   故 $f(x)$ 可表示為：
   $f(x) = \frac{1}{16(1+x)} + \frac{1}{16(1-x)} + \frac{1}{8(1-x)^2} + \frac{1}{4(1-x)^3} + \frac{1}{2(1-x)^4}$

4. 提取 $x^n$ 的係數 $[x^n] f(x)$：
   利用廣義二項式定理，可得：
   $[x^n] \frac{1}{1+x} = (-1)^n$
   $[x^n] \frac{1}{(1-x)^{k+1}} = \binom{n+k}{k}$
   因此：
   $[x^n] f(x) = \frac{1}{16}(-1)^n + \frac{1}{16}\binom{n}{0} + \frac{1}{8}\binom{n+1}{1} + \frac{1}{4}\binom{n+2}{2} + \frac{1}{2}\binom{n+3}{3}$

5. 化簡為多項式閉形式（Closed Form）：
   將組合項化簡並通分（分母為 48）：
   $\frac{1}{2}\binom{n+3}{3} = \frac{n^3 + 6n^2 + 11n + 6}{12} = \frac{4n^3 + 24n^2 + 44n + 24}{48}$
   $\frac{1}{4}\binom{n+2}{2} = \frac{n^2 + 3n + 2}{8} = \frac{6n^2 + 18n + 12}{48}$
   $\frac{1}{8}\binom{n+1}{1} = \frac{n+1}{8} = \frac{6n + 6}{48}$
   $\frac{1}{16}\binom{n}{0} = \frac{1}{16} = \frac{3}{48}$
   $\frac{1}{16}(-1)^n = \frac{3(-1)^n}{48}$
   加總整理可得：
   $[x^n] f(x) = \frac{4n^3 + 30n^2 + 68n + 45 + 3(-1)^n}{48}$

方法二：分類討論法（重複組合加總驗證）
設糖果 $A$ 取 $2k$ 顆（$k \ge 0$），則其餘 3 種糖果共需分得 $n - 2k$ 顆。
利用重複組合公式 $H^3_{n-2k} = \binom{(n-2k)+3-1}{n-2k} = \binom{n-2k+2}{2}$，總方法數為：
$\sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n - 2k + 2}{2}$

---

(b) 詳解推導

題目要求從 3 種不同的糖果中挑選 $n$ 顆，其中指定 2 種糖果的數量必須為奇數（$1, 3, 5, \dots$），剩餘 1 種無限制（$0, 1, 2, \dots$）。

方法一：一般生成函數法（標準正攻法）
設 3 種糖果分別為 $A, B, C$，其中 $A, B$ 的選取數量必須為奇數。

1. 建立各種類的生成函數：

   • 糖果 $A, B$（奇數顆）：$x + x^3 + x^5 + x^7 + \dots = \frac{x}{1 - x^2}$
   • 糖果 $C$（無限制）：$1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}$

2. 建立整體生成函數 $g(x)$：
   $g(x) = \left(\frac{x}{1 - x^2}\right)^2 \cdot \left(\frac{1}{1 - x}\right) = \frac{x^2}{(1-x)^3(1+x)^2}$

3. 進行部分分式拆解：
   將 $g(x)$ 拆解為：
   $g(x) = \frac{A}{1+x} + \frac{B}{(1+x)^2} + \frac{C}{1-x} + \frac{D}{(1-x)^2} + \frac{E}{(1-x)^3}$
   解得各項係數為：
   $A = -\frac{1}{16}, \quad B = \frac{1}{8}, \quad C = -\frac{1}{16}, \quad D = -\frac{1}{4}, \quad E = \frac{1}{4}$
   即：

設普通生成函數為

$$G(x)=\sum_{n=0}^{\infty}a_nx^n,$$

其中 $a_0,a_1,\ldots=1,2,3,4,5,5,\ldots$。則

$$G(x)=1+2x+3x^2+4x^3+5x^4+5x^5+\cdots.$$

核心觀念

本題屬於離散數學組合學（Combinatorics）中「從多種相異類別中選取物件」的**重複組合（Combinations with Repetition）**問題。

在離散數學考題標準規範中，當題目給定 4 種食品罐頭（雞肉、牛肉、豬肉、魚肉）並要求選取指定數量時，同種類的罐頭視為同型（Identical），種類之間為相異（Distinct）。

設選取之雞肉罐頭數量為 $c$、牛肉罐頭數量為 $b$、豬肉罐頭數量為 $p$、魚肉罐頭數量為 $f$。因為救生艇需選取 15 個罐頭，且每種罐頭儲備總數皆為 15 個（即單一種類選取的上限為 15，絕不超越儲備上限），故題意等價於求解非負整數解 $(c, b, p, f)$ 的組數：
$c + b + p + f = 15, \quad c, b, p, f \in \mathbb{N}_0$

本題主要運用之定義與定理：

1. 重複組合公式：將 $k$ 個相同物件分配給 $n$ 個相異類別（即方程式 $x_1 + x_2 + \dots + x_n = k$ 之非負整數解個數）為：
   $H^n_k = \binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1}$
2. 奇偶性與範圍限制處理：
   • 奇偶性限制：採用變數代換 $b = 2k$ 或針對奇數項分類加總。
   • 範圍限制：採用直接分類討論法（Direct Case Analysis）或反面扣除法（Complementary Counting）。

---

解題方法

(a) 包含偶數個牛肉罐頭與奇數個雞肉罐頭之組合數

限制條件：

• 牛肉罐頭數 $b$ 為偶數：$b \in \{0, 2, 4, 6, 8, 10, 12, 14\}$
• 雞肉罐頭數 $c$ 為奇數：$c \in \{1, 3, 5, 7, 9, 11, 13, 15\}$
• 豬肉與魚肉罐頭數 $p, f \ge 0$
• $c + b + p + f = 15$

推導步驟：

1. 將雞肉罐頭可能出現的奇數 $c$ 進行分類。令 $c = 15 - R$，其中 $R$ 必為偶數，$R \in \{0, 2, 4, 6, 8, 10, 12, 14\}$。
2. 原方程式化簡為 $b + p + f = R$。
3. 設 $b = 2k$（$0 \le k \le \frac{R}{2}$），則 $p + f = R - 2k$。
4. 對於固定的 $R$ 與 $k$，$p + f = R - 2k$ 的非負整數解個數為：
   $H^2_{R - 2k} = \binom{(R - 2k) + 2 - 1}{R - 2k} = R - 2k + 1$
5. 固定 $R = 2h$（其中 $h = \frac{R}{2}$），讓 $k$ 從 $0$ 累加至 $h$：
   $\sum_{k=0}^{h} (2h - 2k + 1) = \sum_{j=0}^{h} (2j + 1) = (h + 1)^2$
6. $c$ 的可能取值對應 $h = \frac{15 - c}{2} \in \{0, 1, 2, 3, 4, 5, 6, 7\}$。
7. 加總所有可能之 $h$：
   $\text{總組合數} = \sum_{h=0}^{7} (h + 1)^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2$
   $\text{總組合數} = \frac{8 \times 9 \times 17}{6} = 204$

---

(b) 包含至少三個豬肉罐頭或完全沒有豬肉罐頭之組合數

限制條件：

• 豬肉罐頭數 $p \ge 3$ 或 $p = 0$
• 罐頭總數 $c + b + p + f = 15$，且 $c, b, f \ge 0$

推導步驟（提供兩種標準解法）：

• 方法一：直接分類討論法
  1. 事件一：完全沒有豬肉罐頭 ($p = 0$)
     方程式簡化為 $c + b + f = 15$，由 3 種類中選取 15 個罐頭：

核心觀念

字母表 $\Sigma$ 中有：

• 數字字符：$5$ 個；
• 英文字母：$6$ 個。

限制條件是：不能出現連續的兩個 alphabetic characters，且不論兩個字母是否相同，只要相鄰皆不允許。因此合法字串的形式必須符合：

$$\text{字母之間至少隔著一個數字。}$$

令 $T_n$ 表示長度為 $n$ 的合法字串數量。可利用字串最後一個字符的類型建立遞迴關係。

解題方法

將長度為 $n$ 的合法字串分成兩類：

• $A_n$：最後一個字符是數字；
• $B_n$：最後一個字符是字母。

因此：

$$T_n=A_n+B_n$$

以數字結尾

若最後一個字符是數字，前面長度 $n-1$ 的部分可以是任意合法字串，最後再選擇 $5$ 個數字之一：

$$A_n=5T_{n-1}$$

以字母結尾

若最後一個字符是字母，由於不能有連續字母，倒數第二個字符必須是數字。

前面長度 $n-2$ 的部分有 $T_{n-2}$ 種，接著選一個數字，再選一個字母，因此：

$$B_n=5\cdot 6\cdot T_{n-2}=30T_{n-2}$$

合併兩類：

$$T_n=A_n+B_n$$

所以得到遞迴關係：

$$T_n=5T_{n-1}+30T_{n-2},\qquad n\ge 2$$

初始條件為：

$$T_0=1$$

空字串屬於 $\Sigma^*$，因此長度為 $0$ 時有 $1$ 種。

長度為 $1$ 時可以選擇任意一個字符：

$$T_1=5+6=11$$

故完整遞迴關係為：

$$\boxed{T_n=5T_{n-1}+30T_{n-2},\quad T_0=1,\quad T_1=11}$$

解遞迴關係

其特徵方程為：

$$r^2-5r-30=0$$

解得：

$$r=\frac{5\pm\sqrt{145}}{2}$$

令：

$$r_1=\frac{5+\sqrt{145}}{2},\qquad r_2=\frac{5-\sqrt{145}}{2}$$

因此通解為：

$$T_n=C_1r_1^n+C_2r_2^n$$

利用初始條件：

$$C_1+C_2=1$$

以及：

$$C_1r_1+C_2r_2=11$$

解得：

$$C_1=\frac{17+\sqrt{145}}{2\sqrt{145}}$$

核心觀念

快速排序法（Quick Sort）是一種基於**分治法（Divide and Conquer）**的高效排序演算法。其核心思想為：

1. 分割（Partition）：從陣列中挑選一個元素作為「基準值」（Pivot），並重排陣列，使得所有小於基準值的元素皆位於基準值左側，所有大於或等於基準值的元素皆位於右側。
2. 遞迴求解（Conquer）：分別對基準值左側與右側的子陣列遞迴執行 Quick Sort。
3. 合併（Combine）：由於子陣列採原地（In-place）排序，當子陣列完成排序時，整體陣列即已完全有序，無需額外的合併步驟。

本題主要考驗演算法邏輯寫法、遞迴關係式（Recurrence Relation）之建立，以及運用**主定理（Master Theorem）與代數展開法（Algebraic Induction/Substitution Method）**進行最差、最佳與平均時間複雜度（Time Complexity）之推導。

---

解題方法

一、 Quick Sort 演算法虛擬碼 (Pseudo-code)

QuickSort(A, low, high):
    if low < high:
        // q 為 Partition 後 Pivot 的最終正確位置 index
        q = Partition(A, low, high)
        QuickSort(A, low, q - 1)   // 遞迴排序左半部
        QuickSort(A, q + 1, high)  // 遞迴排序右半部

Partition(A, low, high):
    x = A[high]                    // 選擇最後一個元素作為 Pivot
    i = low - 1                    // i 為較小元素的邊界指標
    for j = low to high - 1:
        if A[j] <= x:
            i = i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[high]     // 將 Pivot 置於正確分割位置
    return i + 1

---

二、 時間複雜度詳細分析 (Time Complexity Analysis)

設陣列長度為 $n$。Partition 步驟需要掃描整個陣列一次，其時間複雜度為 $\Theta(n)$。整體時間複雜度取決於每次 Partition 劃分出的兩個子陣列大小。

1. 最佳情況（Best-case Complexity）：$T(n) = \Theta(n \log n)$

• 條件：每次 Partition 都能將長度為 $n$ 的陣列極度均勻地平分為大小約為 $\lfloor \frac{n}{2} \rfloor$ 與 $\lceil \frac{n}{2} \rceil - 1$ 的兩半。
• 遞迴關係式：
  $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$
• 詳細推導（套用主定理 Master Theorem）：
  • 形式：$T(n) = aT\left(\frac{n}{b}\right) + f(n)$，其中 $a = 2, b = 2, f(n) = \Theta(n)$。
  • 計算 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$。
  • 由於 $f(n) = \Theta(n) = \Theta(n^{\log_b a})$，符合主定理 Case 2。
  • 得證最佳時間複雜度 $T(n) = \Theta(n \log n)$。

2. 最差情況（Worst-case Complexity）：$T(n) = \Theta(n^2)$

• 條件：每次選取的 Pivot 皆為當前陣列的最大值或最小值（例如：輸入已排序或反向排序，且固定選取首尾為 Pivot），導致分割出的兩個子陣列長度分別為 $0$ 與 $n-1$。
• 遞迴關係式：
  $T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + c \cdot n$
• 詳細推導（代數級數展開）：
  $T(n) = T(n-1) + cn$
  $T(n) = T(n-2) + c(n-1) + cn$
  $T(n) = T(1) + c \sum_{i=2}^{n} i = T(1) + c \left( \frac{n(n+1)}{2} - 1 \right)$
  • 由等差級數求和可知最高次項為 $n^2$，故最差時間複雜度 $T(n) = \Theta(n^2)$。

3. 平均情況（Average-case Complexity）：$T(n) = \Theta(n \log n)$

核心觀念

霍夫曼編碼（Huffman Coding） 是一種用於無損資料壓縮的貪婪演算法（Greedy Algorithm），其目標是建構一套最佳前綴碼（Optimal Prefix Code），使得給定檔案或文本的總變長編碼長度達到最短。

1. 前綴碼（Prefix Code / Prefix-free Code）：
   任何字元的編碼皆不能是另一個字元編碼的前綴。此性質保證了解碼時的唯一可解碼性（Unique Decipherability），解碼過程無需分隔符號即可順暢進行。
2. 最佳樹結構（Optimal Binary Tree）：
   編碼對應至一棵滿二元樹（Full Binary Tree），字元皆位於葉節點（Leaf Nodes）。字元出現頻率越高，其在樹中的深度越淺（編碼越短）；頻率越低，深度越深（編碼越長）。
3. 加權外路徑長（Weighted External Path Length）：
   若字元集為 $C$，字元 $c \in C$ 的出現頻率為 $f(c)$，其在二元樹 $T$ 中對應葉節點的深度為 $d_T(c)$（亦即編碼長度），則總編碼成本為：
   $B(T) = \sum_{c \in C} f(c) \cdot d_T(c)$
   霍夫曼演算法保證能找到使 $B(T)$ 達到最小值的樹結構。

---

解題方法

1. 演算法描述與虛擬碼（Pseudocode）

霍夫曼演算法採用**自底向上（Bottom-up）**的貪婪策略：每次從當前的節點集合中，選出出現頻率最小的兩個節點合併為一棵新子樹，新節點的頻率為該兩節點頻率之和，再將新節點放回集合中。重複此過程直至只剩下一個根節點為止。

為了有效率地找出頻率最小的節點，演算法使用最小優先佇列（Min-Priority Queue / Min-Heap） $Q$ 來維護所有節點。

HUFFMAN(C)
1. n = |C|
2. Q = C  // 將所有字元節點放入最小優先佇列 Q 中（以頻率 f[c] 為鍵值）
3. for i = 1 to n - 1 do
4.     allocate a new node z
5.     z.left = x = EXTRACT-MIN(Q)   // 取出頻率最小的節點 x
6.     z.right = y = EXTRACT-MIN(Q)  // 取出頻率次小的節點 y
7.     z.freq = x.freq + y.freq      // 新節點頻率為兩者之和
8.     INSERT(Q, z)                  // 將新內部節點 z 放回最小優先佇列 Q
9. return EXTRACT-MIN(Q)             // 傳回二元樹之根節點

---

2. 詳細時間複雜度分析（Detailed Time Complexity Analysis）

設字元集 $C$ 包含 $n$ 個不同的字元（即 $n = |C|$）：

1. 初始化優先佇列（Line 1–2）：
   • 將包含 $n$ 個字元的陣列建立成一個 Min-Heap。
   • 使用標準的 BUILD-MIN-HEAP 演算法，時間複雜度為 $O(n)$。（若逐一插入 $n$ 次則為 $O(n \log n)$，但不影響最終的整體漸進複雜度）。

高度為 $h$ 的完全 $n$ 元樹，每個內部節點至多有 $n$ 個子節點，因此第 $i$ 層至多有 $n^i$ 個節點。葉節點數在所有葉節點皆位於第 $h$ 層時最多，故

$$m\le n^h.$$

假設 $n>1$，兩邊取以 $n$ 為底的對數：