斐波纳契

一.概述

如果从文件中读取的数据记录的关键字排列有序(递增或递减)，则可以使用比二分搜索法方法更有效的搜索方法来查找文件中的记录，即斐波那契搜索，也称为黄金分割搜索方法。

二、什么是斐波那契搜索

斐波那契数列，又叫黄金分割数列，指这样一个数列：1，1，2，3，5，8，13，21，…数学上，斐波那契数列用递归方法定义如下：F(1)=1，F(2)=1，f (n)=f，随着数列的进行，两个相邻数的比值趋于黄金比例值(0.618)。

第三，基本思路

斐波那契搜索方法类似于二分搜索法的基本思想，就是减少搜索序列的长度，各个击破地搜索关键词。他的搜索过程是：先确定要搜索的记录的范围，然后逐渐缩小搜索范围，直到找到该记录(或者搜索可能失败)。

斐波那契搜索是在二分搜索法的基础上根据斐波那契序列划分的。在斐波那契数列中找到一个略大于查找表中元素个数的数字F[n]，将原查找表扩展到长度为Fn，完成后进行斐波那契分段，即把F[n]个元素分成前半部分的F[n-1]个元素和后半部分的F[n-2]个元素，找出要搜索的元素在哪里，递归直到找到为止。

斐波那契搜索的时间复杂度仍然是O(log 2 n)，但是与二分搜索法相比，斐波那契搜索的优点是只涉及加减，不涉及除法，除法比加减耗时更多。所以斐波那契搜索的运行时间理论上比二分搜索法短，但还是要看具体情况。

四.例子

对于斐波那契数列：1，1，2，3，5，8，13，21，34，55，89.(也可以从0开始)，随着级数的增加，前后两个数的比值越来越接近0.618的黄金比例。比如这里的89被认为是整个有序表中的元素个数，89是前面两个斐波那契数34和55的和，也就是说89个元素的有序表分为前半部分由前55个数据元素组成，后半部分由后34个数据元素组成，所以前半部分的元素个数与整个有序表长度的比值接近黄金分割比0.618。如果要搜索的元素在前半部分，那么继续看斐波那契序列，55=34 ^ 21，那么继续把前半部分分成前34个数据元素的前半部分和后21个元素的后半部分，继续搜索，重复这个过程直到搜索成功或者失败，从而把斐波那契序列应用到搜索算法中。

在此插入图片描述

从图中可以看出，当有序表中的元素个数不是斐波那契数列中的某个数时，就需要把有序表中的元素个数的长度补上，使之成为斐波那契数列中的一个数值。当然不可能截断原来的有序表，不然怎么找？然后图中表示每次取斐波那契数列中的某个值(F[k])，都会进行-1运算，因为有序表数组的位次是从0开始的，纯粹是为了迎合从0开始的位次。

5.怎么算

作为二分搜索法方法的增强和优化版本，它将黄金分割的思想融入到关键字的搜索中，并根据斐波那契序列的特点划分有序表。

1.斐波那契阵列

斐波那契搜索是二分搜索法的变体。其时间复杂度为O(log2n)。

斐波那契数列，又称黄金分割数列，f {1，1，2，3，5，8，13，21，34，…} f={1，1，2，3，5，8，13，21，34，…}数学表达式：

在此插入图片描述

之所以也叫黄金分割系列，是因为随着数字的增加，前一项与后一项的比例逐渐接近0.618的黄金分割比例。

2.用斐波那契数列确定元素的位置

因此，斐波那契搜索改变了二分搜索法原有中值中值的求解方式，它的中值不再代表中值，而是代表黄金分割点：

在此插入图片描述

二分搜索法，将数组除以一半元素；

斐波那契搜索，数组除以黄金分割点。

假设表中有n个元素，搜索过程是取区间中间元素的下标mid，将mid的关键字与给定值的关键字进行比较：

(1)如果与给定关键字相同，则搜索成功，并返回表中的位置；

(2)如果给定的关键字很大，找到并向右减少2个斐波那契区间；

(3)如果给定的关键字很小，则向左查找并减少一个斐波那契区间；

(4)重复该过程，直到找到关键字(成功)或间隔为空集(失败)。

它要求起始表中的记录数比一个斐波那契数少一个，n=F(k)-1；

将k值与F(k-1)位置(中=低F(k-1)-1)的记录进行比较，比较结果也分为三种类型

(1) key=k [mid]，中间位置的元素就是你想要的；

(2)keyk[mid]，low=mid 1，k-=2；

