基本情報技術者試験
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
よって、正解は
エ
です。
