java - 在斐波那契搜索算法方面需要帮助

Question

我正在尝试根据我从中获得的理解将 java 代码用于斐波那契搜索 http://en.wikipedia.org/wiki/Fibonacci_search :

将 k 定义为 F 中的一个元素，即斐波那契数列。 n = Fm 是数组大小。如果数组大小不是斐波那契数，则令 Fm 为 F 中大于 n 的最小数。

斐波那契数列定义为 Fk+2 = Fk+1 + Fk，当 k ≥ 0，F1 = 1，F0 = 0。

要测试一个项目是否在有序数字列表中，请按照下列步骤操作:

设 k = m。如果 k = 0，则停止。没有匹配项；该项目不在数组中。将项目与 Fk−1 中的元素进行比较。如果项目匹配，则停止。如果项目小于条目 Fk-1，则丢弃位置 Fk-1 + 1 到 n 的元素。设置 k = k − 1 并返回步骤 2。如果项目大于条目 Fk-1，则丢弃从位置 1 到 Fk-1 的元素。将剩余元素从1重新编号为Fk−2，设k = k − 2，返回步骤2。

下面是我的代码:

package com.search.demo;

public class FibonacciSearch {

static int[] a = {10,20,30,40,50,60,70,80,90,100};

static int required = 70;
static int m = 2;
static int p = 0;
static int q = 0;


/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    FibonacciSearch fs = new FibonacciSearch();
    fs.findm();
    fibSearch(required);
}

private void findm(){
    //here you have to find Fm which matches size of searching array, or which is close to it.
    int n = a.length;
    int fibCurrent = 1;
    int fibPrev1 = 1;
    int fibPrev2 = 0;

    while(n > fibCurrent){
        fibPrev2 = fibPrev1;
        fibPrev1 = fibCurrent;
        fibCurrent = fibPrev1 + fibPrev2;
        m++;
    }
    p = m-1;
    q = m-2;
}

public static int fibSearch(int no){
    for(;;){

        if(m == 0){
            System.out.println("not found");
            return -1;
        }
        int j = f(p);

        if(no == a[j]){
            System.out.println("found at "+p);
        }else if(no < a[j]){
            m = p;
            p = m - 1;
            q = m - 2;

        }else if(no > a[j]){
            m = q; // as per the step 6..
            p = m-1;
            q = m-2;
        }
    }
    //return m;
}

public static int f(int val){

    if(val == 2 || val == 1 || val == 0){
        return 1;
    }
    return (f(val-1) + f(val-2));
}


}

请指正我做错了什么，并帮助我清楚地理解它..

我看过这个Fibonacci Search和 http://www.cs.utsa.edu/~wagner/CS3343/binsearch/searches.html但我无法理解..

Answer 1

while(n > fibCurrent){
                      fibPrev2 = fibPrev1;
                      fibPrev1 = fibCurrent;
                      fibCurrent = fibPrev1 + fibPrev2;
                      m++;
                    }

findm() 函数中的这部分实际上是比较第 n 个斐波那契数，但根据算法，它应该是截至该点的斐波那契数的累加和。相反，您可以在 findm 的 while 循环中搜索元素。