次の関数 g(x)g(x)g(x) の定義に従って g(4)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(x)={1g(x−1)+g(x−2)(x<2 のとき)(x≥2 のとき)
3
4
5
7
正解は「イ」です。
定義に従って g(4)g(4)g(4) を展開すると次のようになります。
メモ化を行わない場合,g(2)g(2)g(2) は g(3)g(3)g(3) の計算時と g(4)g(4)g(4) の計算時の 2 回呼び出されます。加算が発生するのは,g(3)g(3)g(3) 内の g(2)g(2)g(2),g(3)g(3)g(3) 自身,g(4)g(4)g(4) 内の g(2)g(2)g(2),g(4)g(4)g(4) 自身の 4 か所であり,必要な加算の回数は 4 回です。
よって,正解は「イ」です。
本文が同じ・似ている問題を表示しています