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

核心觀念

本題考查 C 語言的：

• 遞迴函式（recursion）
• if 終止條件
• while 迴圈
• % 取餘數運算
• / 整數除法
• 十進位數字各位數總和

函式的定義如下：

int function(int n)
{
 if (n < 10)
 return n;
 ...
 return function(sum);
}

當 $n<10$ 時，直接回傳 $n$，這是遞迴的終止條件。當 $n\geq 10$ 時，先計算各位數字總和，再以總和作為新的參數呼叫自己。

---

解題方法

逐層計算 function(n) 的執行結果。

第 1 層：function(12345)

因為 $12345\geq 10$，進入 while 迴圈：

當下的 n	n % 10	sum 累加後	n /= 10 後
12345	5	5	1234
1234	4	9	123
123	3	12	12
12	2	14	1
1	1	15	0

因此：

$$\text{function}(12345)=\text{function}(15)$$

第 2 層：function(15)

同樣計算各位數字總和：

當下的 n	n % 10	sum 累加後	n /= 10 後
15	5	5	1
1	1	6	0

因此：

$$\text{function}(15)=\text{function}(6)$$

第 3 層：function(6)

因為：

核心觀念

本題考查堆疊（Stack）的後進先出（LIFO, Last In First Out）特性：

• Push：將資料放入堆疊頂端。
• Pop：只能取出目前堆疊頂端的資料。
• 後推入的資料，必須先於先推入的資料被彈出。

推入順序固定為：

$123 \rightarrow 234 \rightarrow 345 \rightarrow 456 \rightarrow 567$

要求的彈出順序為：

$345 \rightarrow 567 \rightarrow 456 \rightarrow 234 \rightarrow 123$

解題方法

依照指定的 Pop 順序逐一處理。每次要 Pop 某項資料時：

1. 若該資料已在堆疊頂端，直接 Pop。
2. 若尚未推入，依照固定 Push 順序繼續推入，直到該資料位於堆疊頂端。
3. 若目標資料下方已有資料，則表示無法直接取出，順序即不可能。

Push 與 Pop 步驟

堆疊底端以左側表示，頂端以右側表示。

步驟	操作	堆疊內容
1	Push 123	123
2	Push 234	123、234
3	Push 345	123、234、345
4	Pop 345	123、234
5	Push 456	123、234、456
6	Push 567	123、234、456、567
7	Pop 567	123、234、456
8	Pop 456	123、234
9	Pop 234	123
10	Pop 123	空

因此實際操作序列為：

$$\operatorname{Push}(123)$$

核心觀念

本題考查：

• C 語言函式遞迴（recursion）。
• 餘數運算子 %。
• 歐幾里得算法（Euclidean algorithm）。
• 最大公因數（Greatest Common Divisor, GCD）的計算。

函式如下：

int f(int a, int b) {
 if (a % b == 0) return b;
 return f(b, a % b);
}

其核心數學性質為：

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

當 $a\bmod b=0$ 時，表示 $b$ 可以整除 $a$，此時 $b$ 即為兩數的最大公因數，因此函式回傳 $b$。

---

解題方法

依照函式執行順序，逐步計算餘數，直到餘數為 $0$。

1. 計算 f(21, 9)

第一次呼叫：

$$21\bmod 9=3$$

因為結果不是 $0$，所以遞迴呼叫：

f(9, 3)

接著：

$$9\bmod 3=0$$

符合 if (a % b == 0)，回傳 $b=3$。

因此：

$$f(21,9)=3$$

---

2. 計算 f(6, 44)

第一次呼叫：

$$6\bmod 44=6$$

結果不是 $0$，因此呼叫：

f(44, 6)

接著：

$$44\bmod 6=2$$

因此呼叫：

f(6, 2)

再計算：

$$6\bmod 2=0$$

符合終止條件，回傳 $b=2$。

因此：

$$f(6,44)=2$$

這也符合：

$$\gcd(6,44)=2$$

---

程式輸出

main 函式先執行 f(21, 9)，再執行 f(6, 44)，所以輸出為：

核心觀念

本題考查：

• C 語言函式呼叫與「傳值呼叫」。
• for 迴圈的執行次數。
• 關係運算子：>、<、<=、>=
• 邏輯運算子：&&、||、!
• 邏輯運算式的逐次判斷。
• 變數在迴圈中的累加與累減。

題目程式中的 i 未宣告，嚴格依 C 語言規則會造成編譯錯誤。因此以下依題意採合理假設，視為函式中已有：

int i;

解題方法

函式呼叫為：

function(x, y);

其中：

x = 5;
y = 10;

由於函式參數採傳值方式，函式內的初始值為：

a = 5
b = 10

函式一開始先執行：

printf("a=%d,b=%d\n", a, b);

因此第一行輸出為：

a=5,b=10

接著判斷迴圈條件：

!(a > 10 && b < 10) && (a <= 10 || b >= 10)

令：

• $P = (a > 10 \ \&\& \ b < 10)$
• $Q = (a <= 10 \ || \ b >= 10)$

整體條件為：

$$\neg P \land Q$$

條件成立時，執行：

a = a + 1;
b = b - 1;

也就是每次令：

$$a \leftarrow a+1,\qquad b \leftarrow b-1$$

第 0 次迴圈

目前：

a=5,b=10

判斷：

a > 10 && b < 10
5 > 10 && 10 < 10
false && false
false

因此：

!(...) = true

再判斷：

a <= 10 || b >= 10
5 <= 10 || 10 >= 10
true || true
true

整體條件為：

true && true
true

更新後：

a=6,b=9

第 1 至第 5 次迴圈

每次迴圈皆使 $a$ 增加 $1$、$b$ 減少 $1$：

迴圈次數	更新前 $(a,b)$	更新後 $(a,b)$	條件
1	$(6,9)$	$(7,8)$	成立
2	$(7,8)$	$(8,7)$	成立
3	$(8,7)$	$(9,6)$	成立
4	$(9,6)$	$(10,5)$	成立
5	$(10,5)$	$(11,4)$	成立

以第 5 次為例：