论坛 › 数据结构与算法 › c语言——斐波那契查找算法

兔子不吃窝边草 发表于 2021-10-1 18:03:52

c语言——斐波那契查找算法

本帖最后由 兔子不吃窝边草 于 2021-10-2 16:08 编辑

                                                                                                        初学者，学到斐波那契算法，总结实现了一下，各位大佬有啥需要注意的给点建议。

原始数组a[]是从1到n存储数据，n为查找数据的个数，F[]为斐波那契数列。

实现原理：
        由n找到斐波那契数列中稍大于n的值F（F不能等于n，因为n为存储最后一个数据的下标,F个数是从数组a[]的下标0开始计数的，最后一位为a-1]），
由于F=F+F ,从a[]数组下标1计数共F-1个数，F-1 = ( F-1 ) +( F-1 )+1,这个1就是分隔点mid；
        mid =low+F-1，low为起点，F-1为mid到low的差值。
        当key<a时，说明在左半区，新的范围内个数为 F-1，k=k-1；
        当key>a时，说明在右半区，新的范围内个数为F-1，k=k-2；
        当F的值很大时，mid无限接近黄金分割点0.618的位置，
#include<stdio.h>
int F;
int count;
void Fibonacci(int *F,int n)
{
        int i;
        F=0;
        F=1;
        for(i=2;i<=n;i++)
        F=F+F;
}
int Fibonacci_Search(int *a,int n,int key)
{
        int low,high,mid,i,k;
        low =1;
        high =n;
        k=0;
        while(n>F-1)
                k++;
        for(i=n;i<=F-1;i++)
                a = a;
        while(low<=high)
        {
                count++;
                mid = low+F-1;
                if(key<a)
                {
                        high = mid-1;
                        k =k-1;
                }
                else if(key>a)
                {
                        low =mid+1;
                        k =k-2;
                }
                else
                {
                        if(mid<=n)
                        return mid;
                        else
                        return n;
                }
        }
}
int main()
{
        int n,m,key,i;
        int a;
        printf("输入查找个数，斐波那契数组的最大下标，查找值\n");
        scanf("%d%d%d",&n,&m,&key);
        for(i=0;i<=n;i++)
        scanf("%d",&a);
        Fibonacci(F,m);
        printf("查找次数次数:%d,在数组中的位置:%d",count,Fibonacci_Search(a,n,key));
        return 0;
}

兔子不吃窝边草 发表于 2021-10-1 18:08:50

https://baike.baidu.com/pic/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%90%9C%E7%B4%A2/19131306/0/eaf81a4c510fd9f9be07bba72f2dd42a2934a4e8?fr=lemma&ct=single#aid=0&pic=eaf81a4c510fd9f9be07bba72f2dd42a2934a4e8

嘉岳呀 发表于 2021-10-1 20:18:13

建议不要直接发文本代码

点击 <> 按钮就可以发带有 "复制代码" 的代码了，那样别人会看着舒服点

兔子不吃窝边草 发表于 2021-10-2 16:06:32

嘉岳呀 发表于 2021-10-1 20:18
建议不要直接发文本代码

点击按钮就可以发带有 "复制代码" 的代码了，那样别人会看着舒服点

多谢提醒，已经修正了。

查看完整版本: c语言——斐波那契查找算法