108 高普考普通考試 資訊處理 程式設計概要 考古題詳解

核心觀念

本題評量巢狀迴圈（Nested Loops）的執行流程控制與圖形輸出規律建模能力，為國考資訊處理類科《程式設計概要》的經典基本題型。核心觀念包含：

1. 巢狀迴圈的控制分工：

• 外層迴圈（Outer Loop）：負責控制輸出的「列數（Rows）」與換行時機。
• 內層迴圈（Inner Loop）：負責控制該列中各「行（Columns）」所輸出的字元內容與次數。

2. 輸出函數的差異：

• System.out.print：輸出字元後不換行，用於在同一列連續輸出空白或星號。
• System.out.println：輸出換行字元（移至下一列開頭）。

3. 線性關係規律推導：

• 圖形輸出題必須將幾何構圖轉換為代數關係式。設外層列指標為 $i$，推導出該列所需「空白字元數」與「星號字元數」關於 $i$ 的一次方程式（等差數列）。

---

解題方法

第一部分：分析原程式 PreStars 的輸出結果

原程式結構如下：

for (int i=1; i<=5; i++) {
 for (int j=1; j<=i; j++)
 System.out.print('*');
 System.out.println;
}

追蹤外層與內層迴圈變數的迭代過程：

• 外層迴圈 $i$ 從 $1$ 遞增至 $5$，共執行 $5$ 次，代表輸出 $5$ 列。
• 當 $i = 1$：內層 $j$ 範圍為 $1 \le j \le 1$，執行 $1$ 次，印出 *，接著換行。
• 當 $i = 2$：內層 $j$ 範圍為 $1 \le j \le 2$，執行 $2$ 次，印出 **，接著換行。
• 當 $i = 3$：內層 $j$ 範圍為 $1 \le j \le 3$，執行 $3$ 次，印出 ***，接著換行。
• 當 $i = 4$：內層 $j$ 範圍為 $1 \le j \le 4$，執行 $4$ 次，印出 ****，接著換行。
• 當 $i = 5$：內層 $j$ 範圍為 $1 \le j \le 5$，執行 $5$ 次，印出 *****，接著換行。

因此，原程式會輸出一個高度為 $5$ 列、靠左對齊的直角三角形星號圖形。

---

第二部分：修改程式以輸出目標星號構圖

步驟一：分析目標圖形的數學規律

題目要求的構圖共有 $10$ 列，每列由前導空白（Space）與星號（*）組成。 以列指標 $i$（令 $i$ 從 $1$ 到 $10$）建立對應關係表：

列號 $i$	前導空白數	星號數	規律推導
$1$	$0$	$10$	空白 $= i - 1$；星號 $= 11 - i$
$2$	$1$	$9$	空白 $= i - 1$；星號 $= 11 - i$
$3$	$2$	$8$	空白 $= i - 1$；星號 $= 11 - i$
$\vdots$	$\vdots$	$\vdots$	$\vdots$
$10$	$9$	$1$	空白 $= i - 1$；星號 $= 11 - i$

通式驗算：

• 前導空白數為公差為 $+1$ 的等差數列：首項為 $0$，故第 $i$ 列的空白數為 $i - 1$。
• 星號數為公差為 $-1$ 的等差數列：首項為 $10$，故第 $i$ 列的星號數為 $10 - (i - 1) = 11 - i$。

步驟二：程式修改架構設計

維持題目要求的「巢狀 for 迴圈架構」與「小修」原則，評分實務上採納以下兩種標準作法：

• 解法 A（經典雙內層迴圈法）： 外層迴圈維持 $i$ 控制列數（範圍改為 $1$ 到 $10$）。

核心觀念

本題評量遞迴副程式（Recursive Subroutine）​的設計能力與字串處理技巧，重點概念包含：

1. 遞迴三要素：

• 基底條件（Base Case / 終止條件）：停止遞迴並直接回傳結果的邊界，避免無窮遞迴導致堆疊溢位（StackOverflowError）。
• 遞迴步驟（Recursive Step）：將原問題拆解為結構相同但規模較小的子問題。
• 向終止條件逼近：每次遞迴呼叫時，傳入的狀態必須往基底條件推進。

2. 呼叫堆疊（Call Stack）與回溯特性（Backtracking）： 題目要求輸出反向整數串（從索引 $n-1$ 倒數輸出至 $x$）。在副程式參數固定為 (int[] arr, int x) 且不可增減參數的限制下，必須利用呼叫堆疊的「後進先出（LIFO）」特性：先遞迴深入至陣列尾端（$x$ 逐次加 1 逼近 $n-1$），於回溯階段（Return）才將當前元素 $arr[x]$ 串接在後方。

