普考申論題
114年
[資訊處理] 程式設計概要
第 一 題
📖 題組：
撰寫一個 Java 程式，使用遞迴計算給定正整數 n 的「卡塔蘭數」（Catalan Number）C(n)，其中 C(n)定義為：C(0) = 1，C(n) = Σ(C(i) * C(n-1-i)) for i from 0 to n-1，使用者輸入 n（n 為非負整數且不超過 15）。輸出 C(n)，並使用 long 型別。執行範例如下：例如 n 輸入 4，輸出 C(4) = 14。
4
C(4) = 14
import java.util.InputMismatchException;
import java.util.Scanner;
public class JP2 {
public static long catalan(int n) {
(A)
return sum;
}
public static void main(String[] args) {
Scanner scanner = (B)
int n;
try {
n = scanner.nextInt();
(C){
System.out.println("輸入不合法!");
scanner.close();
return;
}
} catch (InputMismatchException e) {
System.out.println("輸入不合法!");
scanner.close();
return;
}
(D)
System.out.println((E) + result);
scanner.close();
}
}
撰寫一個 Java 程式，使用遞迴計算給定正整數 n 的「卡塔蘭數」（Catalan Number）C(n)，其中 C(n)定義為：C(0) = 1，C(n) = Σ(C(i) * C(n-1-i)) for i from 0 to n-1，使用者輸入 n（n 為非負整數且不超過 15）。輸出 C(n)，並使用 long 型別。執行範例如下：例如 n 輸入 4，輸出 C(4) = 14。
4
C(4) = 14
import java.util.InputMismatchException;
import java.util.Scanner;
public class JP2 {
public static long catalan(int n) {
(A)
return sum;
}
public static void main(String[] args) {
Scanner scanner = (B)
int n;
try {
n = scanner.nextInt();
(C){
System.out.println("輸入不合法!");
scanner.close();
return;
}
} catch (InputMismatchException e) {
System.out.println("輸入不合法!");
scanner.close();
return;
}
(D)
System.out.println((E) + result);
scanner.close();
}
}
📝 此題為申論題，共 5 小題
小題 (一)
完成(A)程式碼（12 分）
思路引導 VIP
看到遞迴計算題，應優先確立「終止條件（Base case）」與「遞迴關係（Recursive case）」。本題需注意下方已有 return sum;，因此在填空處必須宣告 long sum = 0;，並利用 for 迴圈將題目給定的公式轉換為程式碼。
小題 (二)
完成(B)程式碼（3 分）
思路引導 VIP
觀察變數宣告型別為 Scanner，且後續程式碼使用 scanner.nextInt() 來接收使用者輸入。在 Java 中，要讀取控制台的標準輸入（鍵盤輸入），必須實例化 Scanner 物件並傳入 System.in 作為輸入串流。
小題 (三)
完成(C)程式碼（3 分）
思路引導 VIP
看到此題，首先回顧題目對變數 n 的限制條件：「非負整數且不超過 15」。接著觀察 (C) 後的程式區塊為印出「輸入不合法!」並結束程式，可知此處需要一個 if 條件判斷式，用來捕捉小於 0 或大於 15 的不合法輸入值。
小題 (四)
完成(D)程式碼（4 分）
思路引導 VIP
觀察上下文，(D) 的上方剛完成變數 n 的讀取與合法性驗證，下方緊接著要印出包含 result 變數的計算結果。因此 (D) 處需宣告與 catalan 函式回傳值相同型態 (long) 的變數 result，並呼叫 catalan(n) 來計算答案。
小題 (五)
完成(E)程式碼（3 分）
思路引導 VIP
觀察執行範例的輸出格式為「C(n) = 計算結果」，並對照程式碼 System.out.println((E) + result);。由於 result 儲存最終計算數值，可知 (E) 需利用字串串接變數 n 來產生前半段的提示字串。
卡塔蘭數與遞迴實作
💡 掌握遞迴公式轉程式碼、例外處理與基礎輸入輸出規範。
🔗 卡塔蘭數程式執行邏輯
- 1 輸入驗證 — 透過 Scanner 與 try-catch 排除非數字或範圍外輸入
- 2 遞迴計算 — 依 C(n) = Σ C(i)*C(n-1-i) 邏輯進行自我呼叫與累計
- 3 格式化輸出 — 將計算結果 long result 依範例要求印出至主機板
↓
↓
🔄 延伸學習：延伸學習：可思考如何使用 Memoization (記憶化) 優化遞迴效率
