109 年 國立臺灣大學工程科學及海洋工程學系碩士班丁組《計算機概論（A）》

這題主要在考驗學生對於電腦效能基本指標的理解，包括時脈頻率、每條指令時脈數 (CPI) 以及指令執行數，並進一步探討 RISC/CISC 設計哲學的差異。

首先，我們需要了解電腦效能的基本公式：
執行時間 (Execution Time) = 指令執行數 (Number of Instructions) × 每條指令時脈數 (CPI) / 時脈頻率 (Clock Rate)
或者
執行時間 (Execution Time) = 指令執行數 (Number of Instructions) × 每條指令的時脈數 (CPI) × 時脈週期時間 (Clock Cycle Time)
其中，時脈週期時間 (Clock Cycle Time) = 1 / 時脈頻率 (Clock Rate)。

題目中提到「Computer B performs as fast as Computer A」，這意味著它們的執行時間是相同的。

a. 計算 Computer B 的 CPI：
我們知道 Computer A 的執行時間 = (100 × 10^6 指令) × 1.8 (CPI) / (3.6 × 10^9 Hz)。
Computer B 的執行時間 = (100 × 10^6 指令) × CPI_B / (2.8 × 10^9 Hz)。
由於執行時間相同，我們可以得到：
(100 × 10^6) × 1.8 / (3.6 × 10^9) = (100 × 10^6) × CPI_B / (2.8 × 10^9)
1.8 / 3.6 = CPI_B / 2.8
0.5 = CPI_B / 2.8
CPI_B = 0.5 × 2.8 = 1.4

【答案】1.4

b. 比較 Computer A 和 B 的快取大小：
題目提到 Computer A 和 B 使用相同的 CPU 架構，但時脈頻率和快取大小不同。Computer A 的時脈頻率是 3.6 GHz，CPI 是 1.8。Computer B 的時脈頻率是 2.8 GHz，CPI 是 1.4。
雖然題目沒有直接給出快取大小，但通常來說，較高的時脈頻率和較低的 CPI 意味著 CPU 執行指令的效率更高。然而，這裡的關鍵是「相同的 CPU 架構」。在相同的 CPU 架構下，如果一個系統的時脈頻率較高 (Computer A)，但 CPI 也較高，而另一個系統時脈頻率較低 (Computer B)，但 CPI 也較低，這可能暗示著它們在記憶體存取或快取效率上有差異。

一般而言，CPU 的效能受到指令執行數、CPI 和時脈頻率的影響。如果 Computer A 和 B 的 CPU 架構相同，但時脈頻率不同，且 CPI 也不同，這說明它們的微架構可能存在細微差異，或是記憶體子系統（包括快取）的效能不同。

題目中提到「Computer B performs as fast as Computer A」，這表示整體效能相似。
Computer A: 指令數 100M, 時脈 3.6G, CPI 1.8 => 總時脈週期數 = 100M * 1.8 = 180M
Computer B: 指令數 100M, 時脈 2.8G, CPI 1.4 => 總時脈週期數 = 100M * 1.4 = 140M

因為 Computer A 的時脈頻率 (3.6 GHz) 高於 Computer B (2.8 GHz)，但兩者的執行時間卻相同，這意味著 Computer A 在執行相同指令數時，所花費的總時脈週期數 (180M) 比 Computer B (140M) 要多。
如果 CPU 架構相同，CPI 的差異主要與指令的執行複雜度和記憶體存取延遲有關。較低的 CPI (如 Computer B 的 1.4) 通常表示 CPU 在執行指令時，能夠更少地等待記憶體（快取命中率高）。

在此情況下，雖然題目沒有直接說明，但通常 CPU 設計師會透過較大的快取來降低記憶體延遲，從而提高 CPI（尤其是在時脈頻率較低時，可能需要更大的快取來彌補）。然而，從效率的角度來看，Computer B 以較低的時脈和較低的 CPI 達到了與 Computer A 相同的效能，這暗示著 Computer B 的記憶體子系統（包含快取）可能更有效率，或者說，它的快取能夠更好地滿足 CPU 的需求，從而降低了 CPI。

在相同的 CPU 架構下，如果一個系統的時脈頻率較低但 CPI 也較低，且整體效能與高時脈系統相當，這通常意味著該系統的記憶體存取延遲較低，這往往是由於較大的快取所達成。因此，Computer B 的快取可能更大。

這題考驗對 C 語言參數傳遞機制（傳值與傳址）、指標操作、巨集定義以及位元運算性質的理解。

a. Code A 是否可行：
Code A 的函數簽名是 void Swap (int a, void b)。
在 C 語言中，函數參數的傳遞預設是「傳值」(pass-by-value)。這意味著當你呼叫 Swap(a, b) 時，變數 a 和 b 的值會被複製一份傳遞給函數內部的局部變數 a 和 b。函數內部對這兩個局部變數進行的任何修改（例如 a ^= b;）都不會影響到函數外部原始變數 a 和 b 的值。
此外，void b 作為函數參數是無效的，函數參數必須指定類型。即使假設是 int b，傳值機制依然會導致交換失敗。

