Șirul lui Fibonacci: iterativ, recursiv și termeni din fișier

Șirul lui Fibonacci începe cu doi termeni egali cu 1, iar fiecare termen următor este suma celor doi dinaintea lui:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Matematic: F₁ = F₂ = 1 și F_n = F_n−1 + F_n−2 pentru n ≥ 3. Unele enunțuri pornesc de la F₀ = 0 sau definesc altfel primii termeni, așa că citește cu atenție definiția din problemă. La BAC informatică, șirul este un exemplu clasic pentru trei lucruri: bucle cu trei variabile, recursivitate și probleme de eficiență.

Varianta iterativă: trei variabile care „alunecă”

Nu ai nevoie de vector ca să generezi termenii. Îți ajung ultimii doi termeni, pe care îi actualizezi la fiecare pas:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;                  // n >= 2, de exemplu 10
    int a = 1, b = 1;
    cout << a << " " << b;
    for (int i = 3; i <= n; i++)
    {
        int c = a + b;
        cout << " " << c;
        a = b;
        b = c;
    }
    return 0;
}

Pentru n = 10 se afișează 1 1 2 3 5 8 13 21 34 55. Ordinea atribuirilor contează: dacă scrii b = c înaintea lui a = b, pierzi vechea valoare a lui b. Complexitatea este O(n), iar memoria folosită e constantă.

În pseudocod, aceeași idee arată astfel și o vei recunoaște ușor la Subiectul II:

citește n
a ← 1; b ← 1
pentru i←3,n execută
    c ← a+b
    a ← b
    b ← c
scrie b

Acest algoritm afișează F_n pentru n ≥ 2 (pentru n = 10 afișează 55).

Varianta recursivă și de ce este lentă

Definiția se traduce direct într-o funcție recursivă:

int fib(int n)
{
    if (n <= 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Este corectă, dar foarte ineficientă, pentru că recalculează aceleași valori de multe ori. Arborele de apeluri pentru fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

Sunt 9 apeluri în total pentru un rezultat egal cu 5, iar fib(3) se calculează de două ori. Dacă notezi cu A(n) numărul de apeluri, ai A(1) = A(2) = 1 și A(n) = A(n−1) + A(n−2) + 1, deci A(3) = 3, A(4) = 5, A(5) = 9, A(6) = 15, A(7) = 25. Numărul de apeluri crește aproape la fel de repede ca șirul însuși, adică exponențial. Pentru fib(45) sunt de ordinul miliardelor de apeluri.

Varianta cu vector

Dacă ai nevoie de mai mulți termeni simultan (de exemplu, să verifici dacă numere citite sunt termeni ai șirului), îi poți memora într-un vector:

int F[50];
F[1] = F[2] = 1;
for (int i = 3; i <= 45; i++)
    F[i] = F[i - 1] + F[i - 2];

Fiecare termen se calculează o singură dată, deci O(n). Limita de 45 nu e aleasă întâmplător: F₄₆ = 1 836 311 903 încă încape în int, dar F₄₇ = 2 971 215 073 depășește 2 147 483 647. Cu long long poți merge până la F₉₂.

Observă cât de repede crește șirul: F₄₄ = 701 408 733 este ultimul termen mai mic decât 10⁹. Asta înseamnă că sub un miliard există mai puțin de 50 de termeni Fibonacci — o observație esențială pentru problemele de eficiență.

Problemă cu fișier: câte numere sunt termeni Fibonacci

Fișierul bac.in conține cel mult 10⁶ numere naturale din intervalul [1, 10⁹]. Se cere numărul de valori din fișier care sunt termeni ai șirului lui Fibonacci.

Descrierea algoritmului: generez o singură dată termenii șirului mai mici sau egali cu 10⁹ (sunt mai puțin de 50) și îi păstrez într-un vector. Citesc numerele din fișier unul câte unul, fără să le memorez, și pentru fiecare caut dacă apare printre termeni. Fiecare căutare are cel mult câteva zeci de pași, deci timpul este proporțional cu numărul de valori din fișier, iar memoria folosită este constantă (un vector de 50 de elemente).

#include <fstream>
using namespace std;

int main()
{
    ifstream fin("bac.in");
    int F[50], k = 2;
    F[1] = F[2] = 1;
    while (F[k - 1] + F[k] <= 1000000000)
    {
        F[k + 1] = F[k - 1] + F[k];
        k++;
    }
    // F[1..k] sunt termenii <= 10^9
    int x, nr = 0;
    while (fin >> x)
    {
        bool gasit = false;
        for (int i = 2; i <= k && F[i] <= x; i++)
            if (F[i] == x)
                gasit = true;
        if (gasit)
            nr++;
    }
    ofstream fout("bac.out");
    fout << nr;
    return 0;
}

Pentru fișierul 4 13 1 100 89 21 se scrie 4 (13, 1, 89 și 21 sunt termeni; 4 și 100 nu). Căutarea pornește de la indicele 2 pentru că F[1] și F[2] sunt ambele egale cu 1, deci e suficient să compari o singură dată cu valoarea 1. Bucla se oprește și când termenii depășesc x, pentru că șirul e crescător.

Fibonacci în ordine inversă

O altă cerință întâlnită: se dau doi termeni consecutivi ai șirului, x < y, și trebuie afișați toți termenii până la primul, în ordine descrescătoare. Ideea: dacă y = x + z, termenul anterior lui x este z = y − x.

while (x > 0)
{
    cout << y << " ";
    int z = y - x;
    y = x;
    x = z;
}
cout << y;

Pentru x = 21 și y = 34 se afișează 34 21 13 8 5 3 2 1 1. La ultimul pas, din perechea (1, 1) se obține z = 0, bucla se oprește, iar instrucțiunea de după ea afișează ultimul 1.