109 年 國立臺南大學資訊工程學系碩士班《計算機概論》

本題主要在考察物件導向程式設計 (Object-Oriented Programming, OOP) 的基本觀念，要求考生設計包含父類別 (parent class) 和子類別 (child class) 的程式碼，並分別展示資料封裝 (Data encapsulation)、方法多載 (Overloading)、方法覆寫 (Overwriting)、多型 (Polymorphism) 和後期繫結 (Late binding) 這五個核心概念。

由於題目要求設計「任意」的類別，因此以下提供一個範例，展示如何在 C++ 中實現這些概念。

核心觀念說明：

• 資料封裝 (Data encapsulation)： 將資料（成員變數）和操作資料的方法（成員函數）綁定在一起，並透過存取修飾符（如 public, private, protected）來控制對資料的存取。這有助於保護資料的完整性，並將內部實現細節隱藏起來。
• 方法多載 (Overloading)： 在同一類別中，定義多個名稱相同但參數列表（參數型別或數量）不同的方法。編譯器會根據傳入的參數來決定呼叫哪一個方法。
• 方法覆寫 (Overwriting)： 在子類別中重新實作父類別中已有的方法。子類別的方法必須與父類別的方法有相同的名稱、參數列表和返回型別（或相容的返回型別）。這通常與繼承和多型一起使用。
• 多型 (Polymorphism)： 允許使用父類別的指標或參考來指向子類別的物件。在執行時，根據實際物件的型別來決定呼叫哪個方法。這使得程式碼更具彈性和擴展性。
• 後期繫結 (Late binding) / 動態繫結 (Dynamic binding)： 指的是在程式執行時才決定呼叫哪個方法。這通常透過虛擬函數 (virtual functions) 來實現，並與多型緊密相關。

範例設計 (C++):

我們設計一個 Shape (形狀) 作為父類別，以及 Circle (圓形) 和 Rectangle (矩形) 作為子類別。

本題要求使用 C/C++ 語言，針對一個「不規則」二維陣列 (irregular 2D array)，使用巢狀 for 迴圈來計算並印出陣列的內容、總元素數、平均值、最大值及其索引、最小值及其索引。

「不規則二維陣列」通常指的是每一列的元素數量不固定。在 C/C++ 中，實現不規則二維陣列有幾種方式，例如：

1. 使用指標的指標 (int**)：動態分配記憶體，每一列分配不同大小的空間。
2. 使用陣列的陣列 (int* arr[])：宣告一個陣列，其中每個元素都是一個指向陣列的指標。
3. 使用 std::vector<std::vector<int>> (C++): 這是 C++ 中最常用且靈活的方式，內部會自動管理記憶體。

考量到題目要求使用「巢狀 for 迴圈」來處理，且是 C/C++ 語言，通常會偏向使用指標或 std::vector。這裡我們採用 std::vector<std::vector<int>>，因為它最能體現「不規則」的特性，且語法相對簡潔。

題目中給定的資料：

83
2   64   23   15
62  37
59  45   78   90
83

這看起來像是以空白分隔的數字，但最後一行只有一個數字 83。仔細觀察，第一行 83 似乎是一個單獨的元素，緊接著第二行有四個元素，第三行有兩個，第四行有四個，第五行有一個。

如果將這些數字看作是「行」，並且每行有若干元素，則：

• 第一行：83 (1 個元素)
• 第二行：2 64 23 15 (4 個元素)
• 第三行：62 37 (2 個元素)
• 第四行：59 45 78 90 (4 個元素)
• 第五行：83 (1 個元素)

這是一個典型的「不規則陣列」結構。

C++ 程式碼實作：

本題要求實作一個遞迴函數 int multiply(int m, int n)，用於計算兩個整數 m 和 n 的乘積。

核心觀念：遞迴 (Recursion)
遞迴是指一個函數在其定義中呼叫自身。一個遞迴函數必須包含兩個部分：

1. 終止條件 (Base Case)： 確保遞迴能夠停止，避免無限迴圈。
2. 遞迴步驟 (Recursive Step)： 將問題分解成一個或多個較小的、與原問題相似的子問題，並透過呼叫自身來解決這些子問題。