【答案】Code A 不可行。因為 C 語言預設是「傳值」參數傳遞，函數內部對參數的修改不會影響到函數外部的原始變數。此外，void b 作為函數參數是無效的。

b. 證明 XOR 運算可以交換兩個整數：
假設我們有兩個整數 A 和 B，我們要證明透過以下步驟可以交換它們的值，而不使用臨時變數：

1. A = A ^ B
2. B = A ^ B
3. A = A ^ B

證明過程：
初始狀態：變數 A 和 B 分別儲存值 $v_A$ 和 $v_B$。

步驟 1: A = A ^ B
此時 A 的值變為 $v_A \oplus v_B$ (其中 $\oplus$ 代表 XOR 運算)。
B 的值仍為 $v_B$。

步驟 2: B = A ^ B
將步驟 1 中 A 的新值 $(v_A \oplus v_B)$ 與 B 的舊值 $(v_B)$ 進行 XOR：
B 的新值 = $(v_A \oplus v_B) \oplus v_B$
根據 XOR 的結合律和性質 ($X \oplus X = 0$, $X \oplus 0 = X$)：
B 的新值 = $v_A \oplus (v_B \oplus v_B)$
B 的新值 = $v_A \oplus 0$
B 的新值 = $v_A$
此時，B 的值已經變成了原始 A 的值 ($v_A$)。
A 的值仍為 $v_A \oplus v_B$。

步驟 3: A = A ^ B
將 A 的當前值 $(v_A \oplus v_B)$ 與 B 的新值 $(v_A)$ 進行 XOR：
A 的新值 = $(v_A \oplus v_B) \oplus v_A$
根據 XOR 的交換律和結合律：
A 的新值 = $(v_A \oplus v_A) \oplus v_B$
A 的新值 = $0 \oplus v_B$
A 的新值 = $v_B$
此時，A 的值已經變成了原始 B 的值 ($v_B$)。

經過這三個步驟，A 的值變為 $v_B$，B 的值變為 $v_A$，成功交換了兩個整數的值。

【答案】證明如上所述，利用 XOR 的交換律、結合律以及 $X \oplus X = 0$ 和 $X \oplus 0 = X$ 的性質，可以證明 XOR 運算序列 a ^= b; b ^= a; a ^= b; 能夠交換變數 a 和 b 的值。

c. Code B 和 Code C 的優缺點比較：
Code B (指標傳遞)

void Swap (int *a, void *b) // 假設 void *b 應為 int *b
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

• 優點：

核心觀念

本題考查 Fibonacci 數列的遞迴定義，以及遞迴與迭代兩種程式設計方法。

數列定義為：

$$Fib(n)= \begin{cases} 0, & n=0,\\ 1, & n=1,\\ Fib(n-1)+Fib(n-2), & n>1. \end{cases}$$

因此，計算 $Fib(n)$ 時必須處理兩個基底條件：

• $n=0$ 時回傳 $0$。
• $n=1$ 時回傳 $1$。

當 $n>1$ 時，依定義計算 $Fib(n-1)+Fib(n-2)$。

---

解題方法一：遞迴法

遞迴法直接按照題目給定的數學定義撰寫。函式在 $n>1$ 時，呼叫自身計算前兩項，再將結果相加。

int fib_rec(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fib_rec(n - 1) + fib_rec(n - 2);
}

以 $Fib(5)$ 為例，執行過程為：

$$Fib(5)=Fib(4)+Fib(3)$$ $$Fib(4)=Fib(3)+Fib(2)$$ $$Fib(3)=Fib(2)+Fib(1)$$

最後利用 $Fib(0)=0$、$Fib(1)=1$，逐層回傳並完成加總：

$$Fib(5)=5$$

遞迴法複雜度

每個非基底節點會再產生兩個子問題，因此會重複計算許多相同的 Fibonacci 項，例如 $Fib(3)$ 會被多次計算。

• 時間複雜度：$O(2^n)$，亦可寫成 $O(\varphi^n)$，其中 $\varphi$ 為黃金比例。
• 空間複雜度：$O(n)$，來自遞迴呼叫堆疊的最大深度。

---

解題方法二：迭代法

迭代法由小到大計算 Fibonacci 數列，先掌握目前連續兩項：

• prev2 表示前前項。
• prev1 表示前一項。
• current 表示目前要計算的新項。

每次依照公式：

$$current=prev1+prev2$$

計算後向前更新：

$$prev2 \leftarrow prev1$$ $$prev1 \leftarrow current$$

核心觀念

