108 地方特考四等 資訊處理 程式設計概要 考古題詳解

核心觀念

本題測驗的核心為 Java 巢狀迴圈（Nested Loops）之控制流程與圖形輸出追蹤，主要評量以下重點：

1. 迴圈計數與終止條件：評量對計數型 for 迴圈初值、條件判斷式（<=）、步進值（++）之掌握。
2. 輸出方法之差異：

• System.out.print：輸出資料後不換行，後續輸出接續於同一列後方。
• System.out.println：輸出資料（此處為空白）並執行換行（Line Break）。

3. 字元與字串輸出特性：注意第一組內層迴圈輸出單一空格字元 ' '，第二組內層迴圈每次印出雙星號字串 "**"。

---

解題方法

解析此類圖形列印題，最穩健且標準的切入點為​「建立迴圈追蹤表（Trace Table）」，將程式結構依外層迴圈分為 5 次迭代，分別推導每列的空白數與星號數：

1. 外層迴圈：for (int i = 1; i <= 5; i++)

• 控制總列數，變數 $i$ 依序取值為 $1, 2, 3, 4, 5$，共執行 5 列。

2. 第一組內層迴圈（輸出空白）：for (int j = 1; j <= i; j++)

• 控制每列前置空白數。當外層為第 $i$ 列時，$j$ 從 $1$ 遞增至 $i$，故印出 $i$ 個空白 ' '。

3. 第二組內層迴圈（輸出星號）：for (int j = 1; j <= 6 - i; j++)

• 控制星號輸出。迴圈條件為 $j \le 6 - i$，每次迴圈印出 "**"（2 個星號）。
• 總星號數為：$2 \times (6 - i) = 12 - 2i$ 個星號。

4. 換行指令：System.out.println

• 兩組內層迴圈執行完畢後換行，進入下一列。

逐列執行推導表

外層變數 $i$	空白迴圈次數 ($j \le i$)	印出空白數	星號迴圈次數 ($j \le 6-i$)	印出星號數 ($2 \times$ 次數)	該列輸出樣式
$i = 1$	$1 \le j \le 1$（1 次）	1	$1 \le j \le 5$（5 次）	10	1 個空白 + 10 個星號
$i = 2$	$1 \le j \le 2$（2 次）	2	$1 \le j \le 4$（4 次）	8	2 個空白 + 8 個星號

核心觀念

1. 質數（Prime Number）定義： 質數是指大於 1 的正整數中，除了 1 和自身以外，無法被其他正整數整除的數。最小的質數為 2。
2. 試除法（Trial Division）及其上界： 若正整數 $n$ 為合數，則必可分解為兩個整數因數相乘，即 $n = a \times b$。若 $a$ 與 $b$ 皆大於 $\sqrt{n}$，則 $a \times b > n$，產生矛盾。因此合數 $n$ 必存在至少一個不大於 $\sqrt{n}$ 的因數。檢驗 $n$ 是否為質數時，僅需檢查 $2$ 到 $\lfloor\sqrt{n}\rfloor$ 之間的所有整數是否能整除 $n$ 即可，運算條件可表達成 $d \times d \le n$，時間複雜度由 $O(n)$ 降至 $O(\sqrt{n})$。
3. 巢狀迴圈（Nested Loops）與流程控制：

• 外層迴圈：遍歷候選數值範圍（$2$ 至 $499$）。
• 內層迴圈：對當前數值進行因數試除，搭配布林旗標（Boolean Flag）記錄是否為質數；一旦發現能被整除（餘數為 0），立即使用 break 敘述中斷內層迴圈，以節省不必要的計算。

4. 國考題意限制遵循： 題目明訂「不要另訂 class、method 或 function」，因此不得宣告額外的輔助類別（如自訂演算法類別）或自訂方法（如 static boolean isPrime(int n)），所有檢驗流程、計數與列印均須直接整合在 main 方法中。

---

解題方法

1. 定義變數與計數器： 宣告整數變數 count 作為累計質數個數的計數器，初值設為 0。
2. 外層迴圈遍歷候選區間： 題目要求「小於 500 的所有質數」，因此外層迴圈變數 $i$ 從最小質數 $2$ 開始遞增，終止條件為 $i < 500$（即最大檢查至 499）。
3. 內層迴圈進行質數判定：

• 每輪外層迴圈開始時，宣告布林旗標 boolean isPrime = true;。
• 內層迴圈以變數 $j$ 作為除數，從 $2$ 開始檢查，條件設為 $j \times j \le i$。
• 若 $i \pmod j == 0$（即 i % j == 0），代表 $i$ 為合數，將 isPrime 設為 false 並執行 break 跳出內層迴圈。

4. 輸出結果與累加計數：

核心觀念

