フィボナッチ数列

フィボナッチ数列は、$F_0=0$、$F_1=1$とし、$n\ge2$で$F_n=F_{n-1}+F_{n-2}$と定める数列です。0、1、1、2、3、5、8、…と続きますが、$F_1=1$、$F_2=1$から始める添字流儀もあります。

■ 試験で押さえるポイント

• 各項は直前二項の和なので、値だけでなく初期条件と添字を確認します。F0始まりなら$F_{10}=55$です。

• 定義どおりの単純な再帰実装は同じ部分問題を何度も計算し、呼出し数が指数的に増えます。メモ化又は反復DPなら時間$O(n)$、追加領域$O(1)$でも計算できます。

• 行列$\begin{bmatrix}1&1\\1&0\end{bmatrix}$の累乗や高速ダブリングを使うと$O(\log n)$段階で計算でき、大きなnでは多倍長整数や剰余計算が必要です。

• 連続項の比$F_{n+1}/F_n$はnが大きいと黄金比$(1+\sqrt5)/2$へ近づきます。閉形式は丸め誤差に注意します。

■ 選択肢での判断ポイント

漸化式・初期値・添字、単純再帰とDPの計算量差が頻出です。同じ結果でもアルゴリズム効率が大きく異なります。

例: $F_0=0$、$F_1=1$から、$F_2=1$、$F_3=2$、$F_4=3$、$F_5=5$、$F_6=8$と、前二項を一度ずつ足して求めます。