[[398011]]

基本介紹

1. 斐波那契是指把一條線段分割成兩部分，使其中一部分與全長之比等于另一部分與這部分之比。取其前三位數字的近似值是0.618。由于按此比例設計的造型十分美麗，因此也稱為黃金分割，也稱中外比。
2. 斐波那契數列{1,1,2,3,5,8,13,21,34,55}發現斐波那契數列的兩個相鄰數的比例，無限接近黃金分割值0.618.

斐波那契查找原理

斐波那契查找原理與二分查找和插值查找相似，僅僅改變了中間點(mid)的位置，mid不再是中間或插值得到的，而是位于黃金分割點附近，即mid = low+F(k-1)-1,F代表斐波那契數列，如下圖

對F(k-1)-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]**的兩段，即如上圖所示。從而中間位置為：mid = low+F(k-1)-1。
2. 類似的，每個字段也可以才用相似的方式分割。
3. 但順序表長度n不一定剛好等于F[k]-1，所以需要將原來的順序表長度n增加至F[k]-1。這里的k值只要能使得F[k]-1恰好大于等于n即可，由以下代碼得到，順序表長度增加后，新增的位置(從n+1到F[k]-1),都賦為n位置的值即可.

while(n>fib(k)-1){ 
   k++; 
} 

 代碼案例

package com.xie.search; 
 
public class Fibonacci { 
 
    public static void main(String[] args) { 
        int arr[] = {1, 8, 10, 89, 1000, 1234}; 
        int n = 6; 
        int x = 1; 
 
//        int[] arr = new int[100]; 
//        for (int i = 0; i < 100; i++) { 
//            arr[i] = i; 
//        } 
//        int n = 100; 
//        int x = 1; 
 
        System.out.println("Found at index: " + 
                fibMonaccianSearch(arr, x, n)); 
    } 
 
    /** 
     * 返回x和y最小的數 
     * 
     * @param x 
     * @param y 
     * @return 
     */ 
    public static int min(int x, int y) { 
        return (x <= y) ? x : y; 
    } 
 
    /** 
     * 斐波那契搜索x的索引，找到就返回索引位置，否則返回-1 
     * <p> 
     * 算法說明： 
     * 令arr[0..n-1]為輸入數組，要搜索的元素為x。 
     * 1.找到大于或等于n的最小斐波那契數。將此數字設為fibM [第m個斐波納契數], 
     * 設其前面的兩個斐波那契數為fibMm1 [第（m-1）個斐波那契數]和fibMm2 [第（m-2）個斐波那契數]。 
     * 2.當數組中有要檢查的元素時： 
     *  a.將x與fibMm2覆蓋范圍的最后一個元素進行比較,如果x匹配，則返回索引; 
     *  b.如果x小于元素，則將三個Fibonacci變量向前移動兩個Fibonacci，表示消除了剩余數組的大約后三分之二； 
     *  c.如果x大于元素，則將三個斐波那契變量向后移動一個斐波那契。將偏移量重置為索引。這些加在一起表明消除了其余陣列的大約三分之一； 
     * 3.由于可能還有一個元素需要比較，因此請檢查fibMm1是否為1。如果是，則將x與該剩余元素進行比較。如果匹配，則返回索引。 
     * 
     * @param arr 數組 
     * @param x   查找的值 
     * @param n   數組的長度 
     * @return x索引位置或者-1 
     */ 
    public static int fibMonaccianSearch(int arr[], int x, int n) { 
        // 初始化斐波那契數 
        //第（m-2）個斐波那契編號 
        int fibMMm2 = 0; 
        //第（m-1）個斐波那契編號 
        int fibMMm1 = 1; 
        //第 m個斐波那契數 
        int fibM = fibMMm2 + fibMMm1; 
 
        /* fibM將存儲最小的斐波那契數大于或等于n*/ 
        while (fibM < n) { 
            fibMMm2 = fibMMm1; 
            fibMMm1 = fibM; 
            fibM = fibMMm2 + fibMMm1; 
        } 
 
        // 從前面標記消除的范圍 
        int offset = -1; 
 
        /* 循環檢查元素,注意，我們將arr[fibMm2]與x進行了比較,當fibM變為1時，fibMm2變為0 */ 
        while (fibM > 1) { 
            // 檢查fibMm2是否為有效位置 
            int i = min(offset + fibMMm2, n - 1); 
 
            /* 如果x大于索引fibMm2處的值，則將從offset到i切割為子數組 */ 
            if (arr[i] < x) { 
                fibM = fibMMm1; 
                fibMMm1 = fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
                offset = i; 
            } else if (arr[i] > x) { 
                /*如果小于索引fibMm2處的值，則將從i+1到arr.length-1進行切割數組*/ 
                fibM = fibMMm2; 
                fibMMm1 = fibMMm1 - fibMMm2; 
                fibMMm2 = fibM - fibMMm1; 
            } else { 
                /*找到了，就返回索引*/ 
                return i; 
            } 
        } 
 
        /* 將最后一個元素與x比較 */ 
        if (fibMMm1 == 1 && arr[offset + 1] == x) { 
            return offset + 1; 
        } 
 
        /*沒有找打，返回-1 */ 
        return -1; 
    } 
} 

 【編輯推薦】