基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
二つの再帰呼出し
条件を整理し、答えを選んでから解き方を確認しましょう。
G(0)は1を返し、n>0ならG(n−1)+G(n−1)を返す。メモ化しない。最初のG(2)自身も含む呼出し総数はどれか。
答え・解き方を読む
7回
図で見る
部分木を数えて根の一つを加える
図を拡大して見る ↗木の親子関係の模式図で、設問の節点数・文字をそのまま描いたものではありません。探索は設問指定の左右順と幅優先/深さ優先に従います。個数は根1と左右の部分木を足します。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
考える順序
- 1深さ0にG(2)が1回
- 2深さ1にG(1)が2回
- 3深さ2にG(0)が4回で計7回
選択肢ごとの理由
- 比較 · 3回
異なる引数の種類数でなく全呼出しを数えます。
- 比較 · 5回
G(1)が二つともさらに2回呼び出します。
- 正解 · 7回
深さ0にG(2)が1回。深さ1にG(1)が2回。深さ2にG(0)が4回で計7回。
- 比較 · 4回
4回は末端のG(0)だけの回数です。