Java プログラミングスキル - データ構造とアルゴリズム「フィボナッチ検索」

[[398011]]

基本的な紹介

フィボナッチとは、線分を 2 つの部分に分割し、一方の長さと全体の長さの比率が、もう一方の部分とこの部分の比率と等しくなるようにすることです。最初の 3 桁のおおよその値は 0.618 です。この比率に従って設計された形状は非常に美しいため、黄金比、または中外比率とも呼ばれています。
フィボナッチ数列 {1,1,2,3,5,8,13,21,34,55} では、フィボナッチ数列内の 2 つの隣接する数字の比率が黄金比の値 0.618 に限りなく近いことがわかりました。

フィボナッチ探索原理

フィボナッチ探索の原理は、二分探索や補間探索に似ています。中間点（mid）の位置を変えるだけです。midはもはや中間でも補間でもなく、黄金分割点の近くにあります。つまり、mid = low + F（k-1）-1、Fは以下に示すようにフィボナッチ数列を表します。

F(k-1)-1の理解:

フィボナッチ数列 F[k] = F[k-1]+F[k-2] の性質により、**(F[k]-1) = (F[k-1]-1)+(F[k-2]-1)+1** が得られます。この式は、主系列テーブルの長さが F[k]-1 の場合、上図に示すように、テーブルを **F[k-1] と **F[k-2]** の長さの 2 つのセグメントに分割できることを示しています。したがって、中間の位置は、mid = low+F(k-1)-1 です。
同様に、各フィールドも同様の方法で分割できます。
ただし、シーケンスリストの長さ n は必ずしも F[k]-1 と正確に等しいとは限らないため、シーケンスリストの元の長さ n を F[k]-1 に増やす必要があります。ここでの k の値は、F[k]-1 が n とちょうど同じかそれよりも大きくなる程度に十分です。次のコードでは、シーケンステーブルの長さが増加した後、新しく追加された位置 (n+1 から F[k]-1 まで) にはすべて n の位置の値が割り当てられます。

 n>fib(k)-1 の場合{
   関数
}

コード例

パッケージ com.xie.search; 
 
パブリッククラス Fibonacci { 
 
公共 静的void main(String[] args) {
 int arr[] = {1, 8, 10, 89, 1000, 1234};
整数n = 6;
整数x = 1; 
 
 // int [] arr = 新しいint [100];
 // ( int i = 0; i < 100; i++)の場合{
 // arr[i] = i;
 // }
 // int n = 100;
 // int x = 1; 
 
        System.out.println ( "インデックスで見つかりました: " +
                fibMonaccianSearch(arr, x, n));
    } 
 
    /**
     * xとyの最小値を返す
     *
     * @パラメータ x
     * @param y
     * @戻る 
     */
公共 静的 整数 最小値( int x, int y) {
戻り値(x <= y) ? x : y;
    } 
 
    /**
     * フィボナッチはxのインデックスを検索し、見つかった場合はそのインデックス位置を返し、見つからない場合は-1を返します。
     * <p>
     * アルゴリズムの説明:
     * arr[0..n-1]を入力配列とし、検索する要素をxとします。
     * 1. n 以上の最小のフィボナッチ数を見つけます。この数をfibM [m番目のフィボナッチ数]とすると、
     * 前の 2 つのフィボナッチ数を fibMm1 [(m-1) 番目のフィボナッチ数] と fibMm2 [(m-2) 番目のフィボナッチ数] とします。
     * 2. 配列内にチェックする要素がある場合:
     * a. x を fibMm2 がカバーする範囲の最後の要素と比較します。x が一致する場合は、インデックスを返します。
     * b. x が要素より小さい場合は、3 つのフィボナッチ変数を 2 つのフィボナッチ分前方に移動します。つまり、残りの配列の最後の約 3 分の 2 が削除されます。
     * c. x が要素より大きい場合は、3 つのフィボナッチ変数を 1 つのフィボナッチ分後方にシフトします。オフセットをインデックスにリセットします。これらを合わせると、残りの配列の約 3 分の 1 が削除されることになります。
     * 3. 比較する要素がもう 1 つある可能性があるので、fibMm1 が 1 かどうかを確認します。そうであれば、x は残りの要素と比較されます。一致する場合は、インデックスが返されます。
     *
     * @param arr 配列
     * @param x 検索する値
     * @param n 配列の長さ
     * @return x インデックス位置または -1
     */
公共 静的  int fibMonaccianSearch( int arr[], int x, int n) {
        // フィボナッチ数を初期化する
        //(m-2)番目のフィボナッチ数
fibMMm2 = 0;
        //(m-1)番目のフィボナッチ数
fibMMm1 = 1;整数
        //m番目のフィボナッチ数
fibM = fibMMm2 + fibMMm1; 
 
        /* fibM は n 以上の最小のフィボナッチ数を格納します*/
        （fibM < n）の間{
            fibMMm2 = fibMMm1;
            fibMMm1 = fibM;
            fibM = fibMMm2 + fibMMm1;
        } 
 
        // 前のマークから範囲を削除します
整数オフセット = -1; 
 
        /* 要素をループします。arr[fibMm2] と x を比較することに注意してください。fibM が 1 になると、fibMm2 は 0 になります */
        （fibM > 1）の場合{
            // fibMm2 が有効な位置であるかどうかを確認します
int i = min (オフセット + fibMMm2, n - 1); 
 
            /* x がインデックス fibMm2 の値より大きい場合、オフセットから i までのサブ配列に分割されます */
            もし（arr[i] < x）{
                fibM = fibMMm1;
                fibMMm1 = fibMMm2;
                fibMMm2 = fibM - fibMMm1;
                オフセット = i;
            }そうでなければ(arr[i] > x) {
                /*インデックス fibMm2 の値より小さい場合、配列は i+1 から arr.length-1 までカットされます*/
                fibM = fibMMm2;
                fibMMm1 = fibMMm1 - fibMMm2;
                fibMMm2 = fibM - fibMMm1;
            }それ以外{
                /* 見つかった場合はインデックスを返す */
 iを返します。
            }
        } 
 
        /* 最後の要素を x と比較します */
        (fibMMm1 == 1 && arr[オフセット + 1] == x)の場合{
オフセット+1を返します。
        } 
 
        /*結果が見つからない場合は -1 を返します */
 -1 を返します。
    }
 }