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):

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

• Brainly
• PbInfo