Se consideră şirul Fibonacci, definit astfel: f1=1, f2=1, respectiv fn=fn-1+fn-2, dacă n>2.

Cerinţa

Se dă un şir cu n elemente, numere naturale. Să se afişeze elementele şirului care sunt termeni ai şirului lui Fibonacci.

Se va defini şi apela o funcţie fibo care verifică dacă un număr natural, transmis ca parametru, face parte din şirul lui Fibonacci.

Date de intrare

Pe prima linie a fişierului fiboverif1.in se află numărul n, iar pe a doua linie n numere naturale.

Date de ieşire

Pe prima linie a fişierului fiboverif1.out se vor afla elementele şirului dat care sunt termeni ai şirului lui Fibonacci, separaţi prin exact un spaţiu.

Restricţii şi precizări

• 1 ≤ n ≤ 10
• elementele şirului vor avea cel mult 9 cifre

Exemplu

fiboverif1.in

8
13 1 8 24 21 55 47 8

fiboverif1.out

13 1 8 21 55 8

#include <bits/stdc++.h>
using namespace std;

ifstream fin("fiboverif1.in");
ofstream fout("fiboverif1.out");

int fibo(int n)
{
    int a[100];
    a[0]=1 , a[1]=1;
    int ok=0;
    if(n==1)
    ok++;
    for(int i = 2 ; a[i-1] <= n ; ++i)
    {
        a[i]=a[i-1]+a[i-2];
        if(a[i]==n)
        {
        ok++;
        break;
        }
    }
    if(ok)
    return 1;
    else
    return 0;
}

int main()
{
    int n;
    fin >> n;
    int a[1000];
    for(int i = 0 ; i < n ; ++i)
    {
        fin >> a[i];
        if(fibo(a[i]))
        fout << a[i] << ' ';
    }
    
    fin.close();
    fout.close();
    
    return 0;
}