アルゴリズム(全101問中42問目)

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

　g(x) = if x<2 then 1
　　　　　　　else g(x－1)＋g(x－2)

出典：平成24年秋期　問 7

  • 3
  • 4
  • 5
  • 7
正解　イ問題へ
分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム
広告
解説
再帰関数を1つずつ展開していったものが次の図です。g(1)とg(0)は整数1を返すので、これらの再帰部分は省略してあります。
07.png
必要となる加算の回数は4回です。
広告

次の問題前の問題

この問題の出題歴

▲
Pagetop