問題プレビューID: 517a6341応用情報技術者試験 2012年(平成24年度)秋期 午前

問 7
応用情報技術者試験 2012年(平成24年度)秋期 午前

次の関数 g(x)g(x) の定義に従って g(4)g(4) を再帰的に求めるとき,必要な加算の回数は幾らか。

g(x)={1(x<2 のとき)g(x−1)+g(x−2)(x≥2 のとき)g(x) = \begin{cases} 1 & (x < 2 \text{ のとき}) \\ g(x-1) + g(x-2) & (x \ge 2 \text{ のとき}) \end{cases}

解説

正解は「イ」です。

定義に従って g(4)g(4) を展開すると次のようになります。

  • g(4)=g(3)+g(2)g(4) = g(3) + g(2)
  • g(3)=g(2)+g(1)g(3) = g(2) + g(1)
  • g(2)=g(1)+g(0)g(2) = g(1) + g(0)
  • g(1)=1g(1) = 1,g(0)=1g(0) = 1(x<2x < 2 のため加算は行わない)

メモ化を行わない場合,g(2)g(2) は g(3)g(3) の計算時と g(4)g(4) の計算時の 2 回呼び出されます。加算が発生するのは,g(3)g(3) 内の g(2)g(2),g(3)g(3) 自身,g(4)g(4) 内の g(2)g(2),g(4)g(4) 自身の 4 か所であり,必要な加算の回数は 4 回です。

よって,正解は「イ」です。

関連問題

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