アルゴリズム (全82問中23問目)

No.23

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

 g(x) = if x<2 then 1
       else g(x−1)+g(x−2)
  • [この問題の出題歴]
  • ソフトウェア開発技術者 H20秋期 問13

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

再帰関数を1つずつ展開していったものが次の図です。g(1)とg(0)は整数1を返すので、これらの再帰部分は省略してあります。
07.gif/image-size:243×139
必要となる加算の回数は4回です。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop