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;
} 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
建议不要直接发文本代码
点击按钮就可以发带有 "复制代码" 的代码了,那样别人会看着舒服点
多谢提醒,已经修正了。
页:
[1]