修了試験 2011-12-18実施分 基本情報技術者試験 問7

解説

正解は4です。 f(n, k)は、kが0またはnのとき1を返し、それ以外はf(n-1, k-1)＋f(n-1, k)を返す再帰関数です。 これはパスカルの三角形を作る規則と同じです。 したがって、f(n, k)はn個からk個を選ぶ組合せの数になります。 【計算】 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(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つの和なので、3ではありません。 2：× 4はf(4, 1)やf(4, 3)の値です。 f(4, 2)の値ではありません。 3：× 5になる計算経路はありません。 正しく展開すると6になります。 4：○ 展開した結果の6と一致します。 4個から2個を選ぶ組合せの数4×3÷2＝6とも一致します。 【ポイント】 再帰関数の問題は、終了条件にたどり着くまで1段ずつ展開して計算します。 漸化式がパスカルの三角形と同じだと気づけば、組合せの公式で検算できます。