Dându-se un număr natural n, să se verifice dacă este sau nu un termen al șirului Fibonacci.

Exemplu. Pentru n = 13, răspunsul este DA, pe când, pentru n = 14, răspunsul este NU.

Ce este șirul Fibonacci

Șirul Fibonacci este un faimos șir, care se generează pe baza următoarei reguli:

Astfel, primele elemente ale șirului sunt: 1, 1, 2, 3, 5, 8, 13, 21, ….

Explicarea algoritmului

Vom genera elementele șirului Fibonacci până când elementul curent este egal sau mai mare decât n (numărul pe care îl verificăm). Astfel, dacă atingem valoarea n, înseamnă că n este un termen Fibonacci. Dacă, în schimb, trecem peste valoarea n, înseamnă că n nu face parte din șirul Fibonacci.

Implementare C++

Iată secvența de cod care verifică dacă un număr n este sau nu număr Fibonacci.

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim numărul pe care îl verificăm, n
    int n;
    cin >> n;

    if(n == 1) { //Caz particular
        cout << "DA";
    } else {
        //Generăm șirul Fibonacci pentru a verifica dacă n face parte din șir
        //Îl vom genera cu trei variabile: c = fn, b = fn-1, a = fn-2
        int a = 1, b = 1, c;
        int esteTermenFib = 0; //În caz că nu este termen Fibonacci, să afișăm NU la final
        do {
            c = a + b;
            a = b;
            b = c;
            if(n == c) { //Este termen Fibonacci
                esteTermenFib = 1;
                cout << "DA";
                break;
            }
        } while(c <= n);
        if(esteTermenFib == 0) { //Nu este termen Fibonacci
            cout << "NU";
        }
    }
    return 0;
}

Bibliografie sau alte resurse

• 100din100
• Invata.info
• PbInfo
• cwsin