プログラミングの基礎(擬似言語のトレース)
次の関数 fib を fib(10) として呼び出したときの戻り値はどれか。
○整数型: fib(整数型: n)
整数型: a ← 0, b ← 1, t
for (i を 1 から n まで 1 ずつ増やす)
t ← a + b
a ← b
b ← t
endfor
return a- A34
- B55
- C89
答えと解説を見る
正解：B. 55
繰返しのたびに (a, b) は、隣り合うフィボナッチ数の組を1つずつ進めます。(0, 1) → (1, 1) → (1, 2) → (2, 3) → (3, 5) → (5, 8) → (8, 13) → (13, 21) → (21, 34) → (34, 55) → (55, 89) と10回進むので、a = 55 を返します。a は i 回目の繰返しの後に i 番目のフィボナッチ数になります。素朴な再帰で書くと同じ値を何度も計算しますが、この書き方では n 回の繰返しで済みます。
- A. 繰返しが1回少ない(終値を n − 1 にした)場合の値です。
- B. 正しい。10回進めた後の a = 55 です。
- C. b を返した場合の値で、11番目のフィボナッチ数です。