平成26年度 秋期 午前 問7
アルゴリズム
関数に関する問題
次の関数 f(n, k) がある。f(4, 2) の値は幾らか。
〔関数の定義〕字に書き起こしたもの（原典は大きな中括弧で3つの場合を並べている）
┌ 1 (k ＝ 0)
f(n, k) ＝ ┤ f(n−1, k−1) ＋ f(n−1, k) (0 ＜ k ＜ n)
└ 1 (k ＝ n)- ア3
- イ4
- ウ5
- エ6
答えと解説を見る
✓ これが正解エ6
解説
端は 1、内側は上の二つの和で 6 になります。
この関数は、二つ目の引数が 0 のときと二つの引数が等しいときに 1 と決まり、それ以外では自分より一つ小さい二つの呼び出しの和になります。判定の軸は、1 と決まるところまで確実に展開できるかという一点です。求める値は、まず f(3,1) と f(3,2) の和に分かれます。f(3,1) は f(2,0) と f(2,1) の和で、前者は 1、後者は f(1,0) と f(1,1) がどちらも 1 なので 2 となり、合わせて 3 です。f(3,2) は f(2,1) と f(2,2) の和で、2 と 1 なので同じく 3 です。したがって求める値は 3 と 3 を足した 6 になります。段ごとに数を並べていくと、両端が 1 で内側が上の段の二つの和になる三角形ができ、四段目の真ん中に同じ数が現れます。この形は、いくつかの中から選ぶ場合の数を並べたものと同じ作りです。
ほかの選択肢はなぜ違うのか
- ア3：展開を一段手前で止めた形です。この数は f(3,1) と f(3,2) がそれぞれ取る値で、その二つを足す最後の一手が残っています。
- イ4：段は合っていますが位置が一つずれた形です。四段目に並ぶ数は端から 1、4、6、4、1 なので、この数は真ん中の隣にあたります。
- ウ5：四段目までに現れる数は 1、2、3、4、6 だけで、この数はどの段のどの位置にも現れません。与えられた決まりからは導けない値です。
出典：平成26年度 秋期 基本情報技術者試験 午前 問7（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）