---

解題方法

1. 題意與子問題分析

給定陣列長度為 $n$（即 arr.length），需回傳的整數串為： $arr[n-1], arr[n-2], \dots, arr[x+1], arr[x]$

觀察子問題的關係：

• 若已取得 reverse(arr, x + 1) 的結果：$arr[n-1] \dots arr[x+1]$。
• 則 reverse(arr, x) 的完整字串即為：reverse(arr, x + 1) + " " + arr[x]。

2. 基底條件（Base Case）設計

• 極限邊界：題目指出 $x \le n$。若 $x = n$（即 $x \ge arr.length$），表示不包含任何元素，應回傳空字串 ""。
• 最後一個元素：當 $x = n - 1$（即 arr.length - 1）時，為倒序字串的第一個輸出元素（即 $arr[n-1]$）。此時直接將該整數轉為字串回傳，不需前置空格，作為遞迴終止的基準點。

3. 追蹤驗算（Trace）

以 reverse(intArr, 7) 為例（其中 intArr 長度 $n=10$）：

1. 呼叫 reverse(arr, 7)：等待 reverse(arr, 8) 的結果。
2. 呼叫 reverse(arr, 8)：等待 reverse(arr, 9) 的結果。
3. 呼叫 reverse(arr, 9)：符合 $x = 9 = n-1$，直接回傳字串 "10"。
4. 回溯至第 2 步：回傳 "10" + " " + arr[8] $\rightarrow$ "10 9"。
5. 回溯至第 1 步：回傳 "10 9" + " " + arr[7] $\rightarrow$ "10 9 8"。

輸出結果與題目範例完全吻合，且開頭與尾端均無多餘空格。

---

選項分析

核心觀念

本題為經典的已排序串列原地去重複演算法（In-place Remove Duplicates from Sorted Array），核心測驗考生對以下四項觀念的理解：

1. 雙指標（快慢指標）機制：利用快指標（for 迴圈中的 $i$）循序走訪串列，慢指標（變數 count）記錄不重複元素的個數，同時標記下一個新相異元素應覆寫的索引位置。
2. 條件覆寫（In-place Modification）：若快指標數值大於當前記錄的最大相異值（$i > current$），則將該值寫入慢指標位置 list[count]，並推進慢指標（$count \leftarrow count + 1$）。
3. 區間迭代與尾端刪除：range(count, last) 產生半開區間 $[count, last)$ 的整數序列，透過 list.pop 逐次自串列末端移除元素，將多餘的舊元素截除。
4. Python print 函式之預設引數：print 傳入多個引數時，預設會以單一空白字元（sep=' '）作為引數間的分隔符號。

---

解題方法

解題切入點採用程式分段追蹤法，將程式碼拆解為三個主要階段進行推導：

階段一：變數初始化

• 初始串列：list = [2, 2, 3, 7, 7, 7, 9, 9, 10, 10]，長度為 10。
• count = 1：代表已保留第 0 個元素，去重複後的有效長度從 1 開始計數。
• current = list[0] = 2：記錄目前最新的相異值基準。

階段二：for 迴圈走訪與覆寫

迴圈依序取出 list 中的元素 $i$，當 $i > current$ 時觸發覆寫與累加：

迭代次數	元素 $i$	判斷式 $i > current$	執行動作	count	current	list 當前內容
1	2	$2 > 2$（False）	不執行	1	2	[2, 2, 3, 7, 7, 7, 9, 9, 10, 10]
2	2	$2 > 2$（False）	不執行	1	2	[2, 2, 3, 7, 7, 7, 9, 9, 10, 10]
3	3	$3 > 2$（True）	list[1] = 3	2	3	[2, 3, 3, 7, 7, 7, 9, 9, 10, 10]
4	7	$7 > 3$（True）	list[2] = 7	3	7	[2, 3, 7, 7, 7, 7, 9, 9, 10, 10]
5	7	$7 > 7$（False）	不執行	3	7	[2, 3, 7, 7, 7, 7, 9, 9, 10, 10]
6	7	$7 > 7$（False）	不執行	3	7	[2, 3, 7, 7, 7, 7, 9, 9, 10, 10]
7	9	$9 > 7$（True）	list[3] = 9	4	9	[2, 3, 7, 9, 7, 7, 9, 9, 10, 10]
8	9	$9 > 9$（False）	不執行	4	9	[2, 3, 7, 9, 7, 7, 9, 9, 10, 10]
9	10	$10 > 9$（True）	list[4] = 10	5	10	[2, 3, 7, 9, 10, 7, 9, 9, 10, 10]

