1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
#include<iostream>
#include<string>
#include<fstream>
#include<ctime>
using namespace std;
int FibonacciNumber(int arr_last_entry,int &fnm2)
{
int fn1=1,fn2=-1,temp=0;
while(fn1<=arr_last_entry)
{
fnm2=fn2;
temp=fn1;
fn1=fn1+fn2;
fn2=temp;
}
return fn2;
}
void FibonacciSearch(string *storewords,string f_skeyword,int left,int right)
{
int arr_pos=0,fnm1=0,fnm2=0;
arr_pos=FibonacciNumber(right,fnm2);
fnm1=arr_pos;
while((left<right)&&(storewords[left-1+fnm1]!=f_skeyword))
{
if(f_skeyword<storewords[left-1+fnm1])
{
right=right-fnm2; //right-=fnm2;
fnm2=fnm1-fnm2;
fnm1=fnm1-fnm2; //fnm1-=fnm2;
}
else
{
left=left+fnm1;
fnm1=fnm1-fnm2; //fnm1-=fnm2;
fnm2=fnm2-fnm1; //fnm2-=fnm1;
}
}
if(storewords[left-1+fnm1]==f_skeyword)
cout<<"YES";
else
cout<<"NO";
}
void main(void)
{
string a[12]={"0","1","2","3","5","6","9","11","15","18","20","23"};
string f="0"; //numbers that can't be found: 9 6 5 3 2
FibonacciSearch(a,f,0,11);
system("pause");
}
|