Fw: [課業] 資料結構/費式搜尋比較次數問題
※ [本文轉錄自 Examination 看板 #1Gy3LSNt ]
作者: 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
推
01/12 11:34, , 1F
01/12 11:34, 1F
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: pthread (111.253.199.191), 時間: 01/12/2013 19:59:12