算法与数据结构实验四 实现Fibonacci检索算法

【文件属性】：

文件名称：算法与数据结构实验四 实现Fibonacci检索算法

文件大小：80KB

文件格式：DOC

更新时间：2014-06-13 16:51:52

编程实现Fibonacci检索算法 完整报告 流程图

 实验内容： 编程实现Fibonacci检索算法  实验原理： Fibonacci数的定义为f0=0,f1=1,fi=f(i-1)+f(i-2)(i≥2)。由此得Fibonacci 数列为0，1，1，2，3，5，8，13，21，34，55，89，144，…… 设数组F中元素按关键字值从小到大顺序排列，并假定元素个数n比某个Fibonacci 树fi小1，即n=fi-1。第一次用待查关键字k与F[f（i-1）]，Key比较，其算法描述 如下： ① 若k=F[f(i-1)],Key，则检索成功，F[f(i-1)]为k所在记录。 ② 若kF[f(i-1)],Key，则下一次的检索范围为下标f(i+1)+1到fi-1，序列长度为（fi-1）-（f(i-1)+1）+1=fi-f(i-1)-1=f(i-2)-1 设F是顺序存储的线性表且满足F[1]，key≤F[2]，key≤…≤F[n]。key,k是已知的关键字值，在F中检索关键字值为k的记录。若找到返回其下标值，否则返回0.