地特三等申論題
105年
[資訊處理] 資料結構
第 一 題
📖 題組：
二項式係數（Binomial Coefficient）的計算公式如下： ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − +⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − = − =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ 1 1 1 !( )! ! m n m n m n m n m n ⎩ ⎨ ⎧ − + − − = = = Bino ( 1, ) Bino ( 1, 1); otherwise 1, if 0 or Bino ( , ) n m n m m m n n m
二項式係數（Binomial Coefficient）的計算公式如下： ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − +⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − = − =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ 1 1 1 !( )! ! m n m n m n m n m n ⎩ ⎨ ⎧ − + − − = = = Bino ( 1, ) Bino ( 1, 1); otherwise 1, if 0 or Bino ( , ) n m n m m m n n m
📝 此題為申論題，共 3 小題
小題 (一)
求 Bino(5,3)的值？（5 分）
思路引導 VIP
看到二項式係數（Binomial Coefficient）問題，首先檢視題目給定的公式。本題同時提供了「階乘公式」與「遞迴關係式」，解題時可擇一詳細計算，並以另一方法進行驗算。在資料結構考科中，建議以展示「遞迴展開」的過程為主，展現對演算法執行步驟的理解，能確保獲取完整分數。
小題 (二)
求 Bino(5,3)時，共呼叫 Bino 此函數多少次？（5 分）
思路引導 VIP
看到這類遞迴呼叫次數的計算題，有兩種解法：一是「建立狀態轉移關係式」由下而上（Bottom-up）逐步推導；二是利用「嚴格二元樹性質」速解，因為每一次遞迴分支必定產生2個子呼叫，且基本條件的回傳值為1，故總呼叫次數必為「2 × 最終組合數值 - 1」。
小題 (三)
當 n, m∈ N且 n≥m≥0 求 Bino(n, m)時，共呼叫 Bino 函數 T(n, m)次，求 T(n, m)=？（10 分）
思路引導 VIP
遇到遞迴函數呼叫次數的計算，首先根據程式邏輯寫出次數的遞迴關係式 $T(n, m)$ 及邊界條件。接著可利用平移（加上常數）或假設通解的形式，將其化簡為已知的標準組合數遞迴式（巴斯卡定理）以求得封閉解。