基本情報技術者試験 2014年度 = 平成26年度・秋期 午前 問7

 次の関数f (n , k )がある。f (4, 2)の値は幾らか。

┌ 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

解答



解説

 関数f は再帰的な関数です。f (4, 2)の値は以下のように求められます。
  [A] f (4, 2) = f (3, 1) + f (3, 2)
 ここで、
  [B] f (3, 1) = f (2, 0) + f (2, 1)
です。定義により、f (2, 0)は1ですから、f (3, 1)は1 + f (2, 1)です。
 また、
  [C] f (3, 2) = f (2, 1) + f (2, 2)
です。定義により、f (2, 2)は1ですから、f (3, 2)はf (2, 1) + 1です。
 さて、両方に含まれるf (2, 1)は、以下のように求められます。
  [D] f (2, 1) = f (1, 0) + f (1, 1)
 ここで、f (1, 0)とf (1, 1)の両方は1ですから、f (2, 1)は2です。

 したがって、次のようになります。
  [B] f (3, 1) = f (2, 0) + f (2, 1) = 1 + 2 = 3
  [C] f (3, 2) = f (2, 1) + f (2, 2) = 2 + 1 = 3
  [A] f (4, 2) = f (3, 1) + f (3, 2) = 3 + 3 = 6
 よって、正解はです。


BohYoh.comトップページへ