说明：low=mid 1表示要搜索的元素在[mid 1，high]范围内，k-=2表示[mid 1，high]范围内的元素个数为n-(f(k-1))=fk-1-f(k-1)=fk-f(k-1)-1=

(3)keyk[mid]，high=mid-1，k-=1 .

说明：low=mid 1表示要搜索的元素在[low，mid-1]范围内，k-=1表示[low，mid-1]范围内的元素个数为F(k-1)-1，因此可以递归应用斐波那契搜索。

斐波那契搜索也是二分搜索法的一种改进算法。利用黄金分割比的概念，在序列中选择搜索点进行搜索，提高了搜索效率。同样，斐波那契搜索属于有序搜索算法。

3.例子

例如，假设有集合E0=2，E1=3，E2=7，E3=14，E4=22，E5=33，E6=55，E7=75，E8=89，E9=123。

找到元素44的过程：

已知：

元素号大小=10；

下标区间[低，高]为左=0，右=9。

那么初始化后的斐波那契数列就是FIB={1，1，2，3，5，8，13} FIB={1，1，2，3，5，8，13}，也就是斐波那契数列的最后一位大于size-1。

这时搜索的步是：刚初始化完，斐波那契数列的最后一个区间是第六个区间，即区间(8，13)；第8位数字是当前黄金分割点，那么第8位数字是下标7，检测到的数字是E7。数组除以8后，左边的区间是(1，8)。

在此插入图片描述

这时搜索的第二步是：和步一样，黄金分割点是下标4的第五位数字。

在此插入图片描述

上一步结束时，还剩{33 55}。这时搜索的第三步是：黄金分割点是第二个数字55，下标是6。

在此插入图片描述

上一步结束时，还剩{33}个。这时搜索的第四步是：黄金分割点是个数字33，下标是5。

在此插入图片描述

不及物动词代码实现

1.斐波那契数组实现

//生成斐波那契序列

无效斐波那契(int* F)

{

int I=0；

f[0]=1；

f[1]=1；

for(I=2；I N；I)

{

F[I]=F[I-1]F[I-2]；

}

}

2.斐波那契搜索

int search(int* a，int key，int n)

{

int i=0，low=0，high=n-1；

int mid=0，k=0，F[N]；

斐波那契(F)；

While (n F[k]-1) //计算斐波那契数列中n的序列

{

k；

}

//不满足时完成数组

for(I=0；I F[k]-1；I)

{

a[I]=a[高]；//用数组的最后一项完成数组

}

while(低=高)

{

mid=low F[k-1]-1；//根据斐波那契数列除法

如果(a[mid]键)//更小，它就在左边

{

高=mid-1；

k-=1；//左：F[N-1]-1通式：F[N]-1=F[N-1]-1 F[N-2] -1 1

}

else if(一个[mid]键)

{

low=mid 1；

k-=2；//右：F[N-12]-1

}

其他

{

If (mid=high)//如果是真的，找到对应的位置

返回中间；

其他

return-1；

}

}

}

3.实验数据和测试

# includestdio.h

#定义N 30

//生成斐波那契序列

无效斐波那契(int* F)

{

int I=0；

f[0]=1；

f[1]=1；

for(I=2；I N；I)

{

F[I]=F[I-1]F[I-2]；

}

}

int search(int* a，int key，int n)

{

int i=0，low=0，high=n-1；

int mid=0，k=0，F[N]；

斐波那契(F)；

While (n F[k]-1) //计算斐波那契数列中n的序列

{

k；

}

//不满足时完成数组

for(I=0；I F[k]-1；I)

{

a[I]=a[高]；//用数组的最后一项完成数组

}

while(低=高)

{

mid=low F[k-1]-1；//根据斐波那契数列除法

如果(a[mid]键)//更小，它就在左边

{

高=mid-1；

k-=1；//左：F[N-1]-1通式：F[N]-1=F[N-1]-1 F[N-2] -1 1

}

else if(一个[mid]键)

{

low=mid 1；

k-=2；//右：F[N-12]-1

}

其他

{

If (mid=high)//如果是真的，找到对应的位置

返回中间；

其他

return-1；

}

}

}

int main()

{

int a[N]={ 2，3，5，7，9，11，12，15，19，22 }；

int k，r=0；

Printf('请输入要查找的号码：')；

scanf_s('%d '，k)；

r=search(a，k，10)；

if (r！=-1)

printf(' \ n在数组的位置%d找到元素：%d\n '，r 1，k)；

其他

printf(' \ n在数组中找不到元素：%d\n '，k)；

返回0；

}

在此插入图片描述

4.编译环境

Visual Studio 2019