＜アルゴリズムの基本④＞繰り返し処理（２）配列を使ったフィボナッチ数列

さまざまな数列の値を保持するのには、配列が便利です。今回は、フィボナッチ数列を求めるアルゴリズムについてまとめます。

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。
この数列 (Fn)はフィボナッチ数列（フィボナッチすうれつ、Fibonacci sequence）と呼ばれ、
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …（オンライン整数列大辞典の数列 A45）
と続く。最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている。

目的
擬似コード例
Pythonコード例
1. 出力例
2. 処理時間の検証
まとめ

目的

先頭からｎ個（ｎ≧２）のフィボナッチ数列を生成する

擬似コード例

整数ｎまでのフィボナッチ数列を求めるアルゴリズムを擬似コードで表します。

Procedure Fibo(n)
    f[0] ← 0
    f[1] ← 1
    i  ← 2
    while i < n do
          f[i] ← f[i-2] + f[i-1]
          i ← i + 1
    end-while
    return f

Pythonコード例

上記アルゴリズムをPythonコードで記載しました。

def fibo(n):　# n個のフィボナッチ数列を生成する関数
    f = [0 for i in range(n)] 　　　　　　　　　 # n個の 空の配列を準備
    f[0] = 0　　#0番目に0を代入
    f[1] = 1　　#1番目に1を代入
    i = 2
    while i < n:
        f[i] = f[i-2] + f[i-1]
        i += 1
    return f

出力例

>>> fibo(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> fibo(15)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

処理時間の検証

前回同様に、データ量と処理速度の関係を調べました。下記のグラフは上記アルゴリズムを使ってフィボナッチ数列を10（=10^1）〜10,000(=10^4)個生成させた場合の処理時間をプロットしたものです。縦軸・横軸ともに基底を10とした対数値としてあります。（コードはこちら）
これにより、上記アルゴリズムの処理時間はデータ量にほぼ比例することがわかります。

フィボナッチ数列の生成時間

まとめ

今回は、配列をつかってフィボナッチ数列を求めるアルゴリズムを検討してみました。次回も引き続き配列を使った繰り返し処理についてまとめる予定です。

（参考文献：杉浦賢、図解でかんたんアルゴリズム　情報処理のかなめとなる考え方が手に取るようにわかる、Softbank Creative）