本題評量遞迴函式（Recursive Method）之設計與邏輯分支，涵蓋以下核心要點：

1. 遞迴的兩大要素：

• 基準條件／終止條件（Base Case）：遞迴停止呼叫自身並直接回傳結果的臨界狀態，用於避免程式陷入無窮遞迴導致堆疊溢位（StackOverflowError）。
• 遞迴步驟（Recursive Step）：將大問題分解為結構相同但規模較小的子問題，並藉由自我呼叫進行數值累加。

2. 正偶數的定義與數論性質：

• 正偶數集合為 $\{2, 4, 6, 8, \dots\}$。
• 包含 $0$ 與 $1$ 的情況下，小於或等於其值的正偶數不存在，其總和定義為 $0$。

3. 奇偶數分流處理：

• 若 $x$ 為偶數（$x \pmod 2 = 0$），當前數值須計入總和，並遞迴尋求下一個偶數（$x - 2$）的總和。
• 若 $x$ 為奇數（$x \pmod 2 \ne 0$），當前數值不屬於正偶數，不應計入總和，問題可直接等價轉化為求小於或等於 $x - 1$ 的正偶數總和。

---

解題方法

本題要求計算小於或等於 $x$ 的所有正偶數總和。依據遞迴架構，解題步驟推導如下：

步驟一：確立終止條件（Base Case）

最小的正偶數為 $2$。因此，當傳入的參數 $x \le 1$ 時（例如題目測試資料中的 $x = 0$ 或 $x = 1$），集合中沒有任何正偶數，應直接回傳 $0$： $x \le 1 \implies \text{sumOfEvens}(x) = 0$

步驟二：處理奇數情況（Odd Case）

若 $x$ 為奇數（即 x % 2 != 0），因為 $x$ 本身不是偶數，不得累加至總和中。小於或等於奇數 $x$ 的正偶數集合，與小於或等於 $x - 1$ 的正偶數集合完全相同，故直接回傳： $\text{sumOfEvens}(x) = \text{sumOfEvens}(x - 1)$

步驟三：處理偶數情況（Even Case）

若 $x$ 為大於等於 $2$ 的偶數（即 x % 2 == 0），$x$ 本身為有效正偶數，應將 $x$ 加上前一個偶數（$x - 2$）為上限的正偶數總和： $\text{sumOfEvens}(x) = x + \text{sumOfEvens}(x - 2)$

數學遞迴定義式

綜合上述分析，可建立完整的遞迴關係式：

$$\text{sumOfEvens}(x) = \begin{cases} 0, & \text{若 } x \le 1 \\ \text{sumOfEvens}(x - 1), & \text{若 } x > 1 \text{ 且 } x \text{ 為奇數} \\ x + \text{sumOfEvens}(x - 2), & \text{若 } x > 1 \text{ 且 } x \text{ 為偶數} \end{cases}$$

---

選項分析

本題為程式實作題（申論題），無選項。以下針對題目給定的五組測試資料進行程式追蹤與驗證：

1. sumOfEvens(0)：

• 滿足 $x \le 1$ 條件，直接回傳 $0$。
• 輸出：sumOfEvens(0) = 0（正確）。

核心觀念

1. Python 資料結構特性（串列 List 與 字典 Dictionary）：

• 串列（list）：以連續整數為索引的有序序列。在 Python 中，不能直接對超過現有索引長度的位置進行指定賦值（如 list[k] = v，當 $k \ge \text{len}(list)$ 時會拋出 IndexError）。
• 字典（dict）：以雜湊表（Hash Table）實作的鍵值對（Key-Value Pair）映射結構。可動態以任意不可變物件作為鍵新增或查詢項目（如 dict[k] = v）。

2. 經典演算法「兩數之和」（Two Sum）：

• 核心邏輯在於走訪數列時，對於當前數值 $num$，計算其互補數 $other = target - num$。
• 利用暫存結構記錄「數值 $\to$ 出現索引」，達到平均時間複雜度 $O(n)$ 即可找出相加等於目標值之兩數索引。

3. 內建函式與運算子：

• enumerate(nums)：每次迭代同時產生目前元素之「索引（index）」與「數值（num）」。
• in 運算子：在串列中為線性搜尋（$O(n)$），在字典中則為檢查「鍵（Key）」是否存在（平均 $O(1)$）。

---

解題方法

本題在國考評分上存在「純語法嚴格執行」與「命題原意（修正筆誤）」兩種層次，標準作答須依序推導說明：

一、 嚴格依原題程式碼追蹤（語法與執行階段）

1. 執行第一道呼叫 secret([1, 3, 5], 4)：

