求一個序列中最大的子序列

Problem statement:

問題陳述：

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

Solution

解

What is Subsequence?

什么是子序列？

A subsequence is not same as subarray. A subarray means collection of contiguous elements from an array. Where subsequence means a set of elements from the array, let's say S,

子序列與子數組不同。 子數組表示從數組中收集連續元素。 如果子序列表示數組中的一組元素，那么說S ，

Where ant two pair (a_i,b_j)(where, i and j are their respective indices from original array and a and b be their respective value) i<j

其中ant兩對(a _i ，b _j )(其中i和j是它們各自從原始數組開始的索引，而a和b是它們各自的值) i <j

Let's say A=1, 2, 3, 4, 5

假設A = 1、2、3、4、5

A subsequence Scan be {1, 3, 5} but not {2, 1, 4}

子序列掃描為{1、3、5}，但不是{2、1、4}

Whereas both are not subarrays.

兩者都不是子數組。

So to find the subsequence where elements are Fibonacci number we need to check the subsequent elements Fibonacci number or not. If element is Fibonacci we can add to our subsequence.

因此，要找到元素為斐波那契數的子序列，我們需要檢查后續元素是否為斐波那契數。 如果element是斐波那契，我們可以添加到我們的子序列中。

Pre-requisite:

先決條件：

1. Input array A

   輸入數組A

2. A Boolean function isFibo(n) that checks whether n is Fibonacci or not

   布爾函數isFibo(n) ，用于檢查n是否為斐波那契

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

現在最有趣的是isFibo(n)函數。 檢查給定的數字是否為斐波那契真是令人討厭。 但是數學一直是一個很好的福音，以至于斐波那契數和黃金比例之間存在著可愛的聯系，這實際上導致了一個很好的公式來檢查數字是否為斐波那契數

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

如果5 * n * n +4或5 * n * n -4是理想平方，則n是斐波那契數。 有關詳細信息，請在此處檢查： 搜索斐波那契數

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

C ++實現

#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

翻譯自: https://www.includehelp.com/icp/largest-fibonacci-subsequence.aspx

求一個序列中最大的子序列