地特三等申論題
111年
[資訊處理] 程式設計
第 二 題
📖 題組：
一、有關 C 程式設計，回答下列問題：
一、有關 C 程式設計，回答下列問題：
📝 此題為申論題，共 2 小題
小題 (二)
下列程式執行結果為何？（10 分）
#include
#include
bool func2(int A[], int x, int y){
if (x > y) return false;
else{
int m = (x + y) / 2;
printf("%3d %3d %3d\n", x, m, y);
if (A[m] == m) return true;
else if (A[m] > m) return func2(A, x, m - 1);
else return func2(A, m + 1, y);
}
}
int main(void) {
int a[] = { 35, 60, 45, 7, 10, 22, 2, 50, 14, 3, 66};
printf("%3d", func2(a, 1, 10));
}
#include
#include
bool func2(int A[], int x, int y){
if (x > y) return false;
else{
int m = (x + y) / 2;
printf("%3d %3d %3d\n", x, m, y);
if (A[m] == m) return true;
else if (A[m] > m) return func2(A, x, m - 1);
else return func2(A, m + 1, y);
}
}
int main(void) {
int a[] = { 35, 60, 45, 7, 10, 22, 2, 50, 14, 3, 66};
printf("%3d", func2(a, 1, 10));
}
思路引導 VIP
這是一題典型的遞迴追蹤與二元搜尋（Binary Search）變體題。解題時應先寫出陣列各索引對應的值，然後依序記錄每次遞迴呼叫時 x, y, m 參數的變化與輸出；最後要特別注意 C 語言中 bool 型態回傳 false 時，以 %3d 格式列印會輸出 0。
小題 (一)
下列程式執行結果為何？（13 分）
#include
int func1(int a, int b){
printf("%3d %3d\n", a, b);
if (b == 0) return a;
else if (a % 2 && b % 2)
return func1((a + b) / 2, (a - b) / 2);
else if (a % 2 && !(b % 2))
return func1(a, b / 2);
else if (!(a % 2) && b % 2)
return func1(a / 2, b);
else
return 2 * func1(a / 2, b / 2);
}
int main(void) {
int x = 19, y = 2;
printf("%3d", func1(x, y));
}
#include
int func1(int a, int b){
printf("%3d %3d\n", a, b);
if (b == 0) return a;
else if (a % 2 && b % 2)
return func1((a + b) / 2, (a - b) / 2);
else if (a % 2 && !(b % 2))
return func1(a, b / 2);
else if (!(a % 2) && b % 2)
return func1(a / 2, b);
else
return 2 * func1(a / 2, b / 2);
}
int main(void) {
int x = 19, y = 2;
printf("%3d", func1(x, y));
}
思路引導 VIP
本題考驗 C 語言遞迴函式的追蹤能力以及算術運算與邏輯判斷的細節（特別是非零值即為真的特性）。解題時應將每次呼叫的 a 和 b 帶入，並依序寫下 printf 的格式化輸出（留意 %3d 佔用的空白數），同時特別注意當計算到負數取餘數「-1 % 2 = -1」時，在條件判斷中應視為真（True）。