修了試験 2017-06-11実施分 基本情報技術者試験 問7

解説

正解は4です。 再帰的に定義された関数の値を、定義に従って小さい引数まで展開して求める問題です。 k＝0またはk＝nのときは1、それ以外は二つの関数値の和になります。 【計算】 f(4, 2)＝f(3, 1)＋f(3, 2) です。 f(3, 1)＝f(2, 0)＋f(2, 1) です。 f(2, 1)＝f(1, 0)＋f(1, 1)＝1＋1＝2 です。 f(2, 0)＝1 なので、f(3, 1)＝1＋2＝3 です。 f(3, 2)＝f(2, 1)＋f(2, 2)＝2＋1＝3 です。 よって、f(4, 2)＝3＋3＝6 です。 【選択肢別解説】 1：× 3はf(3, 1)やf(3, 2)の値であり、f(4, 2)はその二つの和になります。 2：× 4はf(4, 1)やf(4, 3)の値に当たり、f(4, 2)ではありません。 3：× 5になる展開の経路はなく、計算の途中で値を数え落とした場合の誤りです。 4：○ 展開を最後までたどると、f(4, 2)＝6 になります。 【ポイント】 この関数は二項係数C(n, k)（n個からk個を選ぶ組合せの数）と同じ定義で、パスカルの三角形の作り方そのものです。 C(4, 2)＝4×3÷2＝6 と求めることもできます。