首页 > 试题广场 >

下列算法为斐波那契查找的算法: int FibSearch(

[问答题]

下列算法为斐波那契查找的算法:

int FibSearch(SqList r, KeyType K)
 {
 j=1;
 while(fib(j)<n+1)
 j = j + 1;
 mid = n - fib(j-2) + 1;          //若fib(j)=n+1，则mid=fib(j-1)
 f1 = fib(j-2);
 f2 = fib(j-3);
 found = FALSE;
 while((mid<>0) && !found)
 switch
 {
 case K=r[mid].key:
 found = TRUE;
 break;
 case K<r[mid].key:
 if(!f2)
 mid = 0;
 else
 {
 mid = mid-f2;
 t = f1 - f2;
 f1 = f2;
 f2 = t;
 }
 break;
 case K>r[mid].key:
 if(f1=1)
 mid = 0;
 else
 {
 mid = mid + f2;
 f1 = f1 - f2;
 f2 = f2 – f1;
 }
 break;
 }
 if(found)
 return mid;
 else
 return 0;
 }//FibSearch

其中fib(i)为斐波那契序列(若表中所有记录的关键字满足下列关系：ST.elem[i].key≤ST.elem[i+1}.key i=1,2,…n-1。则称表中记录按关键字有序)。试画出对长度为20的有序表进行斐波那契查找的判定树，并求在等概率时查找成功的平均查找长度。