核心觀念

本題為典型的「物件導向程式設計（OOP）」實作題，重點測驗 Java 類別的封裝、物件狀態操作與數學模型對應能力：

1. 物件封裝與成員存取權限：類別內部的 private 成員變數（real 與 imaginary），在同一個類別的不同物件實例（Instance）之間具備存取權限。例如在 add(Complex right) 或 division(Complex right) 中，可直接存取 right.real。
2. toString 覆寫與輸出機制：Java 中任何物件傳入 System.out.printf("%s") 或 System.out.print 時，皆會自動呼叫該物件的 toString 方法。
3. 複數除法與倒數的代數定義：

• 複數除法： $(a+bi)/(c+di) = \frac{ac+bd}{c^2+d^2} + \frac{bc-ad}{c^2+d^2}i$
• 倒數定義：若 $y' * y = 1$，則 $y' = 1 / y = (1.0 + 0.0i) / y$。

4. 字串格式化與邊界條件判斷：輸出特殊代數格式時，需根據實部與虛部的數值狀態（$0.0$、$1.0$、正負號）進行條件分支處理。

---

解題方法與逐步推導

（一）列印結果分析

1. 程式建立兩個複數物件：

• x 的實部為 1.0、虛部為 1.0。
• y 的實部為 2.0、虛部為 2.0。

2. Complex 類別覆寫了 toString，其格式化字串為 String.format("(%.1f, %.1f)", real, imaginary)，保留小數點後一位。
3. 第一行輸出：System.out.printf("x = %s%n", x.toString);

• 明確呼叫 x.toString，回傳 "(1.0, 1.0)"。
• 印出：x = (1.0, 1.0) 並換行。

4. 第二行輸出：System.out.printf("y = %s%n", y);

• %s 轉換符會自動呼叫 y.toString，回傳 "(2.0, 2.0)"。
• 印出：y = (2.0, 2.0) 並換行。

（二）利用 add 列印相加結果

1. x.add(y) 會以 x 為主體，將 y 作為引數傳入，計算 $(1+2) + (1+2)i$，回傳一個新的 Complex(3.0, 3.0) 物件。
2. 題目要求印出 x + y = (3.0, 3.0)，配合 ComplexTest.java 原有的 printf 風格，直接將 x.add(y) 置入輸出敘述中：

System.out.printf("x + y = %s%n", x.add(y));

（亦可使用 System.out.println("x + y = " + x.add(y));）

（三）撰寫 division(Complex right)

1. 方法簽章：依題意必須為 public Complex division(Complex right)。
2. 數學公式與程式變數對應：

• 被除數（this）：$a = \text{real}$，$b = \text{imaginary}$。
• 除數（right）：$c = \text{right.real}$，$d = \text{right.imaginary}$。
• 分母：$\text{denominator} = c^2 + d^2 = \text{right.real} \times \text{right.real} + \text{right.imaginary} \times \text{right.imaginary}$。
• 新實部：$\frac{ac+bd}{c^2+d^2} = \frac{\text{real} \times \text{right.real} + \text{imaginary} \times \text{right.imaginary}}{\text{denominator}}$。
• 新虛部：$\frac{bc-ad}{c^2+d^2} = \frac{\text{imaginary} \times \text{right.real} - \text{real} \times \text{right.imaginary}}{\text{denominator}}$。

3. 回傳值：透過建構子回傳包含計算後之實部與虛部的新 Complex 物件。

（四）利用 division 計算 $y$ 的倒數

1. 倒數之代數轉換：

• 實數 $1$ 的複數表示為 $1 + 0i$，即 new Complex(1.0, 0.0)。
• $y$ 的倒數 $y' = 1 / y$，即以複數 $1$ 呼叫 division(y)。

2. 程式實作：

• 宣告代表 $1$ 的複數物件，或直接鏈式呼叫：new Complex(1.0, 0.0).division(y)。
• 將結果輸出為有意義之說明文字（包含計算結果）。
• 代數驗算： $y = 2 + 2i \implies y' = \frac{1}{2+2i} = \frac{2 - 2i}{2^2 + 2^2} = \frac{2 - 2i}{8} = 0.25 - 0.25i$ 經 toString 的 %.1f 格式化後輸出為 (0.3, -0.3)。