111 地方特考三等 資訊處理 程式設計 考古題詳解

核心觀念

1. 運算子優先權（Operator Precedence）： 在 C 語言中，邏輯非運算子 ! 為單元運算子（Unary Operator），優先權等級為 2；取模運算子 % 為乘除類算術運算子（Multiplicative Operator），優先權等級為 3。單元運算子優先權高於算術運算子，因此運算式 !b % 2 依語法規則嚴格解析為 (!b) % 2，而非 !(b % 2)。
2. C 語言之真偽值判斷： 在 C 語言中，任何非 $0$ 數值皆視為真（True），數值 $0$ 視為偽（False）。

• 對任意非零整數 $b \neq 0$，$!b$ 之值為 $0$，故 (!b) % 2 恆為 $0$（False）。
• 僅當 $b = 0$ 時，$!0 = 1$，$1 \% 2 = 1$（True）。

3. 遞迴函式追蹤（Recursion Tracing）與呼叫堆疊（Call Stack）： 觀察函式之終止條件（Base Case）與遞迴轉移關係。回傳值若有係數乘法（如 2 * func1(...)），須於堆疊返回（Unwind）時逐層累乘。
4. 格式化輸出控制碼： printf("%3d %3d\n", a, b) 代表以十進位整數格式輸出，欄寬固定為 3，向右靠齊（不足 3 位補空白），兩數之間間隔 1 個空白，並於結尾換行；main 函式中的 printf("%3d", ...) 則無換行字元。

---

解題方法

1. 關鍵分支條件之嚴格語法分析

• if (b == 0)：遞迴終止條件，回傳 $a$。
• else if (a % 2 && b % 2)：當 $a$ 為奇數且 $b$ 為奇數時成立。
• else if (a % 2 && !b % 2)： 依優先權規則，!b % 2 等價於 (!b) % 2。進入此分支前已排除 $b == 0$，因此 $b \neq 0$ 恆成立。當 $b \neq 0$ 時，$!b = 0$，$0 \% 2 = 0$。此條件結果恆為 $0$（False），永遠不會執行。
• else if (!a % 2 && b % 2)： 同理，!a % 2 等價於 (!a) % 2。當 $a \neq 0$ 時，$!a = 0$，$0 \% 2 = 0$。只要 $a \neq 0$，此條件結果亦恆為 $0$（False），永遠不會執行。
• else： 當上述條件皆不成立時，執行 return 2 * func1(a / 2, b / 2);。

2. 遞迴呼叫單步追蹤（Trace）

從 main 函式呼叫 func1(19, 2) 開始推導：

• 第 1 次呼叫：func1(19, 2)

• 印出： 19 2\n

• 條件檢查：$b \neq 0$；$a\%2=1, b\%2=0$（條件一不成立）；條件二、條件三皆為偽。

• 執行 else：回傳 $2 \times \text{func1}(19/2, 2/2) = 2 \times \text{func1}(9, 1)$。

• 第 2 次呼叫：func1(9, 1)

• 印出： 9 1\n

• 條件檢查：$a\%2=1, b\%2=1$，滿足條件一 (a % 2 && b % 2)。

• 執行條件一：回傳 $\text{func1}((9+1)/2, (9-1)/2) = \text{func1}(5, 4)$。

• 第 3 次呼叫：func1(5, 4)

• 印出： 5 4\n

• 條件檢查：條件一、二、三皆不成立。

• 執行 else：回傳 $2 \times \text{func1}(5/2, 4/2) = 2 \times \text{func1}(2, 2)$。

• 第 4 次呼叫：func1(2, 2)

• 印出： 2 2\n

• 條件檢查：條件一、二、三皆不成立。

• 執行 else：回傳 $2 \times \text{func1}(2/2, 2/2) = 2 \times \text{func1}(1, 1)$。

• 第 5 次呼叫：func1(1, 1)

• 印出： 1 1\n

• 條件檢查：$a\%2=1, b\%2=1$，滿足條件一。

• 執行條件一：回傳 $\text{func1}((1+1)/2, (1-1)/2) = \text{func1}(1, 0)$。

• 第 6 次呼叫：func1(1, 0)

• 印出： 1 0\n

• 條件檢查：$b == 0$ 成立，回傳 $a = 1$。

3. 呼叫堆疊返回與計算

各層遞迴回傳值如下：

• 第 5 層：回傳 $\text{func1}(1, 0) = 1$
• 第 4 層：回傳 $2 \times \text{func1}(1, 1) = 2 \times 1 = 2$
• 第 3 層：回傳 $2 \times \text{func1}(2, 2) = 2 \times 2 = 4$
• 第 2 層：回傳 $\text{func1}(5, 4) = 4$
• 第 1 層：回傳 $2 \times \text{func1}(9, 1) = 2 \times 4 = 8$

main 函式執行 printf("%3d", func1(x, y))，輸出靠右對齊之整數 8（前補 2 個空白）。

