基本情報技術者試験 無料問題 9 / 10 ・ 分野4: 科目B アルゴリズムとプログラミング分野
次の手続 main を呼び出したとき、出力される値を出力された順にコンマで区切って並べたものはどれか。 〔プログラム〕 大域: 整数型: cnt ← 0 ○整数型: fib(整数型: n) cnt ← cnt + 1 if (n ≦ 2) return 1 endif return fib(n - 1) + fib(n - 2) ○main() 整数型: v ← fib(6) v を出力する cnt を出力する
- 8, 15
- 8, 7
- 8, 6
- 13, 25
正解と解説を見る
正解: A
正解の理由
fib は、呼ばれるたびに大域変数 cnt を 1 増やし、n ≦ 2 なら 1 を返し、そうでなければ fib(n - 1) + fib(n - 2) を返す。値は fib(3) = 2、fib(4) = 3、fib(5) = 5、fib(6) = 8。呼出し回数を C(n) とすると C(1) = C(2) = 1、C(n) = 1 + C(n - 1) + C(n - 2) なので、C(3) = 3、C(4) = 5、C(5) = 9、C(6) = 15。出力は 8, 15 である。
違う選択肢
「8, 6」… n ごとに1回ずつしか呼ばれないと考えている。この fib は同じ n を何度も計算し直す（例えば fib(3) は3回呼ばれる）。
「8, 7」… 値を返すだけの n ≦ 2 の呼出しを数えていない。cnt は if より前で増やすので、すべての呼出しが数えられる。
「13, 25」… 終了条件を n ≦ 1 と読んだ結果で、値が 13、呼出しが 25 回になる。
押さえどころ
このような二重の再帰は、同じ引数の計算を繰り返すため、呼出し回数が n に対して指数的に増える。計算量を見積もるときは、呼出し回数の漸化式を立てて数える。