基本情報技術者試験「数列」の問題
次の手続 fib は、フィボナッチ数列の第 n 項を反復で求める。数列は第 0 項 = 0、第 1 項 = 1、第 k 項 = 第 (k−1) 項 + 第 (k−2) 項 で定義される。fib(11) を実行したとき、戻り値（第 11 項の値）はどれか。便宜上「番目」を単位として付す。
○整数型: fib(整数型: n)
整数型: a ← 0
整数型: b ← 1
整数型: t, k
for (k を 1 から n まで 1 ずつ増やす)
t ← a + b
a ← b
b ← t
endfor
return aア89 番目
イ144 番目
ウ55 番目
エ8 番目
正解
ア．89 番目
a を直前項、b を現在項として n 回更新すると、a は第 n 項を表す。第 11 項は 0,1,1,2,3,5,8,13,21,34,55,89 の 89 であるため アが正しい。
?選択肢ごとの解説
ア ○a を直前項、b を現在項として n 回更新すると、a は第 n 項を表す。第 11 項は 0,1,1,2,3,5,8,13,21,34,55,89 の 89 であるため アが正しい。
イ ×第 12 項 144 を答えた、ループを 1 回多く回した、または return b と取り違えた off-by-one の誤りである。
ウ ×第 10 項 55 を答えた、ループを 1 回少なく回した off-by-one の誤りである。
エ ×数列の前半の項 8（第 6 項）で止めた、ループ回数を大きく取り違えた誤りである。
✎くわしく
反復版フィボナッチでは『何回更新すれば第何項になるか』『最後に返すのが a か b か』の対応が肝心である。1 回の数え違いで隣の項にずれる典型的な off-by-one である。
✓本番での押さえどころ
試験のコツ
小さい n（n=1,2,3）で a, b の値を表にして、return a が第 n 項になることを確かめる。
覚え方
『a は遅れて追う、最後は a を返す』と更新順を覚える。
よくある誤り
ループ回数と項番号の対応を間違え、隣接項（55 や 144）を選ぶミスが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-b-algo-0021