Pythonでフィボナッチ数列の最初のn項の合計を求めるプログラム

数値 n が与えられたとき、フィボナッチ数列の最初の n 項の合計を求めることを考えます。ただし、答えが非常に大きくなる場合は、結果を 10^8 + 7 で割った余りを返します。

例えば、入力が n = 8 の場合、出力は 33 になります。これは、フィボナッチ数列の最初の8項が 0, 1, 1, 2, 3, 5, 8, 13 であり、その合計が 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33 となるためです。

解法のアプローチ

この問題は、メモ化再帰(キャッシュ付きの再帰) を使うことで効率的に解けます。素朴な再帰では同じ値を何度も計算してしまい指数時間かかりますが、一度計算した結果を保存しておくことで線形時間に抑えられます。

具体的には、以下の手順に従います。

• 法(モジュロ)として m := 10^8 + 7 を定義します。
• 計算済みの結果を保存するための辞書(メモ)memo を用意します。
• 関数 solve() を定義します。引数は n と m です。
• n がすでに memo に存在する場合は、計算を省略して memo[n] を返します。
• n < 2 の場合は memo[n] := n、それ以外の場合は memo[n] := (solve(n-1, m) + solve(n-2, m)) mod m とします。
• memo[n] を返します。
• メイン処理では、memo に格納された値のリストを取得し、最初の n 個の合計を出力します。

実装例

以下のPythonコードを見ると、仕組みがよりよく分かります。

m = 10**8+7
memo = {}
def solve(n, m):
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else (solve(n-1, m)+solve(n-2, m)) % m
    return memo[n]

n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))

入力

8

出力

33

ポイントのまとめ

この実装の重要なポイントは次のとおりです。

• メモ化による高速化: 各フィボナッチ数は一度だけ計算されるため、計算量は O(n) になります。
• 剰余計算: 大きな n に対しては値が急速に増大するため、毎回 mod 10^8 + 7 を取ることでオーバーフローを防ぎます(Pythonでは大きな整数も扱えますが、計算を軽く保つために有効です)。
• 合計の取得: 再帰呼び出しの過程で memo に最初の n 項がすべて格納されるため、その値を合計するだけで答えが得られます。