解題思路：
乘法 m * n 可以被看作是將 m 加到自身 n 次，或者將 n 加到自身 m 次。我們可以利用這個特性來設計遞迴。

例如，m * n 可以表示為 m + (m * (n-1))。
這就形成了一個遞迴關係：

• multiply(m, n) = m + multiply(m, n-1)

終止條件：
當 n 減到 0 的時候，乘積就是 0 (m * 0 = 0)。所以，當 n = 0 時，函數應該返回 0。

遞迴步驟：
如果 n 不為 0，則 multiply(m, n) 等於 m 加上 multiply(m, n-1)。

處理負數：
題目沒有明確說明 m 和 n 是否為負數。如果需要處理負數，有幾種策略：

1. 將問題轉換為正數計算： 假設 m 和 n 都是正數。如果 n 是負數，我們可以將問題轉換為 multiply(m, -n) 並在最後取負值，或者更方便地，將 m 變成 -m 來計算 multiply(-m, -n)。
2. 利用加法和減法：
   • 如果 n > 0，則 m * n = m + m * (n-1)。
   • 如果 n < 0，則 m * n = -m + m * (n+1)。這等價於 m * n = -(m + m * (-n-1))。

為了簡化，我們可以先假設 n 為非負數，然後再考慮如何擴展到負數。

遞迴函數實作 (針對非負 n)：

#include <iostream>

// 遞迴函數計算 m * n (假設 n >= 0)
int multiplyRecursiveNonNegative(int m, int n) {
    // 終止條件 (Base Case)
    if (n == 0) {
        return 0;
    }
    // 遞迴步驟 (Recursive Step)
    else {
        // m * n = m + m * (n-1)
        return m + multiplyRecursiveNonNegative(m, n - 1);
    }
}

處理任意整數 (包括負數)：

為了處理 n 為負數的情況，我們可以修改遞迴步驟。
如果 n 是負數，m * n 可以寫成 -(m * (-n))。
所以，如果 n < 0，我們可以調用 multiplyRecursiveNonNegative(m, -n) 然後取其負值。

更精煉的寫法是直接在遞迴步驟中處理：

• 如果 n > 0：m + multiply(m, n-1)
• 如果 n < 0：-m + multiply(m, n+1) （因為 m * n = m * (n+1) - m）

最終的遞迴函數實作：

核心觀念

本題考查：

• 遞迴函式的設計
• C 字串以 '\0' 作為結束標記
• 指標逐字元走訪
• 遞迴的基底條件與遞迴關係式

C 字串 str 是由多個字元組成，最後以空字元 '\0' 結尾。例如：

"apple"

實際儲存為：

'a' 'p' 'p' 'l' 'e' '\0'

因此，遇到 *str == '\0' 時，代表已走完整個字串。

解題方法

將問題拆成兩部分：

1. 檢查目前字元 *str 是否等於 ch
2. 遞迴計算剩餘字串 str + 1 中的出現次數

若目前字元相等，就貢獻 $1$；否則貢獻 $0$。遞迴關係為：

$$\text{count}(ch,str) = \begin{cases} 0, & \text{若 } *str = '\0' \\ (*str == ch) + \text{count}(ch,str+1), & \text{其他情況} \end{cases}$$

在 C 語言中，布林比較式 *str == ch 成立時會得到 $1$，不成立時得到 $0$，正好可直接加入計數結果。

參考程式碼

int count(char ch, const char* str)
{
    if (*str == '\0')
        return 0;

    return (*str == ch) + count(ch, str + 1);
}

執行流程範例

計算：

count('p', "apple")

其遞迴展開如下：

本題要求使用 KMP (Knuth-Morris-Pratt) 演算法，計算給定模式 (pattern) p[] = ababbababaa 的「失敗函數值」(failure function values)，也稱為「部分匹配表」(partial match table) 或「前綴函數值」(prefix function values)，通常表示為 lps 陣列（Longest Proper Prefix which is also a Suffix）。

KMP 演算法簡介：
KMP 演算法是一種高效的字串搜尋演算法，它透過預先計算模式字串的特性，避免在匹配失敗時進行不必要的比較。失敗函數 lps 陣列儲存了模式字串中，對於每個位置 i，其最長的前綴（從開頭算起）同時也是該位置之前的子字串的後綴的最大長度。

