平成24年度 秋期 応用情報技術者試験 午前 問7
テクノロジ／アルゴリズム次の関数 g(x) の定義に従って g(4) を再帰的に求めるとき，必要な加算の回数は幾らか。 g(x) ＝ if x＜2 then 1 else g(x−1)＋g(x−2)
出典：平成24年度 秋期 応用情報技術者試験 午前 問7
- ア3
- イ4
- ウ5
- エ7
正解：イ
解説
g(x)＝g(x−1)＋g(x−2)（x≥2）という再帰定義に基づき，加算回数をA(x)とするとA(x)＝A(x−1)＋A(x−2)＋1（A(0)＝A(1)＝0）となります。これを計算するとA(2)＝1，A(3)＝2，A(4)＝A(3)＋A(2)＋1＝2＋1＋1＝4となり，g(4)を求めるのに必要な加算は4回です。
選択肢ごとの解説
- ア誤り。A(3)までの加算回数(2回)や途中経過を最終回数と取り違えた場合の値です。
- イ正しい。A(4)＝A(3)＋A(2)＋1＝2＋1＋1＝4回の加算が必要です。
- ウ誤り。加算回数を1回多く数えた場合などに生じる値で，正しい計算過程とは一致しません。
- エ誤り。加算に加えて減算の回数まで合算するなど，数え方を誤った場合の値です。