平成24年 秋期 応用情報技術者 午前 問7

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

 g (x ) = if x < 2 then 1
            else g (x - 1) + g (x - 2)

 ア  3
 イ  4
 ウ  5
 エ  7


答え イ


解説
関数g (x )の定義から必要な加算の回数を数える。
 g (4) = g (3) + g (2) = (g (2) + g (1)) + (g (1) + g (0))
 = ((g (1) + g (0)) + g (1)) + (g (1) + g (0))
 = g (1) + g (0) + g (1) + g (1) + g (0)
 = 5
4回(イ)である。

参考に関数g (x )の加算回数を表にまとめる。

引数(x ) 加算回数 処理内容
0 0 g (0) = 1
1 0 g (1) = 1
2 1 g (2) = g (1) + g (0) = 2
3 2 g (3) = g (2) + g (1)
= (g (1) + g (0)) + g (1) = 3
4 4 g (4) = g (3) + g (2)
= (g (2) + g (1)) + (g (1) + g (0))
= ((g (1) + g (0)) + g (1)) + (g (1) + g (0)) = 5
5 7 g (5) = g (4) + g (3) = 5 + 3 = 8
6 12 g (6) = g (5) + g (4) = 8 + 5 = 13
7 20 g (7) = g (6) + g (5) = 13 + 8 = 21
これからg (x )(x ≥ 2)の加算回数は「g (x - 2)の加算回数 + g (x - 1)の加算回数 + 1」である。


キーワード
・再帰的処理

キーワードの解説

戻る 一覧へ 次へ