計算 lps 陣列的步驟：
我們需要計算一個長度與模式字串相同的 lps 陣列。lps[i] 表示模式字串 p[0...i] 中，最長的前綴（Proper Prefix）同時也是其後綴（Suffix）的長度。

• lps[0] 永遠是 0，因為長度為 1 的字串沒有真前綴 (proper prefix)。
• 對於 i > 0，我們比較 p[i] 和 p[length]，其中 length 是 lps[i-1] 的值。

演算法流程：

1. 初始化：

   • 模式字串 p = ababbababaa。
   • 模式長度 M = 11。
   • 創建 lps 陣列，大小為 M。
   • lps[0] = 0。
   • 初始化 length = 0 (表示當前最長前綴/後綴的長度)。
   • 初始化 i = 1 (從模式的第二個字元開始計算 lps 值)。

2. 迭代計算 lps[i] for i from 1 to M-1:

   • 情況 1：p[i] == p[length]
     • 如果當前字元 p[i] 與 p[length] 相等，表示我們找到了更長的前綴/後綴。
     • 將 length 加 1。
     • 設定 lps[i] = length。
     • 將 i 加 1，繼續下一個字元。
   • 情況 2：p[i] != p[length]
     • 如果字元不匹配，我們需要縮短當前的前綴/後綴長度。
     • 如果 length != 0：
       • 我們不能直接放棄，而是需要尋找 p[0...length-1] 這個前綴的下一個更短的前綴，它同時也是 p[0...length-1] 的後綴。這個長度由 lps[length-1] 給出。
       • 將 length 更新為 lps[length-1]。
       • 不要 增加 i，重新比較 p[i] 和新的 p[length]。
     • 如果 length == 0：
       • 表示我們無法找到任何前綴與當前字元 p[i] 匹配。
       • 設定 lps[i] = 0。
       • 將 i 加 1，繼續下一個字元。

計算過程：
模式 p = a b a b b a b a b a a
索引 0 1 2 3 4 5 6 7 8 9 10
lps 陣列大小為 11。

• lps[0] = 0 (初始化)
  length = 0, i = 1

• i = 1: p[1] = 'b', p[length] = p[0] = 'a'.
  p[1] != p[0]. length is 0.
  lps[1] = 0.
  i becomes 2.

• i = 2: p[2] = 'a', p[length] = p[0] = 'a'.
  p[2] == p[0]. Match!
  length becomes length + 1 = 1.
  lps[2] = 1.
  i becomes 3.

• i = 3: p[3] = 'b', p[length] = p[1] = 'b'.
  p[3] == p[1]. Match!
  length becomes length + 1 = 2.
  lps[3] = 2.
  i becomes 4.

• i = 4: p[4] = 'b', p[length] = p[2] = 'a'.
  p[4] != p[2]. Mismatch.
  Since length is 2 (not 0), update length = lps[length - 1] = lps[2 - 1] = lps[1] = 0.
  Now, re-compare p[4] with p[length] (which is now p[0]).
  p[4] = 'b', p[0] = 'a'. Still mismatch.
  Since length is now 0, set lps[4] = 0.
  i becomes 5.

• i = 5: p[5] = 'a', p[length] = p[0] = 'a'.
  p[5] == p[0]. Match!
  length becomes length + 1 = 1.
  lps[5] = 1.
  i becomes 6.

• i = 6: p[6] = 'b', p[length] = p[1] = 'b'.
  p[6] == p[1]. Match!
  length becomes length + 1 = 2.
  lps[6] = 2.
  i becomes 7.

• i = 7: p[7] = 'a', p[length] = p[2] = 'a'.
  p[7] == p[2]. Match!
  length becomes length + 1 = 3.
  lps[7] = 3.
  i becomes 8.

• i = 8: p[8] = 'b', p[length] = p[3] = 'b'.
  p[8] == p[3]. Match!
  length becomes length + 1 = 4.
  lps[8] = 4.
  i becomes 9.

核心觀念

本題考查「循環鏈結串列的整批回收」。ptr 指向使用中的循環鏈結串列尾端節點，故：

