Șirul lui Fibonacci și calculul sumelor

Șirul lui Fibonacci

Definiție recurentă: $F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}$

Primii termeni: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

Iterativ sau recursiv

Recursivitatea naivă recalculează aceiași termeni de nenumărate ori. Pentru $F(5)$ se fac 15 apeluri; pentru $F(40)$, peste 300 de milioane.

La BAC, dacă se cere doar valoarea, folosește varianta iterativă. Recursivitatea se cere când subiectul o indică explicit sau când trebuie urmărit arborele de apeluri.

Atenție la depășire

$F_{47}$ depășește deja int pe 32 de biți. Peste $n = 46$, folosește long long (C/C++), int64 (Pascal). În Python nu e problemă, întregii cresc oricât.

Sume cu termen general dat

Tiparul e mereu același:

1. inițializezi acumulatorul cu 0 pentru sumă, cu 1 pentru produs;
2. parcurgi cu un contor;
3. adaugi (sau înmulțești) termenul general.

Exemple:

• $S = 1 + 2 + \ldots + n$, cu verificare: $n(n+1)/2$;
• $S = 1^2 + 2^2 + \ldots + n^2$, cu verificare: $n(n+1)(2n+1)/6$;
• $S = 1 + 1/2 + \ldots + 1/n$ (suma armonică), care cere tip real.

Greșeli frecvente

1. Se pornește șirul cu $F_1 = 1, F_2 = 1$ când problema cere $F_0 = 0$. Citește cu atenție indexarea din enunț.
2. Se folosește recursivitatea naivă pentru $n$ mare și programul depășește timpul.
3. Se uită depășirea la $n > 46$.

#include <iostream>
using namespace std;

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

    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << "F(" << n << ")=" << a << " ";

    long long s = 0, p = 1;
    for (int i = 1; i <= 5; i++) {
        s += i;
        p *= i;
    }
    cout << "suma1..5=" << s << " produs1..5=" << p;
    return 0;
}