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

兔子不吃窝边草

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

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

实现原理：
        由n找到斐波那契数列中稍大于n的值F[k]（F[k]不能等于n，因为n为存储最后一个数据的下标,F[k]个数是从数组a[]的下标0开始计数的，最后一位为a[F[k]-1]），
由于F[k]=F[k-1]+F[k-2] ,从a[]数组下标1计数共F[k]-1个数，F[k]-1 = ( F[k-1]-1 ) +( F[k-2]-1 )+1,这个1就是分隔点mid；
        mid =low+F[k-1]-1，low为起点，F[k-1]-1为mid到low的差值。
        当key<a[mid]时，说明在左半区，新的范围内个数为 F[k-1]-1，k=k-1；
        当key>a[mid]时，说明在右半区，新的范围内个数为F[k-2]-1，k=k-2；
        当F[k]的值很大时，mid无限接近黄金分割点0.618的位置，

#include<stdio.h>
int F[100];
int count; 
void Fibonacci(int *F,int n)
{
        int i;
        F[0]=0;
        F[1]=1;
        for(i=2;i<=n;i++)
        F[i]=F[i-1]+F[i-2];
}
int Fibonacci_Search(int *a,int n,int key)
{
        int low,high,mid,i,k;
        low =1;
        high =n;
        k=0;
        while(n>F[k]-1)
                k++;
        for(i=n;i<=F[k]-1;i++)
                a[i] = a[n];
        while(low<=high)
        {
                count++;
                mid = low+F[k-1]-1;
                if(key<a[mid])
                {
                        high = mid-1;
                        k =k-1;
                }
                else if(key>a[mid])
                {
                        low =mid+1;
                        k =k-2;
                }
                else
                {
                        if(mid<=n)
                        return mid;
                        else
                        return n;
                }
        }
}
int main()
{
        int n,m,key,i;
        int a[100];
        printf("输入查找个数，斐波那契数组的最大下标，查找值\n");
        scanf("%d%d%d",&n,&m,&key);
        for(i=0;i<=n;i++)
        scanf("%d",&a[i]);
        Fibonacci(F,m);
        printf("查找次数次数:%d,在数组中的位置:%d",count,Fibonacci_Search(a,n,key));
        return 0;
} 

兔子不吃窝边草

                               
登录/注册后可看大图

嘉岳呀

建议不要直接发文本代码

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

兔子不吃窝边草

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

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

多谢提醒，已经修正了。