Generarea șirului Fibonacci generalizat în C++

Dându-se două numere naturale, f1 și f2, să se genereze șirul Fibonacci generalizat, cu primii doi termeni f1 și f2 și termenul general f(n) = f(n - 1) + f(n - 2).

Exemplu. Pentru f1 = 3 și f2 = 1, primele elemente ale șirului sunt 3 1 4 5 9 14 23… (4 = 3 + 1, 5 = 1 + 4, 9 = 4 + 5, …).

Vom genera doar primele 10 elemente pentru a exemplifica algoritmul.

Vom prezenta două metode — una cu vectori și una folosind doar trei variabile.

Metoda 1 (vectori)

Vom crea un șir care să conțină șirul Fibonacci generalizat, în care primii doi termeni sunt f1 și f2. Vom aplica formula termenului general f[n] = f[n - 1] + f[n - 2] pentru a genera următorii termeni. La final, vom afișa vectorul generat.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim primii doi termeni
    int f1, f2;
    cin >> f1 >> f2;

    //Formăm șirul Fibonacci generalizat
    int f[11];
    f[1] = f1; //Atribuim primele două valori în șir
    f[2] = f2;
    for(int i = 3; i <= 10; i++) { //Folosind termenul general al șirului, generăm restul elementelor
        f[i] = f[i - 1] + f[i - 2];
    }

    //Afișăm șirul f la final
    for(int i = 1; i <= 10; i++) {
        cout << f[i] << " ";
    }
    return 0;
}

Metoda 2 (trei variabile)

Observăm că dacă avem doi termeni în două variabile, după ce generăm noul termen, nu mai avem nevoie de termenul mai vechi. Astfel, putem să procedăm astfel:

• Creăm o variabilă auxiliară aux, care ia valoarea termenului curent (f1 + f2);
• Variabila f1 preia valoarea lui f2 (f2 devine noul f1);
• Variabila f2 preia valoarea lui aux (aux este acum f1);
• Afișăm f2 (elementul curent);
• Repetăm pașii până când generăm primii n termeni.

Vom afișa înainte primii doi termeni.

Implementare C++

#include <iostream>

using namespace std;

int main()
{
    //Declarăm și citim primii doi termeni
    int f1, f2;
    cin >> f1 >> f2;

    //Formăm și afișăm șirul Fibonacci generalizat
    cout << f1 << " " << f2 << " "; //Afișăm primii doi termeni
    for(int i = 3; i <= 10; i++) { //Generăm restul termenilor
        int aux = f1 + f2;
        f1 = f2;
        f2 = aux;
        cout << aux << " "; //Afișăm noul element generat
    }
    return 0;
}