fnfn-I+fn-2 从而可得菲薄那序列为:0,1,2,3,5,8,13,21,…假设利用一个数组r来存放 菲薄那数列,且r数组中的元素安关键字从大到小的顺序排列,并且假定元素个数n比某个 fibonacci数fm小1,即n=fm-1,第一次,用要检索的关键字key与r[fm-l]key进行比较, 其算法思想为: (1)若key=rfm-1]key,则检索成功,r[fm-1]为key所在纪录 (2)若key<rfm-l]key,则下一次检索时再从1到fm1-1的范围进行,此时序列长度为 (3)若 key>r[fm-1]key,则下一次检索在从下标从m-1+1到fm-1的范围进行 此时该序列的长度为fm-1)-fm-1+1)+1=m-fm-1-1=fm2-1,从而可得 设r为顺序存储线性表,则 rI1].key <=r[2 .key=..<rn]. key key为已知关键字,在r中检索关键字为key的纪录,若找到,则返回其下标,否则返 回0。假定m为 fibonacci数列的序号,则有fm+l=n+1(>=0fm+1>l1,n为记录元素个 数)。 算法实现]首先可定义一个递归函数,求 fibonacci数列的函数 if(n==O)return(O) else if(n==l)return(1) return (fibonacci(n-1)+fibonacci(n-2): 1 然后再给出数列检索的算法: #define keytype int; #define datatype int type struct g rectype. . fn=fn-1+fn-2 n>=2; 从而可得菲薄那序列为：0，1，2，3，5，8，13，21，…..假设利用一个数组 r 来存放 菲薄那数列，且 r 数组中的元素安关键字从大到小的顺序排列，并且假定元素个数 n 比某个 fibonacci 数 fm 小 1，即 n=fm- 1,第一次，用要检索的关键字 key 与 r[fm-1].key 进行比较， 其算法思想为： (1) 若 key=r[fm-1].key，则检索成功，r[fm-1]为 key 所在纪录 (2)若 key<r[fm-1].key，则下一次检索时再从 1 到 fm-1 -1 的范围进行，此时序列长度为 fm-1; （3） 若 key>r[fm-1].key，则下一次检索在从下标从 fm-1 +1 到 fm -1 的范围进行， 此时该序列的长度为(fm –1)-(fm-1 +1)+1=fm-fm-1 –1=fm-2 -1，从而可得 到： 设 r 为顺序存储线性表，则： r[1].key<=r[2].key<=…….<=r[n].key key 为已知关键字，在 r 中检索关键字为 key 的纪录，若找到，则返回其下标，否则返 回 0。假定 m 为 fibonacci 数列的序号，则有 fm+I=n+1(I>=0,fm+1>I+1,n 为记录元素个 数)。 [算法实现] 首先可定义一个递归函数，求 fibonacci 数列的函数 int fibonacci(n) int n; { if(n==0)return(0); else if(n==1)return(1); else return (fibonacci(n-1)+fibonacci(n-2));} 然后再给出数列检索的算法： #define keytype int; #define datatype int; type struct { keytype key; datatype other; }rectype;