Video: Al N-lea termen Fibonacci în C++

Al N-lea termen Fibonacci în C++

Dându-se un număr natural n, să se determine al n-lea termen din șirul Fibonacci.

Exemplu. Pentru n = 9, F(n) = F(9) = 34.

Ce este șirul Fibonacci?

Șirul Fibonacci, cunoscut după matematicianul Leonardo Bonacci, este șirul definit astfel:

  • primii doi termeni ai șirului, F(1) și F(2), sunt egali cu 1.
  • următorii termeni ai șirului sunt definiți după relația F(n) = F(n - 1) + F(n - 2).

Curiozități despre șirul Fibonacci

  • Primii termeni ai șirului sunt 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ….
  • Doar primii 46 de termeni încap în int — așadar de regulă se lucrează cu variabile de tip long long.

Cum se determină al n-lea termen Fibonacci (cu vector)

Vom crea un vector în care al i-lea element reprezintă al i-lea termen Fibonacci. Vom genera acest vector până la n.

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim variabilele
    int n, fibo[51];
    cin >> n;

    //Generăm șirul
    fibo[1] = fibo[2] = 1;
    for(int i = 3; i <= n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }

    //Afișăm al n-lea termen
    cout << fibo[n];
    return 0;
}

Cum se determină al n-lea termen Fibonacci (recursiv)

Soluția recursivă este foarte ineficientă, deoarece se recalculează aceeași termeni de multe ori. Cu toate acestea, este un exemplu bun de a demonstra recursivitatea:

#include <iostream>

using namespace std;

int fibo(int n) {
    if(n == 1 || n == 2) { //Cazuri particulare
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

int main()
{
    //Declarăm și citim
    int n;
    cin >> n;

    //Afișăm al n-lea termen
    cout << fibo(n);
    return 0;
}

De ce nu este eficientă această soluție?

Să analizăm grafic ce se întâmplă dacă apelăm fibo(5):

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

Observăm că în timpul calculării lui fibo(5), apelăm fibo(4) și fibo(3). Când apelăm fibo(4), apelăm din nou fibo(3), pe care l-am calculat deja. Acesta este un exemplu simplu în care se observă faptul că se repetă calcularea anumitor termeni, dar pentru calcularea fibo(30), de exemplu, poate lua până la un minut — operație ce, în fond, doar face 30 de sume.

Alte resurse și bibliografie

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