• (*ptr)->link 是循環串列的第一個節點。
• avail 指向可用節點串列。
• 不需逐一走訪或釋放節點，只要修改兩個鏈結即可完成串接，因此時間複雜度為 $O(1)$。

解題方法

設使用中的循環串列如下：

$$\text{first} \rightarrow \cdots \rightarrow \text{last} \rightarrow \text{first}$$

其中 *ptr 指向 last。

1. 先以 temp 記錄第一個節點：

   temp = (*ptr)->link;
   

2. 將原本的尾端節點 last 接到可用串列 avail：

   (*ptr)->link = avail;
   

3. 將 avail 改指向原循環串列的第一個節點。此時原本的循環串列便轉為可用串列：

   avail = temp;
   

4. 將原本的串列指標設為空指標：

核心觀念

本題考查「等價類別（Equivalence Classes）」與「不相交集合 Union-Find」的加權合併法（Weighted Union）。

每個元素起初各自形成一個集合：

$$\{0\},\{1\},\ldots,\{11\}$$

處理每一組等價關係 $a=b$ 時，先找出 $a$ 與 $b$ 所屬集合的樹根，再依下列規則合併：

1. 將較小集合的樹根接到較大集合的樹根。
2. 若兩集合大小相同，將樹根編號較大的樹根接到編號較小的樹根。
3. 合併後集合大小為兩集合大小之和。

等價關係具有傳遞性，例如：

$$0=4,\quad 7=4 \Rightarrow 0,4,7$$

因此三者屬於同一等價類別。

---

解題方法與合併過程

依題目給定順序逐一處理：

$$0=4,\ 3=1,\ 6=10,\ 8=9,\ 7=4,\ 6=8,\ 3=5,\ 2=11,\ 11=0$$

第 1 組：$0=4$

兩集合大小皆為 $1$，樹根分別為 $0$ 與 $4$。依規則，較小根 $0$ 作為新樹根：

$$\{0\}+\{4\}\longrightarrow \{0,4\}$$

樹根為 $0$，集合大小為 $2$。

---

第 2 組：$3=1$

兩集合大小皆為 $1$，樹根分別為 $3$ 與 $1$。因為 $1<3$，故樹根 $1$ 接到樹根 $3$：

$$\{3\}+\{1\}\longrightarrow \{1,3\}$$

樹根為 $3$，集合大小為 $2$。

---

第 3 組：$6=10$

兩集合大小皆為 $1$，樹根分別為 $6$ 與 $10$。因為 $6<10$，故樹根 $10$ 接到樹根 $6$：

$$\{6\}+\{10\}\longrightarrow \{6,10\}$$

樹根為 $6$，集合大小為 $2$。

---

第 4 組：$8=9$

兩集合大小皆為 $1$，樹根分別為 $8$ 與 $9$。因為 $8<9$，故樹根 $9$ 接到樹根 $8$：

$$\{8\}+\{9\}\longrightarrow \{8,9\}$$

樹根為 $8$，集合大小為 $2$。

---

第 5 組：$7=4$

元素 $7$ 屬於集合 $\{7\}$，而元素 $4$ 的樹根是 $0$，所以另一集合為 $\{0,4\}$。

兩集合大小分別為 $1$ 與 $2$，將較小的 $\{7\}$ 合併到較大的集合：

$$\{7\}+\{0,4\}\longrightarrow \{0,4,7\}$$

樹根為 $0$，集合大小為 $3$。

---

第 6 組：$6=8$

元素 $6$ 的樹根為 $6$，其集合為：

$$\{6,10\}$$

元素 $8$ 的樹根為 $8$，其集合為：

$$\{8,9\}$$

兩集合大小皆為 $2$。依題目規定，樹根編號較小者 $6$ 作為合併後的樹根：

$$\{6,10\}+\{8,9\} \longrightarrow \{6,8,9,10\}$$

樹根為 $6$，集合大小為 $4$。

---

第 7 組：$3=5$

本題要求填寫 C 語言程式碼，完成一個函數 listPointer invert(listPointer lead)，該函數的功能是反轉一個「單向鏈結串列」(singly linked list)。需要填寫的程式碼位於 while (lead) 迴圈內部，並且總共需要 4 條指令。

