Fibonačijev niz brojeva

Fibonačijev niz je dobio naziv po italijanskom matematičaru Leonardu iz Pize, poznatijem kao Fibonači (Fibonacci). Ako znamo prva dva člana niza:

• F(0) = 0
• F(1) = 1

svaki sledeći član dobija se kao zbir dva prethodna:

F(n) = F(n-1) + F(n-2),  za n ≥ 2

Početak Fibonačijevog niza:

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

---

Fibonačijevi brojevi u prirodi

Fibonačijevi brojevi se često sreću u prirodi. Broj latica mnogih cvetova (3, 5, 8, 13, ...), kao i broj spirala na suncokretu, šišarki i ananasu najčešće su uzastopni Fibonačijevi brojevi. Slično važi i za raspored listova na grani.

Zanimljiv primer je i rodoslov pčela: trut (mužjak) ima samo majku, a ženka ima oba roditelja. Kada se prebroje preci jednog truta po generacijama, dobijaju se brojevi 1, 1, 2, 3, 5, 8, ... Količnik dva uzastopna Fibonačijeva broja približava se zlatnom preseku φ ≈ 1,618.

Geometrijski se niz može prikazati popločavanjem kvadratima čije su stranice uzastopni Fibonačijevi brojevi:

---

Određivanje n-tog Fibonačijevog broja rekurzijom

Definicija niza je prirodno rekurzivna: da bismo izračunali F(n), funkcija mora ponovo da pozove samu sebe za n−1 i n−2.

#include <iostream>
using namespace std;

// Vraća n-ti Fibonačijev broj: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
int fib(int n)
{
    if (n <= 1)          // bazni slučaj: F(0) = 0, F(1) = 1
        return n;

    int f1 = fib(n - 1); // rekurzivni poziv za prethodni član
    int f2 = fib(n - 2); // rekurzivni poziv za član pre njega
    return f1 + f2;
}

int main()
{
    int N, x;
    cin >> N;

    x = fib(N);
    cout << x << endl;

    return 0;
}

Na slici 4 prikazani su pozivi funkcije pri računanju F(4). Isti podproblemi računaju se više puta (na primer, F(2) dva puta), a broj poziva raste eksponencijalno sa n. Zato je ovo rešenje sporo već za n oko 40.

---

Određivanje n-tog Fibonačijevog broja dinamičkim programiranjem

Da bismo skratili vreme izvršavanja, pamtimo u nizu vrednosti koje su već izračunate. Nema rekurzije: pomoću for petlje računamo svaki član sabiranjem njegova dva prethodnika, zapamćena u nizu f.

#include <iostream>
#include <vector>
using namespace std;

// Svaki član računamo samo jednom i pamtimo ga u nizu f
long long fib(int n)
{
    vector<long long> f(n + 2);   // n + 2 da bi f[1] postojao i za n = 0
    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        f[i] = f[i - 1] + f[i - 2];   // zbir dva prethodna, već izračunata člana
    }

    return f[n];
}

int main()
{
    int N;
    cin >> N;

    cout << fib(N) << endl;

    return 0;
}

Svaki član se računa tačno jednom, pa je složenost O(n) vremena i O(n) memorije.

---

Optimizovana metoda: pamćenje samo dva člana

Za računanje sledećeg člana potrebna su samo dva poslednja, pa ne moramo da čuvamo ceo niz:

#include <iostream>
using namespace std;

// Pamtimo samo dva poslednja člana niza
long long fib(int n)
{
    if (n < 2)          // F(0) = 0, F(1) = 1; petlja se tada ne bi izvršila
        return n;

    long long a = 0;    // F(i - 2)
    long long b = 1;    // F(i - 1)
    long long f = 0;    // F(i)

    for (int i = 2; i <= n; i++)
    {
        f = a + b;      // novi član
        a = b;          // pomeramo "prozor" za jedno mesto
        b = f;
    }

    return f;
}

int main()
{
    int N;
    cin >> N;

    cout << fib(N) << endl;

    return 0;
}

Na početku su prethodnici a i b postavljeni na 0 i 1. Kada se odredi novi član f = a + b, pripremaju se prethodnici za sledeći korak: prvi prethodnik postaje dosadašnji drugi (a = b), a drugi postaje upravo izračunati član (b = f). Memorija je sada O(1).

---

Vremenska i prostorna složenost

• Rekurzija: vreme eksponencijalno (oko φ^n poziva)
• Dinamičko programiranje sa nizom: vreme O(n), memorija O(n)
• Optimizovana metoda: vreme O(n), memorija O(1)