---

選項分析

本題為程式追蹤題，程式中各條件分支判斷如下：

• if (b == 0)：正確作為終止基準，成功於第 6 次呼叫終止遞迴。
• else if (a % 2 && b % 2)：判斷兩數是否皆為奇數，於第 2 次及第 5 次呼叫觸發。
• else if (a % 2 && !b % 2) 與 else if (!a % 2 && b % 2)：因運算子優先權導致 !b % 2 恆為 $0$，兩分支在此情境下均無法進入，直接落入 else。
• else：承接所有偶數相除與分支未涵蓋之計算，提供 $2$ 倍乘積的遞迴展開。

---

解題技巧

1. 運算子優先權陷阱： 單元運算子 ! 的結合性強於二元運算子 %。若題目欲表達「$b$ 為偶數」，正確寫法必須加括號寫成 !(b % 2) 或 b % 2 == 0。
2. 命題背景延伸探討（二元最大公因數演算法 Stein's Algorithm）： 本題原型為求 $\gcd(a, b)$ 的二元 GCD 演算法。

本題核心觀念

1. 質數判定演算法（Trial Division 質數試除法）：

• 質數定義為大於 $1$ 且除 $1$ 與本身外無其他因數之正整數。
• 程式利用巢狀迴圈：外層 while y <= x 逐一檢查 $2$ 至 $x$ 的整數；內層 for i in range(2, y) 檢驗是否能被 $i$ 整除。若整除（y % i == 0），則設定 flag = False 並提早 break；若無任何因數，則 flag 維持 True，判定為質數。

2. Python 輸出格式控制：

• print(y, end='') 設定結尾字元為空字串，故輸出之數值不會換行亦無空格，緊密相連。

3. 氣泡排序法（Bubble Sort）原理與實作：

• 概念：兩兩比較相鄰元素，若前項大於後項則進行交換（In-place swap），每一回合將目前未排序區間的最大值「沉底」推移至右側。
• 複雜度與回合數：長度為 $n$ 的串列，共需進行 $n - 1$ 回合。第 $i$ 次排序（$i$ 從 $1$ 至 $n - 1$），內部比較次數為 $n - i$ 次。

---

解題方法與詳細推導

(一) 程式追蹤與輸出分析

1. 函式 func_2_1(x) 執行邏輯：

• 起始值 $y = 2$。
• 當 $y = 2$ 時：內層 range(2, 2) 為空序列，for 迴圈不執行，flag 維持 True，印出 2。
• 當 $y = 3$ 時：3 % 2 != 0，迴圈結束，印出 3。
• 當 $y = 4$ 時：4 % 2 == 0，flag = False，跳離不印出。
• 依此類推，該函式功能即為：依序找出 $2$ 到 $x$ 之間的所有質數，並連續不留空格印出。

2. 案例 1：輸入 $x = 15$

• 區間 $[2, 15]$ 的質數為：$2, 3, 5, 7, 11, 13$。
• func_2_1(15) 依序印出各質數且 end=''，結果為：23571113。

3. 案例 2：輸入 $x = 21$

• 區間 $[2, 21]$ 的質數為：$2, 3, 5, 7, 11, 13, 17, 19$。
• func_2_1(21) 依序印出各質數且 end=''，結果為：235711131719。

---

(二) 氣泡排序函式 func_2_2(x) 演算法設計

原始串列為 $x = [-5, 16, 30, -11, 26, -22]$，長度 $n = 6$。

1. 各回合追蹤驗算：

• 第 1 次排序（比對至索引 4）：
• $30 > -11 \rightarrow$ 交換；$30 > 26 \rightarrow$ 交換；$30 > -22 \rightarrow$ 交換。
• 結果：$[-5, 16, -11, 26, -22, 30]$（最大值 $30$ 到達定位）。
• 第 2 次排序（比對至索引 3）：
• $16 > -11 \rightarrow$ 交換；$26 > -22 \rightarrow$ 交換。

核心觀念

本題為典型的 C++ 物件導向程式設計（OOP）類別實作題，評量考生將類別規格書（介面宣告 .h）轉化為具體實作（.cpp）的實作能力。核心考點包含：

1. 封裝（Encapsulation）與資料隱藏（Data Hiding）：將屬性宣告為 private，並透過 public 的成員函數（Getter / Setter）進行存取與驗證，確保物件內部狀態的一致性與有效性。
2. 建構子（Constructor）與預設引數（Default Arguments）規範：

• 標頭檔 Rect.h 已宣告預設引數 explicit Rect(double = 1.0, double = 1.0);。依 C++ 語法標準，在實作檔（.cpp）定義建構子時，不可重複指定預設引數，否則會引發編譯錯誤（Redefinition of default argument）。

3. 常數成員函數（const Member Functions）：

• 檢查物件狀態而不修改屬性的檢索函數（如 getWidth、getLength、perimeter、area）需在函數標頭後方加上 const 修飾詞，實作時亦必須保留。