核心概念：反轉鏈結串列
反轉單向鏈結串列是指將鏈結串列的方向顛倒。原來的頭節點會變成尾節點，原來的尾節點會變成頭節點，並且所有節點的 next 指標都需要更新，使其指向前一個節點。

標準反轉鏈結串列的迭代方法：
通常使用三個指標來完成這個操作：

1. prev (或 previous): 指向當前節點的前一個節點。初始為 NULL。
2. current (或 lead): 指向當前正在處理的節點。初始為鏈結串列的頭節點。
3. next: 指向當前節點的下一個節點。用於在修改 current->next 之前暫存下一個節點的位置。

迭代步驟：
在 while (current != NULL) 迴圈中：

1. next = current->next; // 暫存下一個節點
2. current->next = prev; // 將當前節點的 next 指向 prev (反轉方向)
3. prev = current; // 將 prev 移動到當前節點
4. current = next; // 將 current 移動到下一個節點

迴圈結束後，prev 指向的就是反轉後鏈結串列的新頭節點。

題目給定的框架：

listPointer invert(listPointer lead)
{
    listPointer middle, trail; // middle, trail 是臨時指標
    middle = NULL; // middle 似乎是用来暂存反转后的新头

    // lead 是当前节点，相当于上面的 current 指针
    while (lead) { // 循环条件是 lead != NULL
        // --- 需要填寫 4 条指令 ---
        // 1. 暂存 lead 的下一个节点
        // 2. 将 lead 的 next 指向 middle (相当于 prev)
        // 3. 更新 middle 为 lead
        // 4. lead 移动到下一个节点
    }
    return middle; // middle 应该就是反转后的新头
}

對照框架與標準方法：

• 題目中的 lead 相當於標準方法中的 current。
• 題目中的 middle 相當於標準方法中的 prev (最終反轉後的新頭)。
• 我們還需要一個指標來暫存 lead 的下一個節點，這個角色在題目框架中沒有直接對應，所以我們需要用 trail 或另一個臨時變數來實現。

填寫指令：
我們需要 4 條指令來完成一次迭代：

1. 暫存 lead 的下一個節點：
   這個位置的指令應該是 trail = lead->next; (或者使用另一個臨時變數，但題目給了 trail，所以用它)。
   trail = lead->next;

2. 反轉 lead 的 next 指標：
   lead 的 next 應該指向原來的 middle (即 prev)。
   lead->next = middle;

3. 更新 middle 指標：
   middle 應該前進到當前節點 lead。
   middle = lead;

4. 更新 lead 指標：
   lead 應該移動到下一個節點，這個節點我們已經在第一步暫存到 trail 中了。
   lead = trail;

填寫後的程式碼：

本題要求使用 Floyd-Warshall 演算法，對圖 Fig.3 計算並寫出成本鄰接矩陣 A-1, A0, A1, 和 A2。

Floyd-Warshall 演算法：
Floyd-Warshall 演算法是一種用於尋找圖中所有節點對之間最短路徑的動態規劃演算法。它能夠處理帶權重的圖，包括負權邊，但不能處理負權環。

演算法的核心思想是：對於任意兩個節點 i 和 j，它們之間的最短路徑，要么是直接連接的邊，要么是經過某個中間節點 k 的路徑。演算法會迭代地考慮所有可能的中間節點 k，並更新節點 i 和 j 之間的最短路徑。

演算法公式：
設 D[i][j] 表示節點 i 到節點 j 的最短路徑長度。
初始時，D[i][j] 被設定為：

• 如果 i == j，則 D[i][j] = 0。
• 如果存在從 i 到 j 的邊，則 D[i][j] 為該邊的權重。
• 如果不存在從 i 到 j 的邊，則 D[i][j] = infinity (一個非常大的值，表示不可達)。

演算法的迭代更新步驟如下：
對於所有的中間節點 k (從 0 到 n-1)：
對於所有的起始節點 i (從 0 到 n-1)：
對於所有的終止節點 j (從 0 到 n-1)：
D[i][j] = min(D[i][j], D[i][k] + D[k][j])

圖 Fig.3 的分析：
圖 Fig.3 是一個有向圖，包含 4 個節點，編號為 0, 1, 2, 3。
邊及其權重如下：

