C++ 所有元素都是斐波那契数的最大子集

斐波那契数列是什么

斐波那契数列是如下整数序列中的数字。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……

通过递推关系，可以用数学术语定义斐波那契数列Fn的序列。

Fn = Fn-1 + Fn-2

使用种子值

F0 = 0 and F1 = 1.

最大子集，其所有元素都是Fibonacci数

给定一个正数数组，任务是找到包含Fibonacci数元素的数组的最大子集。

示例

Input : arr[] = {1, 4, 3, 9, 10, 13, 7};
Output : subset[] = {1, 3, 13}
The output three numbers are Fibonacci numbers.

Input  : arr[] = {0, 2, 8, 5, 2, 1, 4, 13, 23};
Output : subset[] = {0, 2, 8, 5, 2, 1, 13}

遍历给定数组中的所有元素是一个简单的解决方案。检查每个数字是否为Fibonacci数。如果是，将其包含在最终结果中。

C++程序

// C++ program to find largest Fibonacci subset
#include
using namespace std;

// Prints largest subset of an array whose
// all elements are fibonacci numbers
void findFibSubset(int arr[], int n)
{
    // Find maximum element in arr[]
    int max = *std::max_element(arr, arr+n);

    // Generate all Fibonacci numbers till
    // max and store them in hash.
    int a = 0, b = 1;
    unordered_set hash;
    hash.insert(a);
    hash.insert(b);
    while (b < max)
    {
        int c = a + b;
        a = b;
        b = c;
        hash.insert(b);
    }

    // Npw iterate through all numbers and
    // quickly check for Fibonacci using
    // hash.
for (int i=0; i

输出