アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 200912 実施分 問8
次の関数 f(n, k)がある。f(4, 2)の値は幾らか。
f(n, k) =
1 (k = 0),
f(n−1, k−1) + f(n−1, k) (0 < k < n),
1 (k = n).
- ア 3
- イ 4
- ウ 5
- エ 6
出典：基本情報技術者試験 科目A免除 修了試験 200912 実施分 問8
答えと解説を見る
正解：エ
覚える知識
再帰関数のトレース計算
再帰的に定義された関数は、基底条件に至るまで展開して値を求める。
この問題で必要なこと
f(4,2)=f(3,1)+f(3,2)。f(3,1)=3、f(3,2)=3なので6となる。これは組合せ4C2に一致する。
ひっかけ
展開の途中でf(n−1,k)の値を取り違えやすい。
この知識の出題：本試験系 8 回・免除試験 11 回（公開問題での観測値）