Q:

Given an array with positive number the task to find the largest subsequence from array that contain elements which are Fibonacci numbers

0

Given an array with positive number the task to find the largest subsequence from array that contain elements which are Fibonacci numbers.

Example:

    Input array:
    2 4 5 8 13 15 21

    Output:
    2 5 8 13 21

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

    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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now