Palindrome（回文）是指字串從左至右與從右至左讀取結果相同。若字串長度為 $n$，位置為 $i$ 的字元，其對稱位置為：

$$n-1-i$$

因此，判斷回文只需比較：

$$str[i] = str[n-1-i]$$

最長回文子字串則可利用「中心擴展法」：每個回文都具有中心，中心可能是：

• 單一字元：奇數長度回文，例如 aba
• 兩個相鄰字元之間：偶數長度回文，例如 abba

從每個可能中心向左右擴展，即可找出以該中心為核心的最長回文。

---

a. palindrome(str)

解題方法

只需比較字串兩端，逐步向中央靠近：

• 比較第 $i$ 個字元與第 $n-1-i$ 個字元。
• 若有任一組不同，立即判定不是回文。
• 所有對稱位置都相同，才是回文。

只需檢查前半段，因為後半段的比較會重複。

參考程式碼

以下以 C++ 為例：

bool palindrome(const string& str) {
    int left = 0;
    int right = static_cast<int>(str.length()) - 1;

    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

範例

對 "abba"：

比較	結果
a 與 a	相同
b 與 b	相同

所有對稱字元皆相同，因此回傳 true。

對 "xyz"：

比較	結果
x 與 z	不同

立即回傳 false。

複雜度

最多比較 $\lfloor n/2 \rfloor$ 組字元，因此：

$$T(n)=O(n)$$

只使用左右兩個索引：

$$S(n)=O(1)$$

---

b. longest_palindrome(str)

回傳格式

令位置採用 0-based indexing：

• "mississippi" 中的 "ississi" 起始位置為 $1$
• 長度為 $7$

因此回傳：

position = 1
length = 7

解題方法：中心擴展法

對每個位置 $i$，分別檢查兩種中心：

奇數長度回文

以 i 為中心：

left = i
right = i

例如：

aba
 ^

左右同時向外擴展，只要：

str[left] == str[right]

就代表回文範圍可以擴大。

偶數長度回文

以 i 與 i + 1 之間為中心：

left = i
right = i + 1

例如：

abba
 ^^

同樣向左右擴展。

每次得到一個回文後，計算：

$$length = right-left+1$$

若長度大於目前最佳答案，就更新起始位置與長度。

題目要求長度 $>2$，因此長度為 $1$ 或 $2$ 的回文不列入答案。

參考程式碼

核心觀念

排列（permutation）是將 $k$ 個不同符號全部取出，並按照不同順序排列。$k$ 個不同符號共有：

$$k! = k \times (k-1) \times \cdots \times 2 \times 1$$

種排列。

例如集合 $\{a,b,c\}$ 有：

$$3! = 6$$

種排列。

本題的核心是使用「回溯法」（backtracking）逐一決定每個位置放置的符號：

1. 第 1 個位置可放 $k$ 個符號中的任意一個。
2. 第 2 個位置可放剩下的 $k-1$ 個符號。
3. 第 3 個位置可放剩下的 $k-2$ 個符號。
4. 所有位置都填滿時，得到一組完整排列。
5. 回到上一層，改選其他尚未使用的符號。

---

解題方法：回溯法

以 list = [a, b, c] 為例，排列樹如下：

第 1 位選 a
├── 第 2 位選 b
│   └── 第 3 位選 c → abc
└── 第 2 位選 c
    └── 第 3 位選 b → acb

第 1 位選 b
├── 第 2 位選 a
│   └── 第 3 位選 c → bac
└── 第 2 位選 c
    └── 第 3 位選 a → bca

第 1 位選 c
├── 第 2 位選 a
│   └── 第 3 位選 b → cab
└── 第 2 位選 b
    └── 第 3 位選 a → cba

遞迴函式需要記錄：

• path：目前已經排列好的部分。
• remaining：尚未使用的符號。
• 當 remaining 為空時，表示完成一組排列。

---

關鍵程式碼

def permute(items):
    result = []

    def backtrack(path, remaining):
        # 所有符號都已使用，形成一組完整排列
        if len(remaining) == 0:
            result.append(path[:])
            return

        # 依序選擇一個尚未使用的符號
        for i in range(len(remaining)):
            symbol = remaining[i]

            # 選擇 symbol
            path.append(symbol)

            # 移除 symbol，進入下一層
            next_remaining = remaining[:i] + remaining[i + 1:]
            backtrack(path, next_remaining)

            # 回溯：撤銷選擇
            path.pop()

    backtrack([], items)
    return result

使用方式：

print(permute(["a", "b", "c"]))

輸出內容為：

[
    ["a", "b", "c"],
    ["a", "c", "b"],
    ["b", "a", "c"],
    ["b", "c", "a"],
    ["c", "a", "b"],
    ["c", "b", "a"]
]

輸出順序取決於輸入順序與迴圈順序，但內容必須包含全部 $k!$ 組排列。

---

演算法正確性

不重複