• 0 -> 1 (權重 6)
• 0 -> 2 (權重 4)
• 1 -> 2 (權重 2)
• 2 -> 3 (權重 2)
• 3 -> 1 (權重 11)
• 3 -> 2 (權重 3)

節點數量： n = 4 (節點編號 0, 1, 2, 3)。
無限大 (Infinity)： 我們用一個足夠大的數來表示無限大，例如 INF。

初始鄰接矩陣 A-1 (k = -1, 即沒有中間節點)：
這個矩陣代表圖中直接的邊權重，或者節點自身到自身的距離為 0。
A[-1][i][j]

節點 0, 1, 2, 3。
INF 表示不可達。

    0   1   2   3
0 [ 0   6   4  INF ]
1 [ INF 0   2   INF ]
2 [ INF INF 0   2   ]
3 [ INF 11  3   0   ]

計算 A0 (k = 0)：
考慮以節點 0 作為中間節點。
對於所有 i, j，更新 A0[i][j] = min(A-1[i][j], A-1[i][0] + A-1[0][j])。

• A-1[i][0] 的值：

  • A-1[0][0] = 0
  • A-1[1][0] = INF
  • A-1[2][0] = INF
  • A-1[3][0] = INF

• A-1[0][j] 的值：

  • A-1[0][0] = 0
  • A-1[0][1] = 6
  • A-1[0][2] = 4
  • A-1[0][3] = INF

• 更新規則： 只有當 A-1[i][0] 和 A-1[0][j] 都不是 INF 時，才可能發生更新。

  • 當 i=0 時，A-1[0][0] = 0。更新 A0[0][j] = min(A-1[0][j], 0 + A-1[0][j])，沒有變化。
  • 當 j=0 時，A-1[0][0] = 0。更新 A0[i][0] = min(A-1[i][0], A-1[i][0] + 0)，沒有變化。
  • 對於其他 i, j，如果 A-1[i][0] 是 INF (即 i=1, 2, 3)，則 A-1[i][0] + A-1[0][j] 是 INF，不會更新 A-1[i][j]。

• 結論： 使用中間節點 0 不會改變任何路徑，因為除了 0 到 0 的路徑外，沒有其他節點可以透過 0 到達 0，或者從 0 到達其他節點再回到 0。
  因此，A0 矩陣與 A-1 矩陣相同。

    0   1   2   3
0 [ 0   6   4  INF ]
1 [ INF 0   2   INF ]
2 [ INF INF 0   2   ]
3 [ INF 11  3   0   ]

計算 A1 (k = 1)：
考慮以節點 1 作為中間節點。
對於所有 i, j，更新 A1[i][j] = min(A0[i][j], A0[i][1] + A0[1][j])。

• A0[i][1] 的值：

  • A0[0][1] = 6
  • A0[1][1] = 0
  • A0[2][1] = INF
  • A0[3][1] = 11

• A0[1][j] 的值：

  • A0[1][0] = INF
  • A0[1][1] = 0
  • A0[1][2] = 2
  • A0[1][3] = INF

• 檢查可能的更新：

  • i=0, j=2: A0[0][2] = 4. 考慮 A0[0][1] + A0[1][2] = 6 + 2 = 8. min(4, 8) = 4. 不變。
  • i=3, j=2: A0[3][2] = 3. 考慮 A0[3][1] + A0[1][2] = 11 + 2 = 13. min(3, 13) = 3. 不變。

• 結論： 使用中間節點 1 不會改變任何路徑。
  A1 矩陣與 A0 矩陣相同。

    0   1   2   3
0 [ 0   6   4  INF ]
1 [ INF 0   2   INF ]
2 [ INF INF 0   2   ]
3 [ INF 11  3   0   ]

計算 A2 (k = 2)：
考慮以節點 2 作為中間節點。
對於所有 i, j，更新 A2[i][j] = min(A1[i][j], A1[i][2] + A1[2][j])。

• A1[i][2] 的值：

  • A1[0][2] = 4
  • A1[1][2] = 2
  • A1[2][2] = 0
  • A1[3][2] = 3

• A1[2][j] 的值：

  • A1[2][0] = INF
  • A1[2][1] = INF
  • A1[2][2] = 0