アルゴリズム初心者向けの基礎と入門(C#, Pythonとか)

フィボナッチ数とは

フィボナッチ数とは、イタリアの数学者レオナルド・フィボナッチにちなんで名付けられた特別な意味を持つ数です。

F₀ = 0

F₁ = 1

F_{n + 2} = F_n + F_{n + 1} (n ≧ 0)

n番目のフィボナッチ数は上記 F_n の式で再帰的に求めることができます。この数列 (F_n) はフィボナッチ数列と呼ばれます。

フィボナッチ数列は以下のように続いていきます。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ...

サンプルコード

フィボナッチ数の定義をそのまま再帰的な形で実装してやればよいので難しいことはありません。

C#

public static int Fib(long n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fib(n - 1) + Fib(n - 2);
}

メモ化

上記コードで 40番目のフィボナッチ数を求めてみます。すると思った以上に実行時間がかかることに気が付きます。これはすでに求めた計算を何度も計算しているからです。例えば、9番目も8番目も求めるときに7番目の計算を行います。

F₉ = F₈ + F₇

F₈ = F₇ + F₆

さらに言えば、n番目のフィボナッチ数を求めるために、1..n-1番目までのフィボナッチ数すべてを再帰的に計算しています。これは非効率です。

一度計算した値を再度計算しないようにメモ化(Memoization)と呼ばれる最適化技法を使って効率化できます。メモ化とは、関数呼び出し結果を再利用できるように保持しておく手法です。今回の例で言えば、一度計算したフィボナッチ数を保持しておき、あとで利用します。

サンプルコード(メモ化)

再帰的に呼び出される関数の外部に、計算結果のフィボナッチ数を保持できる領域を用意します。再帰的に関数を呼び出す際には、計算済であればそれを利用します。未計算であればそれを計算して保存しておきます。

これで40番目のフィボナッチ数もメモ化なしの場合に比べ高速に求められます。

C#

using System.Collections.Generic;

private static Dictionary<int, long> Memo;
public static long Fib(int n)
{
    // メモ化に使う領域を初期化しておく
    Memo = new Dictionary<int, long>();
    return _Fib(n);
}
private static long _Fib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (!Memo.ContainsKey(n))
    {
        // 未計算の数は計算結果を保存しておく
        Memo[n] = _Fib(n - 1) + _Fib(n - 2);
    }
    // 保存している値を返す
    return Memo[n];
}