Capitolul 18 · Lecția 18.2 din 4

Șirul lui Fibonacci și calculul sumelor

Șirul definit recurent, varianta iterativă vs recursivă și sume cu termen general dat.

Capitolul 18: Algoritmi clasici de BAC

Pe această pagină5 secțiuni

Ș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

	Iterativ	Recursiv naiv
Complexitate	$O(n)$	$O(2^n)$
Memorie	$O(1)$	$O(n)$ pe stivă
F(40)	instantaneu	secunde bune
F(50)	instantaneu	practic imposibil

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:

inițializezi acumulatorul cu 0 pentru sumă, cu 1 pentru produs;
parcurgi cu un contor;
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.

Reține

Inițializarea greșită a acumulatorului e una dintre cele mai frecvente greșeli: 0 la sumă, 1 la produs. Dacă inițializezi produsul cu 0, rezultatul rămâne 0 orice ai face.

Greșeli frecvente

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ț.
Se folosește recursivitatea naivă pentru $n$ mare și programul depășește timpul.
Se uită depășirea la $n > 46$ .

Exemplul, în 4 limbaje

Alege limbajul în care dai examenul. Poți edita codul și îl poți rula direct aici. Programa oficiala de BAC (proba E.d) cere Pascal sau C/C++, la alegere. Python apare in manualele noi si e pus aici pentru inteles, nu ca limbaj de examen.

#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;
}