Șirul lui Fibonacci în C++

Ce este șirul lui Fibonacci?

Șirul Fibonacci este un șir de numere descoperit de matematicianul Leonardo Pisano, unde fiecare element se generează pe baza ultimelor două numere. Astfel:

• Primele două numere ale șirului sunt egale cu 1: f1 = 1, f2 = 1;
• Pentru celelalte numere: fn = fn - 1 + fn - 2 (n ≥ 3).

Unele persoane consideră și elementul 0 ca fiind elementul f0 al șirului.

Astfel, primele 20 de numere ale șirului sunt 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …, care verifică condiția fn = fn-1 + fn-2:

Șirul lui Fibonacci în C++

Pentru a implementa șirul Fibonacci în C++, ne vom folosi de trei variabile, a, b și c, cu următorul algoritm:

• La început, a și b sunt egale cu 1 (primele două elemente Fibonacci);
• La fiecare pas, c primește a + b (devenind astfel noul termen Fibonacci generat), iar a devine b și b devine c (ca să generăm următorul element, care ar fi fost egal cu b + c)

Atenție: doar primii 45 de termeni ai șirului încap în tipul de date int!

Următorul cod C++ afișează pe ecran primele n elemente ale șirului lui Fibonacci (n ≥ 2):

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n; //Numărul de elemente de afișat

    int a = 1, b = 1, c;
    cout << a << " " << b << " "; //Afișăm primii 2 termeni
    for(int i = 3; i <= n; i++) { //Afișăm restul de termeni, de la 3 la n
        c = a + b; //Conform algoritmului descris mai sus
        a = b;
        b = c;

        cout << c << " "; //Afișăm noul element generat
    }
    return 0;
}

Exerciții propuse

Să se completeze următoarele secvențe de cod:

int a = 1, b = 1, c, x;
cin >> x;
cout << a << " " << ??? << " ";
while(a + b <= ???) {
    c = a + b;
    a = b;
    b = c;
    cout << c << " ";
}

??? a = 1, b = 1, c;
cout << a << " " << b << " ";
for(int i = 3; i <= 60; i++) {
    c = a + b;
    a = b;
    b = c;

    cout << c << " ";
}

Probleme propuse

Alte resurse sau bibliografie

• PbInfo: Șirul lui Fibonacci
• Lectiinformatica
• 100din100: Generarea șirului Fibonacci în C++