問題プレビューID: 28879830基本情報技術者試験 午前免除試験 2017年6月11日

問 7
基本情報技術者試験 午前免除試験 2017年6月11日

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

f(n,k)={1(k=0),f(n−1,k−1)+f(n−1,k)(0<k<n),1(k=n).f(n, k) = \begin{cases} 1 & (k = 0), \\ f(n-1, k-1) + f(n-1, k) & (0 < k < n), \\ 1 & (k = n). \end{cases}

解説

正解は「エ」です。

関数 ff は,k=0k = 0 又は k=nk = n のとき 1 を返し,それ以外では f(n−1,k−1)+f(n−1,k)f(n-1, k-1) + f(n-1, k) を返します。これは二項係数 (nk)\binom{n}{k} を求める漸化式(パスカルの三角形)と同じ形です。

f(4,2)f(4, 2) を順に計算します。

f(4,2)=f(3,1)+f(3,2)f(4, 2) = f(3, 1) + f(3, 2)

f(3,1)=f(2,0)+f(2,1)=1+f(2,1)f(3, 1) = f(2, 0) + f(2, 1) = 1 + f(2, 1)

f(2,1)=f(1,0)+f(1,1)=1+1=2f(2, 1) = f(1, 0) + f(1, 1) = 1 + 1 = 2

なので f(3,1)=1+2=3f(3, 1) = 1 + 2 = 3 です。また,

f(3,2)=f(2,1)+f(2,2)=2+1=3f(3, 2) = f(2, 1) + f(2, 2) = 2 + 1 = 3

したがって,

f(4,2)=3+3=6f(4, 2) = 3 + 3 = 6

となり,「エ」が正解です。

関連問題

本文が同じ・似ている問題を表示しています