109 高普考普通考試 資訊處理 程式設計概要 考古題詳解
第 一 題25 分
下面的遞迴程式執行後，印出的信息為何？作答必須解釋計算過程，只寫答案而未加解釋，只能得部分分數。
#include <stdio.h>
int new1(int p) { if (p > 90) return(new1(new1(p - 11))); return(p - 10); }
int new2(int p) { if (p < 91) return(new2(p + 11)); return(p); }
int new(int p) { return(new1(new2(p))); }
int main(int argc, char **argv) { int q;
q = 65;
printf("new(%d)= %d.\n", q, new(q));
q = 95;
printf("new(%d)= %d.\n", q, new(q));
q = 100;
printf("new(%d)= %d.\n", q, new(q));
q = 104;
printf("new(%d)= %d.\n", q, new(q));
q = 110;
printf("new(%d)= %d.\n", q, new(q));
return(0);
}
登入後即可作答並保存紀錄。
核心觀念
本題考查遞迴函式的呼叫順序，以及依照 if 條件逐層追蹤回傳值。
new2(p)：若 ，就以 再呼叫自己；直到參數至少為 才回傳。new1(p)：若 ，就先計算new1(p - 11)，再把該結果當作參數呼叫new1；若 ，則回傳 。new(p)：先計算new2(p)，再將結果傳入new1。
解題方法
先求 new2(p) 的結果。當 時，每次增加 ，直到參數達到或超過 ；因此 new2 的回傳值是第一個不小於 的數。
接著令此回傳值為 ，追蹤 new1(r)。當參數大於 時，先減 遞迴呼叫，再將內層結果作為外層的新參數；直到遇到不大於 的參數，回傳該參數減 。
計算過程
new2 的參數依序為：
因此 new2(65)=98。
new1 的呼叫順序為：
其中 ，再由 。所以 new(65)=67。
new2(95)=95，因為 。
所以 new(95)=64。
new2(100)=100。
第 二 題25 分
請參考以下 Java 程式。如果第一個輸入是 ，第二個輸入是 （負 ），最後印出來是什麼？作答必須解釋計算過程，只寫答案而未加解釋，只能得部分分數。
import java.util.Scanner;
public class JavaExample { public static void main(String args[]) { int num1, num2; Scanner scanner = new Scanner(System.in);
System.out.print("Enter first number:");
num1 = scanner.nextInt();
System.out.print("Enter second number:");
num2 = scanner.nextInt();
num1 = num1 ^ num2;
num2 = num1 ^ num2;
num1 = num1 ^ num2;
scanner.close();
System.out.println("The First number is " + num1);
System.out.println("The Second number is " + num2);
}
}
登入後即可作答並保存紀錄。
核心觀念
本題考查 Java 的位元 XOR（互斥或）運算，以及如何用 XOR 交換兩個整數的值。對每一個二進位位元，XOR 的規則是：
| 位元 A | 位元 B | |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
因此，，且 。Java 的 ^ 是整數位元 XOR 運算子。
解題方法
設輸入後 num1 = 25、num2 = -34。程式依序執行三次 XOR 指派：
num1 = num1 ^ num2
此時 num1 = 25 ^ (-34)，num2 仍為 。
num2 = num1 ^ num2
將第一步的 num1 代入：
第 三 題25 分
請問下列程式執行後，印出結果為何？作答必須解釋計算過程，只寫答案而未加解釋，只能得部分分數。
(define return #f)
(+ 1 (call/cc [lambda(cont) (set! return cont) 1] ))
(return 22)
登入後即可作答並保存紀錄。
核心觀念
本題考查 Scheme 的 續延（continuation），尤其是 call/cc（call-with-current-continuation）如何捕捉程式在呼叫當下「接下來要做什麼」。
call/cc 會將目前的續延傳給它的程序參數。本題中，cont 代表從 call/cc 返回後要繼續執行的部分。程式用 set! 將這個續延存入全域變數 return，之後便可呼叫 return，把執行流程帶回被捕捉的位置，並以呼叫時提供的值作為該位置的結果。
解題方法
先看外層加法：
(+ 1 (call/cc ...))
執行 call/cc 時，已經確定後續要做的事是：取得 call/cc 的結果，再將它與 1 相加。因此，捕捉到的 cont 可理解為：
把給定的值當作
call/cc的結果，接著計算(+ 1 給定的值)。
第一次執行 call/cc 時，傳入的程序執行：
(set! return cont)
1
第 四 題25 分
請問下列程式執行後，印出結果為何？作答必須解釋計算過程，只寫答案而未加解釋，只能得部分分數。
#include <iostream>
using namespace std;
bool sqst(int arr[], int n, int sum) { if (sum == 0) { return true; }
if (n < 0 || sum < 0) {
return false;
}
bool include = sqst(arr, n - 1, sum - arr[n]);
bool exclude = sqst(arr, n - 1, sum);
return include || exclude;
}
int main() { int arr[] = { 7, 3, 2, 5, 8 }; int sum = 14; int n = sizeof(arr) / sizeof(arr[0]);
if (sqst(arr, n - 1, sum))
cout << "Yes";
else
cout << "No";
return 0;
}
登入後即可作答並保存紀錄。
核心觀念
sqst 使用遞迴判斷陣列中是否存在一組元素，其總和等於指定的 sum，這是「子集合總和問題」（Subset Sum）。
對每個元素都有兩種選擇：
- 納入：將目前元素
arr[n]加入子集合，因此遞迴計算sum - arr[n]。 - 排除：不使用目前元素，因此保留
sum不變。
只要納入或排除的其中一條路徑能使目標總和歸零，就回傳 true。
解題方法
陣列為 {7, 3, 2, 5, 8}，目標總和是 。n 從最後一個索引開始，初始值為 。函式依序處理索引 至 的元素。
兩個終止條件是：
sum == 0：已找到總和，回傳true。n < 0 || sum < 0：元素已用完，或剩餘目標總和小於 ，回傳false。
沿著「納入」分支，依序選取 、、：