Pythonで分かるフィボナッチ数列とフィボナッチ探索のアルゴリズム

スポンサーリンク

フィボナッチ探索は、与えられたリストから要素を見つけるために使用される、もう一つの分割統治アルゴリズムです。

この記事では、フィボナッチ探索がどのように動作するか、バイナリサーチとどう違うか、そしてpythonで実装します。

スポンサーリンク

前提条件

フィボナッチ探索を始める前に、まず理解しておかなければならないことが2つあります。

1. バイナリサーチ

バイナリサーチは分割統治アルゴリズムであり、答えを見つけるためにリストを分割することを意味します。

このアルゴリズムを実行するために、与えられたリストはソートされている必要があります。

リストはソートされているので、ターゲットは真ん中の要素から相対的にどこにあるかがわかります。

リストの真ん中でターゲットを見つけるか、真ん中の要素より小さいか大きいかによって、真ん中から片方を排除します。

片方を排除したら、もう片方でこの処理を繰り返す。

このように、1回の反復でリストの半分を削っていくので、n個の要素を見つけるにはlog2n回の反復で済みます。

2. フィボナッチ数

フィボナッチ数とは、フィボナッチ級数を構成する数です。

そこで、まずフィボナッチ級数を定義してみましょう。

級数は再帰的に次のように定義できる。

F(n) = F(n-1) + F(n-2)
F(1) = 1
F(0) = 0

フィボナッチ数を得るには、指数や黄金比を含む公式で直接得る方法もありますが、この方法は、級数の捉え方の意味するところです。

上の定義で、F(n)は「n番目のフィボナッチ数」という意味です。

つまり、0番目のフィボナッチ数は0、1番目のフィボナッチ数は1、2番目のフィボナッチ数は1番目と0番目のフィボナッチ数の和、3番目のフィボナッチ数は2番目と1番目のフィボナッチ数の和、、、となります。

最後に、n番目のフィボナッチ数は、その前の2つのフィボナッチ数の和、つまり、(n-1)番目のフィボナッチ数と(n-2)番目のフィボナッチ数の和となるのです。

以下は、最初の10個のフィボナッチ数の計算です。

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = 3 + 2 = 5
F(6) = 5 + 3 = 8
F(7) = 8 + 5 = 13
F(8) = 21
F(9) = 34
F(10) = 55
...

つまり、0番目から始まるフィボナッチ級数は

F = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

フィボナッチ探索をPythonで実装する

バイナリサーチと同様に、フィボナッチサーチも分割統治アルゴリズムであり、ソートされたリストが必要です。

また、リストを2つに分割し、2つの部分の中心にある項目と対象を比較し、その比較結果に基づいて片方を消去します。

では、具体的にバイナリサーチとどう違うのでしょうか。

フィボナッチ探索では、フィボナッチ数を使ってリストを2分割するので、リストを長さの異なる2つの部分に分割することになります。

また、そのために割り算を行うのではなく、CPUへの負荷が少ない足し算を行います。

では、詳細を見ていきましょう。

まず、与えられたリストの長さが必要です。

次に、リストの大きさ以上の最小のフィボナッチ数を見つけます。

つまり、リストのサイズが100であれば、100より大きい最小のフィボナッチ数は144です。

これをフィボナッチ数n番目とします。

上の例では、144は12番目のフィボナッチ数です。

この後、その数からフィボナッチ級数を2回遡ることになる。

基本的には、(n-2)番目のフィボナッチ数を求めます。

つまり、上の例では、12番目のフィボナッチ数は144なので、10番目のフィボナッチ数は55となります。

これをインデックスとして、リストを2つに分割するのです。

つまり、リストのこのインデックスを見て、リストが昇順にソートされていると仮定して、このインデックスの項目がターゲットより小さければ左側を、そうでなければ右側を排除します。

これを、探している項目が見つかるまで、つまり、計算したインデックスの項目がターゲットと一致するまで続けます。

では、このアルゴリズムのコードを見てみましょう。

def fibonacci_search(lst, target):
    size = len(lst)
     
    start = -1
     
    f0 = 0
    f1 = 1
    f2 = 1
    while(f2 < size):
        f0 = f1
        f1 = f2
        f2 = f1 + f0
     
     
    while(f2 > 1):
        index = min(start + f0, size - 1)
        if lst[index] < target:
            f2 = f1
            f1 = f0
            f0 = f2 - f1
            start = index
        elif lst[index] > target:
            f2 = f0
            f1 = f1 - f0
            f0 = f2 - f1
        else:
            return index
    if (f1) and (lst[size - 1] == target):
        return size - 1
    return None

では、実際に実行して出力を見てみましょう。

Fibonacci Search Example
Fibonacci Search Example

まとめ

この記事では、フィボナッチ数とは何か、フィボナッチ探索アルゴリズムでどのように使用されるか、アルゴリズム自体がどのように動作するか、そしてそのアルゴリズムをpythonで実装しました。

次のチュートリアルでお会いしましょう。

タイトルとURLをコピーしました