• 函式第 2 行宣告 seen = []，建立一個長度為 $0$ 的空串列。
• 進入 for 迴圈第 1 輪：index = 0, num = 1。
• 計算互補數：$other = target - num = 4 - 1 = 3$。
• 判斷 if other in seen: $\to$ 3 in [] 為 False。
• 進入 else: 區塊，執行 seen[num] = index，即 seen[1] = 0。
• 程式中斷：由於 seen 為長度 0 的空串列，索引 1 已超出串列邊界，Python 直譯器立即拋出 IndexError: list assignment index out of range，導致程式崩潰中斷，後續所有語句均無法執行。

---

二、 命題原意推導（假設第 2 行更正為字典 seen = {}）

出題委員原意係以 Python 字典實作經典 Two Sum 演算法，若將 seen = [] 視為出題筆誤並修正為 seen = {}，各次呼叫推導如下：

1. 第一組：print(secret([1, 3, 5], 4))

• 初始：seen = {}
• 輪次 1（index = 0, num = 1）：
• $other = 4 - 1 = 3$。
• $3 \notin seen$，進入 else 執行 seen[1] = 0（目前 seen = {1: 0}）。
• 輪次 2（index = 1, num = 3）：
• $other = 4 - 3 = 1$。
• $1 \in seen$ 成立，執行 return [seen[1], index] $\to$ 回傳 [0, 1]。
• 輸出結果：[0, 1]

2. 第二組：print(secret([2, 3, 6, 8, 10], 16))

• 初始：seen = {}
• 輪次 1（index = 0, num = 2）：$other = 16 - 2 = 14 \notin seen$，寫入 seen[2] = 0。

核心觀念

本題為標準的 Java 物件導向程式設計（OOP）實作題，評量考生對基礎語法與物件導向核心特性的掌握程度，主要涵蓋以下重點：

1. 繼承（Inheritance）與方法覆寫（Method Overriding）：子類別 CustomTee 繼承父類別 TeeShirt，並覆寫繼承自 java.lang.Object 的 public String toString 方法，提供自訂的字串表現形式。
2. 封裝（Encapsulation）與存取權限（Access Modifiers）：父類別宣告為 private 的欄位（如 orderNumber、size、color、price），子類別無法直接存取，必須透過父類別所宣告的 public 取值方法（Getter Methods）間接取得。
3. 物件陣列（Array of Objects）之建立與操作：

• 物件陣列宣告僅配置參考指標空間，陣列元素預設為 null，必須透過 new 逐一實例化各個元素。
• 透過迴圈巡訪（Traversal）批次初始化屬性、呼叫方法與累加數值。

4. 業務邏輯連動：觀察 TeeShirt 類別可發現，該類別並無 setPrice 方法，價格係於呼叫 setSize 時由內部邏輯自動指派。

---

解題方法

（一）TeeShirt 類別之 toString

對照題目提供的「執行結果」，若單純印出父類別 TeeShirt，其屬性包含訂單編號（orderNumber）、尺寸（size）、顏色（color）與價格（price）。

• 第一行輸出訂單編號：Order # 100。
• 第二行縮排 4 格空白（或定位字元 \t），輸出描述： Description: S red。
• 第三行縮排 4 格空白，輸出價格： Price: $19.99。
• 因程式碼身處 TeeShirt 類別內部，可直接存取自身的私有成員變數。

（二）CustomTee 類別之 toString

子類別 CustomTee 增加了自訂標語屬性 slogan。

• 觀察執行結果，標語插入於 Description 與 Price 之間： Slogan: Cute Girl。
• 關鍵切入點：CustomTee 為子類別，而父類別 TeeShirt 的屬性皆為 private，在子類別中直接存取 orderNumber 等變數將導致編譯錯誤；因此必須呼叫 getOrderNumber、getSize、getColor、getPrice 取得父類別屬性值，而自身欄位 slogan 則可直接存取。

（三）DemoTees 類別之 main 實作

題目要求「以 array 的方式和兩個 for 迴圈，產生 5 件 T 恤，依序印出每件 T 恤屬性，最後加總 5 件的總價」：

1. 陣列配置：宣告長度為 5 的 CustomTee 陣列： CustomTee[] tees = new CustomTee[5];
2. 第一個 for 迴圈（產生與初始化）：

• 巡訪索引 $i = 0$ 至 $4$。
• 實例化各元素：tees[i] = new CustomTee;。
• 依序設定訂單編號：tees[i].setOrderNumber(100 + i);。
• 觀察執行結果可知：
• 前 2 件（$i < 2$）：尺寸為 "S"、顏色為 "red"、標語為 "Cute Girl"（呼叫 setSize("S") 自動設定價格為 $19.99）。
• 後 3 件（$i \ge 2$）：尺寸為 "XXL"、顏色為 "blue"、標語為 "Happy Boy"（呼叫 setSize("XXL") 自動設定價格為