作者pthread (QQ)
看板Examination
标题Re: [课业] 资料结构/费式搜寻比较次数问题
时间Fri Jan 11 23:52:57 2013
※ 引述《pthread (QQ)》之铭言：
: 假设今天有如下数列
: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
: 如果用费式搜寻搜寻以下键值 2,10,15
: 各需要几次比较次数呢~?
: 我的答案是
: 2:5次 15:4次 10:4次
: 因为跟书上的答案不一样,算的不知道对不对
: 烦请各位版友指正
怎麽每个人答案不一
用程式跑出的结果跟我自己算的一样
#include <iostream>
#define FibNum 20
using namespace std;
int fibsearch(int [],int [],int,int,int);
int main(){
int k;
int n=16;
int data[16]={1,2,9,16,20,21,52,59,92,97,100,120,122,130,140,145};
int F[FibNum];
F[0]=0;
F[1]=1;
for(int i=2;i<FibNum;i++){
F[i]=F[i-1]+F[i-2];
}
for(k=0;k<FibNum;k++){
if((n>F[k]-1)&&(n<=F[k+1]-1))
break;
}
k++;
cout<<k<<endl;
int input;
cout << endl << "请输入欲搜寻之资料内容 => ";
cin >> input;
cout<<fibsearch(data,F,n,k,input)<<endl;
system("pause");
return 0;
}
int fibsearch(int a[],int fib[],int n,int k,int key){
int l=0,r=n-1,m;
int flag=0;
for(int i=n;i<fib[k]-1;i++)
a[i]=a[n-1];
while(l<=r){
flag++;
m=l+fib[k-1]-1;
if(a[m]==key){
if(m<n){
cout<<"呼叫次数:"<<flag<<endl;
return m;}
else
return n-1;
}
else if(a[m]>key){
r=m-1;
k=k-1;
}
else{
l=m+1;
k=k-2;
}
}
return -1;
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.253.199.191
1F：推 carterdunk:n=16, n+1不属於Fib里面 所以建树之後每个node要减掉4 01/12 11:34
※ pthread:转录至看板 Grad-ProbAsk 01/12 19:59