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的位置，

1. #include<stdio.h>
   
2. int F[100];
   
3. int count;
   
4. void Fibonacci(int *F,int n)
   
5. {
   
6.         int i;
   
7.         F[0]=0;
   
8.         F[1]=1;
   
9.         for(i=2;i<=n;i++)
   
10.         F[i]=F[i-1]+F[i-2];
    
11. }
    
12. int Fibonacci_Search(int *a,int n,int key)
    
13. {
    
14.         int low,high,mid,i,k;
    
15.         low =1;
    
16.         high =n;
    
17.         k=0;
    
18.         while(n>F[k]-1)
    
19.                 k++;
    
20.         for(i=n;i<=F[k]-1;i++)
    
21.                 a[i] = a[n];
    
22.         while(low<=high)
    
23.         {
    
24.                 count++;
    
25.                 mid = low+F[k-1]-1;
    
26.                 if(key<a[mid])
    
27.                 {
    
28.                         high = mid-1;
    
29.                         k =k-1;
    
30.                 }
    
31.                 else if(key>a[mid])
    
32.                 {
    
33.                         low =mid+1;
    
34.                         k =k-2;
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         if(mid<=n)
    
39.                         return mid;
    
40.                         else
    
41.                         return n;
    
42.                 }
    
43.         }
    
44. }
    
45. int main()
    
46. {
    
47.         int n,m,key,i;
    
48.         int a[100];
    
49.         printf("输入查找个数，斐波那契数组的最大下标，查找值\n");
    
50.         scanf("%d%d%d",&n,&m,&key);
    
51.         for(i=0;i<=n;i++)
    
52.         scanf("%d",&a[i]);
    
53.         Fibonacci(F,m);
    
54.         printf("查找次数次数:%d,在数组中的位置:%d",count,Fibonacci_Search(a,n,key));
    
55.         return 0;
    
56. }

复制代码

兔子不吃窝边草

                               
登录/注册后可看大图

嘉岳呀

建议不要直接发文本代码

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

兔子不吃窝边草

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

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

多谢提醒，已经修正了。