Declare subsequence S
For i=0:Array length -1
IF isFibo(A[i])
Add A[i] to S
END IF
END For
Now the most interesting is isFibo(n) function. It really looks like nasty to check whether a given number is Fibonacci or not. But mathematics has been such a nice boon that there exists a lovely relation between Fibonacci number and golden ratio, which actually resulted in a nice formula to check for a number whether Fibonacci number or not
If 5*n*n +4 or 5*n*n -4 is perfect square then n is a Fibonacci number. For details check over here: Search a Fibonacci number
Example with explanation:
Input array:
2 4 5 8 13 15 21
2 is Fibonacci no: 5*2*2-4 is perfect square(5*2*2-4=16)
5 is Fibonacci no: 5*5*5-4 is perfect square(5*5*5-4=121)
8 is Fibonacci no: 5*8*8+4 is perfect square(5*8*8+4=324)
13 is Fibonacci no: 5*13*13-4 is perfect square(5*13*13-4=841)
21 is Fibonacci no: 5*21*21+4 is perfect square(5*21*21+4=2209)
Subsequence is:
2 5 8 13 21
C++ implementation
#include <bits/stdc++.h>
using namespace std;
//checking a is Fibonacci or not
bool isFibo(int a){
int t1=sqrt(5*a*a+4);
int t2=sqrt(5*a*a-4);
//checking whether t1 or t2 is perfect square
if(t1*t1==(5*a*a+4))
return true;
if(t2*t2==(5*a*a-4))
return true;
return false;
}
void largestSubsequence(vector<int> a,int n)
{
for(int i=0;i<n;i++)
if(isFibo(a[i]))
cout<<a[i]<<" ";
}
int main()
{
int n,item;
cout<<"enter no of elements\n";
scanf("%d",&n);
cout<<"Enter array elements\n";
vector<int> a;
for(int j=0;j<n;j++){
scanf("%d",&item);
a.push_back(item);
}
cout<<"Largest fibonacci Subsequence is:\n";
largestSubsequence(a,n);
cout<<endl;
return 0;
}
Output
enter no of elements
7
Enter array elements
2 4 5 8 13 15 21
Largest fibonacci Subsequence is:
2 5 8 13 21
Algorithm:
Now the most interesting is isFibo(n) function. It really looks like nasty to check whether a given number is Fibonacci or not. But mathematics has been such a nice boon that there exists a lovely relation between Fibonacci number and golden ratio, which actually resulted in a nice formula to check for a number whether Fibonacci number or not
If 5*n*n +4 or 5*n*n -4 is perfect square then n is a Fibonacci number. For details check over here: Search a Fibonacci number
Example with explanation:
C++ implementation
Output
need an explanation for this answer? contact us directly to get an explanation for this answer