4. 屬性驗證與例外處理機制：

• 設定函數需驗證數值範圍為 $0.0 < \text{value} < 20.0$。主程式引入了 <stdexcept> 標頭檔，暗示當傳入不合法數值時，物件導向標準作法為拋出 std::invalid_argument 例外；亦可將數值重設為預設值 $1.0$。

5. 幾何計算公式：

• 周長公式：$\text{Perimeter} = 2 \times (\text{length} + \text{width})$
• 面積公式：$\text{Area} = \text{length} \times \text{width}$

---

解題方法

1. 判斷建構子之參數對應順序

主程式中建立物件：

Rect x, y(3.0, 4.0);

其對應的輸出結果為：

y: length = 4.0; width = 3.0; perimeter = 14.0; area = 12.0

分析可知：傳入的引數分別為 $3.0$ 與 $4.0$，而輸出顯示 $\text{width} = 3.0$ 且 $\text{length} = 4.0$。此外，在 Rect.h 的宣告順序中，setWidth 位於 setLength 之前。這明確指出建構子的第一個參數為寬度（width），第二個參數為長度（length）： $\text{Rect}(w, l) \implies \text{width} = w,\ \text{length} = l$

2. 建構子實作策略

在建構子內部，不宜直接對私有成員變數賦值，最佳實務是直接呼叫成員函數 setWidth(w) 與 setLength(l)。如此可重用邊界檢查邏輯，避免代碼重複（DRY 原則），確保物件在初始化時即符合邊界條件。

3. 邊界檢查與設定函數（setWidth / setLength）

題目規定：「長度和寬度均為大於 $0.0$ 且小於 $20.0$ 的浮點數」。 條件判斷式為： $0.0 < w < 20.0 \quad \text{與} \quad 0.0 < l < 20.0$ 主程式已包含 #include <stdexcept>，若傳入數值未符合區間條件，丟出 std::invalid_argument 例外；

核心觀念

1. 完美數（Perfect Number）之數學定義與因數求和： 正整數 $n$ 的「真因數（Proper Divisor）」指小於 $n$ 且能整除 $n$ 的所有正因數。若所有真因數之和恰好等於 $n$ 本身，即滿足： $\sum_{d \mid n, \, 1 \le d < n} d = n$ 則稱 $n$ 為完美數。程式設計的核心在於利用迴圈遍歷範圍內的整數，並對每個整數求其真因數總和進行比對。
2. 基底轉換（Radix Conversion）之短除法原理： 十進位整數轉換為 $B$ 進位制時，採用「除以基底取餘數法（短除法）」。每次將數值除以基底 $B$：

• 餘數（value % B）為該位數之數值。
• 商數（value / B）作為下一輪疊代的被除數。
• 越後計算出的餘數代表越高位元（Most Significant Digit）。

3. Java 字串前置串接（String Prepending）： 程式碼中運算式 oS = s + oS; 將新產生的低位元餘數轉為字串後串接於舊字串前端，恰好符合短除法「反向取餘數」組合出高位在前之特性。

---

解題方法

(一) 尋找小於 10,000 的完美數程式

要找出小於 10,000 的所有完美數，外層迴圈從 $2$ 檢查至 $9999$（最小的正整數完美數為 $6$，$1$ 的真因數總和為 $0$，故不為完美數）。 內層迴圈計算真因數和：最直觀的方法是走訪 $1$ 到 $n/2$；亦可走訪 $1$ 到 $\sqrt{n}$ 以大幅提升效率。由於 $N = 10000$ 規模較小，走訪至 $i \le n/2$ 簡潔明瞭且執行速度極快。

public class PerfectNumbers {
 public static void main(String[] args) {
 System.out.println("小於 10000 的完美數有：");
 for (int num = 2; num < 10000; num++) {
 int sum = 0;
 // 尋找 num 的所有真因數並累加
 for (int i = 1; i <= num / 2; i++) {
 if (num % i == 0) {
 sum += i;
 }
 }
 // 判斷真因數和是否等於自身
 if (sum == num) {
 System.out.println(num);
 }
 }
 }
}

註：小於 10,000 的完美數依序為 $6$、$28$、$496$、$8128$。

---

(二) 程式功能分析與執行追蹤

1. 程式功能： 本程式的功能為將使用者輸入的十進位正整數轉換為「八進位（Octal）」字串並印出。

• 運算式 s = value % 8：求出目前最低位的八進位數字。
• 運算式 oS = s + oS：將新取得的位數置於字串最左側（高位元位置）。
• 運算式 value = value / 8：將十進位數值右移一個八進位位元（去除已處理的最低位）。

2. 輸入追蹤與推導：

• 當輸入為 32 時：
• 第 1 次迴圈：$s = 32 \pmod 8 = 0$，$oS = "0" + "" = "0"$，$value = \lfloor 32 / 8 \rfloor = 4$