在fibonacci搜索算法方面需要帮助

Question

根据从search获得的理解，我试图为fibonacci搜索添加java代码：

设k定义为F中的一个元素，Fibonacci数的数组。N= Fm是数组大小。如果数组大小不是Fibonacci数，设Fm是F中大于n的最小数。

定义了Fibonacci数数组，其中Fk+2 = Fk+1 + Fk，当k≥0，F1 = 1，F0 = 0时。

若要测试项目是否在序号列表中，请执行以下步骤：

设k= m，如果k=0时，停止。没有匹配项；项不在数组中。将项目与Fk−1中的元素进行比较。如果该项匹配，则停止。如果项目小于输入Fk−1，则丢弃从−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

我终于能解决这个难题了，这就阻止了我..。

我认为下面的代码应该能帮助像我这样被困的人。

package com.search.demo;

public class FibonacciSearch {

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

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    fs = new FibonacciSearch();
    int location = fs.find(70);
    if(location < 0){
        System.out.println("number not found..");
    }else{
        System.out.println("found at location "+location);
    }
}

private int find(int no){
    int n = a.length;
    int m = findFm(n);                  //m = Fm iff n is Fibonacci number else returns Fm+1
    int p = fibSequenceIterative(m-1);  //p = Fm-1, always a fibonacci number
    int q = fibSequenceIterative(m -2); //q = Fm-2, always a fibonacci number

    while(true){
        if(no == a[m]){
            return m;
        }else if (no < a[m]){
            if(q == 0){
                return -(m - 1);// we crossed 0th index in array, number not found.
            }                   
            m = m - q;  //moved to 1 step left towards a fibonacci num
            int tmp = p;//hold this temporarily
            p = q;      //move p to 1 step left into another fibonacci num
            q = tmp - q;//moved q to 1 step left....
        }else if(no > a[m]){
            if(p == 1){
                return -m;//we reached 0th index in array again and number not found..
            }
            m = m + q;
            p = p - q;
            q = q - p;
        }
    }

}

private int findFm(int n){
    int prev = 1;
    int curr = 1;
    int next = 0;

    if(n == 0){
        next = 0;
        return -1;
    }else if(n == 1 || n == 2){
        next = 1;
        return 1;
    }else{
        for(int i = 3; ; i++){
            next = prev + curr;
            prev = curr;
            curr = next;
            System.out.println("prev = "+prev+" curr = "+curr+" next = "+next);
            if(n <= curr){
                System.out.println("n = "+n+" curr = "+curr);
                return i;
            }
        }
        //return -1;//we should not get here..
    }


}

/* Iterative method for printing Fibonacci sequence..*/
private int fibSequenceIterative(int n){
    int prev = 1;
    int curr = 1;
    int next = 0;

    if(n == 0){
        next = 0;
        //return 0;
    }else if(n == 1 || n == 2){
        next = 1;
        //return 1;
    }else{
        for(int i = 3; i <= n; i++){
            next = prev + curr;
            prev = curr;
            curr = next;
        }
        return next;
    }
    return next;
}


}

我所做的错误之处是管理索引，这确实会影响在索引位置划分数组的位置。

应该首先找到m，以匹配n(数组大小)的值。如果不匹配，它应该是F(x)将> n的下一个值，也就是说，在我的情况下，大小为10，不匹配任何fibonacci数，因此fibonacci级数中的下一个值是13，并且我们满足条件的指数为F(7) = 13，即> 10。所以m=7。

现在p和q是两个连续的fibonacci数，它总是决定划分数组的间隔。

请阅读以下内容：

取N= 54，使N+1 = 55 = F10。我们将搜索排序数组: A1，.，A54，包含。数组索引严格在两个Fibonacci数之间:0< 55。这个搜索使用从F10 = 55，即F9 = 34降下来的下一个斐波那契数，而不是中点。我们没有将搜索间隔除以两边的50%，而是大致除以黄金分割，大约62%的左边和38%的右侧。如果y == A34，那么我们已经找到它了。否则，我们有两个较小的搜索间隔:0到34和34到55，不包括端点。如果有两个连续的斐波那契数，很容易用减法向后移动，所以上面，从34返回的下一个数字是55-34= 21。我们将以0比34的比分，中间的比分是21。从34到55的范围用下一个斐波那契数被打破:34-21= 13。整个间隔34，55的长度是21，从开始到34 + 13 = 47。注意，这不是Fibonacci数，而是所有间隔的长度。(从http://www.cs.utsa.edu/~wagner/CS3343/binsearch/fibsearch.html复制)

Answer 2

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

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