77 lines
1.9 KiB
C++
77 lines
1.9 KiB
C++
// Reference: https://gist.github.com/ravichandrae/cd458795c7fab56295ec
|
|
// Reference: https://en.wikipedia.org/wiki/Fibonacci_number
|
|
|
|
#include <cmath>
|
|
#include <vector>
|
|
#include <iostream>
|
|
using namespace std;
|
|
|
|
// Function prototypes
|
|
int getIndex(int number);
|
|
|
|
int main() {
|
|
int number;
|
|
cout<<"Enter a number: ";
|
|
cin >> number;
|
|
|
|
// get the square root of 5 x number x number + 4 (as double)
|
|
double root = sqrt(5.0*number*number+4.0);
|
|
// cast to long long
|
|
long long iRoot = root;
|
|
// if the double and long is equal the this is a fibonacci
|
|
if( root == iRoot )
|
|
{
|
|
cout << getIndex(number) << " is a fibonacci index of " << number;
|
|
}
|
|
else
|
|
{
|
|
// get the square root of 5 x n x n - 4 (as double)
|
|
root = sqrt(5.0*number*number-4.0);
|
|
// cast to long long
|
|
iRoot = root;
|
|
// if the double and long is equal the this is a fibonacci
|
|
if( root == iRoot )
|
|
{
|
|
cout << getIndex(number) << " is the fibonacci index of " << number;
|
|
}
|
|
else
|
|
{
|
|
cout << getIndex(number) << " is the closest fibonacci index of " << number;
|
|
}
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int getIndex(int number)
|
|
{
|
|
// the smallest are basic
|
|
if(number == 0){
|
|
return 1;
|
|
} else if(number == 1){
|
|
return 2;
|
|
} else if(number == 2){
|
|
return 4;
|
|
}
|
|
// now we start with the bigger numbers
|
|
int index = 4;
|
|
int previous = 2;
|
|
int next = 3;
|
|
|
|
// Get and index
|
|
while (true){
|
|
// increment the index only when closest
|
|
if (abs(number - previous) > abs(number - next)) {
|
|
index++;
|
|
}
|
|
// close the loop when next is greater
|
|
if (next > number){
|
|
break;
|
|
}
|
|
// calculate the next Fibonacci number
|
|
int sum = previous + next;
|
|
previous = next;
|
|
next = sum;
|
|
}
|
|
return index;
|
|
}
|