平成26年度 秋期 基本情報技術者試験 午前 問7
テクノロジ／アルゴリズム次の関数 f(n, k) がある。f(4, 2) の値は幾らか。 f(n, k) ＝ 1 （k＝0のとき） f(n, k) ＝ f(n－1, k－1)＋f(n－1, k) （0＜k＜nのとき） f(n, k) ＝ 1 （k＝nのとき）
出典：平成26年度 秋期 基本情報技術者試験 午前 問7
- ア3
- イ4
- ウ5
- エ6
正解：エ
解説
この関数は二項係数（コンビネーション）を再帰的に定義したものです。f(4,2)＝f(3,1)＋f(3,2)，f(3,1)＝f(2,0)＋f(2,1)＝1＋2＝3，f(3,2)＝f(2,1)＋f(2,2)＝2＋1＝3となるため，f(4,2)＝3＋3＝6です。
選択肢ごとの解説
- ア誤り。再帰の一部の項を数え落とすなど，途中の足し算を誤ると得られる値です。
- イ誤り。f(3,1)やf(3,2)の値を求める際に，境界条件の適用を誤ると得られる値です。
- ウ誤り。正しい二項係数の計算結果である6よりも小さく，再帰の展開が不十分な場合に生じる値です。
- エ正しい。f(4,2)はC(4,2)に相当し，再帰的に展開すると6になります。