Verifică dacă un număr aparține șirului Fibonacci în C++

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:

https://i.ibb.co/jRfkKfX/image.png

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

DS

Autorul acestei lecții

Dominic Satnoianu

Această lecție a fost redactată de către Dominic Satnoianu.

© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.

Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.

Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.

Comentarii 0

Autentifică-te pentru a putea comenta.

Autentifică-te