Ora 24 - Alte șiruri recurente: Factorial, Lucas și variații

TEORIE - 40 minute

Ce vei învăța astăzi?

După această lecție, vei înțelege șirul factorial, șirul lui Lucas și alte șiruri definite prin relații recurente.

Șirul factorial - definiție și proprietăți

Șirul lui Lucas și relația cu Fibonacci

Șiruri definite prin reguli matematice

Probleme practice cu șiruri recurente

Aplicații ale acestor șiruri în algoritmi

Șirul factorial - n!

Definiție: Șirul factorial este definit ca produsul numerelor naturale de la 1 la n. Notăm cu n! (citim "n factorial").

Formula recurentă:

n! = 1 × 2 × 3 × ... × n = n × (n-1)!
cu condiția inițială: 0! = 1

120

720

Observații importante:

0! = 1 - prin definiție (pentru a păstra coerența în formulele matematice)

1! = 1 - produsul numerelor de la 1 la 1

Cum calculăm 5!: 5! = 5 × 4 × 3 × 2 × 1 = 120

Recurența: 5! = 5 × 4! = 5 × 24 = 120

Analogii pentru factorial:

Farfurii în bufet

Dacă ai 5 farfurii diferite, în câte moduri le poți aranja? Răspuns: 5! = 120 moduri.

Persoane la coadă

În câte moduri pot sta 4 persoane la o coadă? Răspuns: 4! = 24 de moduri.

Cărți pe raft

În câte moduri poți aranja 3 cărți diferite? Răspuns: 3! = 6 moduri.

Piese de șah

Numărul de permutări ale n obiecte distincte este n! – apare des în combinatorică.

Extra (pe înțeles): Factorialul „crește foarte repede”. De aceea, în C++ folosim long long și limităm n (de obicei ≤ 20).

Implementarea factorialului în C++

// FACTORIAL ITERATIV - cel mai eficient long long factorialIterativ(int n) { if (n < 0) return -1; // factorial negativ nu există long long fact = 1; for (int i = 1; i <= n; i++) { fact = fact * i; } return fact; } // EXEMPLU DE UTILIZARE: int main() { int n; cin >> n; cout << n << "! = " << factorialIterativ(n); return 0; }

Atenție la depășire! 20! = 2.432.902.008.176.640.000 care depășește limita lui int. Folosim long long.

Execuție pentru n=5:

fact = 1Valoare inițială

i=1:fact = 1 × 1 = 1

i=2:fact = 1 × 2 = 2

i=3:fact = 2 × 3 = 6

i=4:fact = 6 × 4 = 24

i=5:fact = 24 × 5 = 120

// FACTORIAL RECURSIV - elegant dar mai puțin eficient long long factorialRecursiv(int n) { // Caz de bază if (n < 0) return -1; // eroare if (n == 0) return 1; // 0! = 1 // Caz recursiv: n! = n × (n-1)! return n * factorialRecursiv(n - 1); } // EXEMPLU: calcul 3! recursiv // factorialRecursiv(3) // 3 × factorialRecursiv(2) // 2 × factorialRecursiv(1) // 1 × factorialRecursiv(0) // 1 // = 1 × 1 = 1 // = 2 × 1 = 2 // = 3 × 2 = 6

Recursivitate: O funcție care se autoapelează. Trebuie să ai un caz de bază și un caz recursiv.

Observație: La factorial, recursivitatea e ok pentru n mic (ex: ≤ 20). La Fibonacci „naiv” nu e ok.

fact(3)

3 × fact(2)

fact(2)

2 × fact(1)

fact(1)

1 × fact(0)

fact(0)

Procesul recursiv: apeluri succesive până la cazul de bază

Situație	Soluție cu vector	Când este util	Exemplu
Mai multe factoriale	Calculează toate factorialele de la 0 la n într-un vector	Ai nevoie de mai multe valori factorial rapid	`fact[0]=1, fact[1]=1, fact[2]=2...`
Numere mari	Stochează factorial în vector de cifre	Pentru n>20 (depășește long long)	100! are 158 de cifre
Memoizare	Stochează rezultatele calculate	Evită recalcularea în recursivitate	`if(fact[n]!=0) return fact[n];`

// CALCUL FACTORIALE CU VECTOR (precalcul)
#include <iostream>
using namespace std;

long long fact[21];  // pentru valori până la 20!

void calculeazaFactoriale() {
    fact[0] = 1;
    for (int i = 1; i <= 20; i++) {
        fact[i] = fact[i-1] * i;
    }
}

int main() {
    calculeazaFactoriale();

    cout << "5! = " << fact[5] << endl;   // 120
    cout << "10! = " << fact[10] << endl; // 3628800

    return 0;
}

De ce e util precalculul? Dacă ai multe întrebări (ex: 100 de valori de n), nu mai recalculezi de fiecare dată.

Șirul lui Lucas

Definiție: Șirul lui Lucas este similar cu șirul Fibonacci, dar cu valori inițiale diferite:

L₀ = 2
L₁ = 1
Lₙ = Lₙ₋₁ + Lₙ₋₂ pentru n ≥ 2

Fibonacci

F₀=0 F₁=1 F₂=1 F₃=2 F₄=3 F₅=5 F₆=8 F₇=13

Lucas

L₀=2 L₁=1 L₂=3 L₃=4 L₄=7 L₅=11 L₆=18 L₇=29

Relația dintre Fibonacci și Lucas:

Formula importantă: Lₙ = Fₙ₋₁ + Fₙ₊₁

Exemplu pentru n=4: L₄ = F₃ + F₅ = 2 + 5 = 7 ✓

Alte proprietăți (opțional):

Lₙ × Fₙ = F₂ₙ
Lₙ - 5Fₙ = 4(-1)ⁿ
Lₙ + Lₙ₊₃ = 2Lₙ₊₂

// GENERARE ȘIR LUCAS - similar cu Fibonacci
#include <iostream>
using namespace std;

int lucas(int n) {
    if (n == 0) return 2;
    if (n == 1) return 1;

    int L0 = 2, L1 = 1, Ln = 0;
    for (int i = 2; i <= n; i++) {
        Ln = L0 + L1;
        L0 = L1;
        L1 = Ln;
    }
    return Ln;
}

int main() {
    cout << "Primii 10 termeni Lucas: ";
    for (int i = 0; i < 10; i++) {
        cout << lucas(i) << " ";
    }
    // Afiseaza: 2 1 3 4 7 11 18 29 47 76
    return 0;
}

De reținut: Lucas are aceeași recurență ca Fibonacci, doar pornește diferit (2,1 în loc de 0,1).

Exercițiu de completare - Factorial recursiv:

Completează funcția recursivă pentru calculul factorialului:

#include <iostream>

using namespace ______;

// Funcție factorial recursiv

______ factorial(int n) {

// Caz de bază

if (n ______ 0) return -1; // eroare

if (n == ______) return ______;

// Caz recursiv

return ______ ______ ______(n - 1);

}

______ main() {

int n;

cin >> n;

cout << n << "! = " << ______(n);

return ______;

}

Bancă de cuvinte:

std long long < 0 1 n * factorial int

Hint: La factorial, cazul de bază clasic este n==0 (sau n<=1). Aici folosim n==0 ca să fie foarte clar.

Alte șiruri recurente importante

Șirul Tribonacci: Generalizare a lui Fibonacci cu suma ultimelor 3 termeni.

T₀ = 0, T₁ = 0, T₂ = 1
Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃ pentru n ≥ 3

T₀

T₁

T₂

T₃

T₄

T₅

T₆

T₇

int tribonacci(int n) {
    if (n == 0 || n == 1) return 0;
    if (n == 2) return 1;

    int a = 0, b = 0, c = 1, d;
    for (int i = 3; i <= n; i++) {
        d = a + b + c;
        a = b;
        b = c;
        c = d;
    }
    return c;
}

Numerele Catalan: Folosite în combinatorică pentru numărarea structurilor.

C₀ = 1
Cₙ = (2(2n-1)/(n+1)) × Cₙ₋₁

C₀

C₁

C₂

C₃

C₄

C₅

Aplicații: numărul de parantezări corecte, arbori binari, triangulări ale poligonului etc.

Șirul Perrin: Similar cu Lucas, dar cu alte condiții inițiale.

P₀ = 3, P₁ = 0, P₂ = 2
Pₙ = Pₙ₋₂ + Pₙ₋₃ pentru n ≥ 3

P₀

P₁

P₂

P₃

P₄

P₅

Șirul Pell: O altă variantă de șir recurent.

P₀ = 0, P₁ = 1
Pₙ = 2Pₙ₋₁ + Pₙ₋₂ pentru n ≥ 2

P₀

P₁

P₂

P₃

P₄

P₅

Capcane comune și soluții pentru șiruri recurente

Greșeli frecvente la lucrul cu șiruri recurente:

❌ Depășire de tip de date (overflow)

// GREȘIT pentru n>12
int factorial(int n) {
    int fact = 1;
    for (int i = 1; i <= n; i++) {
        fact = fact * i;  // overflow pentru n>12
    }
    return fact;
}

// CORECT - folosește long long (până la n=20)
long long factorialLL(int n) {
    long long fact = 1;
    for (int i = 1; i <= n; i++) {
        fact = fact * i;
    }
    return fact;
}

❌ Recursivitate infinită (lipsă caz de bază)

// GREȘIT - fără condiție de oprire
int factorialBad(int n) {
    return n * factorialBad(n-1);  // se apelează la infinit
}

// CORECT - cu caz de bază
int factorialOk(int n) {
    if (n <= 1) return 1;
    return n * factorialOk(n-1);
}

❌ Complexitate exponențială în recursivitate

Calculul recursiv al lui Fibonacci fără memoizare are complexitate O(2ⁿ).

// GREȘIT - ineficient (exponențial)
int fibBad(int n) {
    if (n <= 1) return n;
    return fibBad(n-1) + fibBad(n-2);
}

// CORECT - cu memoizare (O(n))
int fibMemo(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
}

Best Practices pentru șiruri recurente:

✅ Folosește tipuri de date corespunzătoare - long long pentru factorial până la 20

✅ Implementează iterativ când este posibil - mai eficient decât recursiv

✅ Folosește memoizare pentru recursivitate - evită recalcularea

✅ Verifică întotdeauna condițiile inițiale - 0!, F₀, L₀, etc.

✅ Testează cu valori mici înainte - 0, 1, valori negative

Încălzire (2 minute)

Test rapid - șiruri recurente: Completează următoarele valori:

4! = verifică
L₃ (Lucas) = verifică
T₄ (Tribonacci) = verifică

Hint: 4! = 24, Șirul Lucas: 2,1,3,4..., Tribonacci: 0,0,1,1,2...

PROBLEME PBINFO - 15 minute

PbInfo #1159 - Factorial

Enunț:

Cerință: Să se calculeze n! (factorialul lui n).

Date de intrare:

Programul citește de la tastatură numărul n, 0 ≤ n ≤ 20.

Date de ieșire:

Programul va afișa pe ecran valoarea lui n!.

Exemplu:

Intrare:

Ieșire:

Explicație: 5! = 1 × 2 × 3 × 4 × 5 = 120

Cum gândim soluția:

Citim numărul n
Dacă n este 0 sau 1, factorialul este 1
Altfel, calculăm produsul numerelor de la 1 la n
Afișăm rezultatul

Execuție pentru n=5:

fact=1Valoare inițială

i=2fact = 1×2 = 2

i=3fact = 2×3 = 6

i=4fact = 6×4 = 24

i=5fact = 24×5 = 120 ✓

Ce trebuie să verifici mereu?

n poate fi 0 (0! = 1)
Folosește long long pentru rezultat
Verifică că n este între 0 și 20

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

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

    long long fact = 1;

    for (int i = 2; i <= n; i++) {
        fact *= i;
    }

    cout << fact;
    return 0;
}

Varianta cu verificare:

#include <iostream>
using namespace std;

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

    if (n < 0 || n > 20) {
        cout << "n trebuie sa fie intre 0 si 20";
        return 0;
    }

    long long fact = 1;
    for (int i = 1; i <= n; i++) fact *= i;

    cout << fact;
    return 0;
}

Ce învățăm din această problemă:

Tip de date corect: long long
Caz special: 0! = 1
Iterativ: rapid și sigur

PbInfo #1160 - Șirul lui Lucas

Problemă care calculează al n-lea termen al șirului Lucas

Enunț:

Cerință: Se citește un număr n. Să se afișeze al n-lea termen al șirului Lucas.

Date de intrare:

Programul citește de la tastatură numărul n, 0 ≤ n ≤ 45.

Date de ieșire:

Programul va afișa pe ecran al n-lea termen al șirului Lucas.

Exemplu:

Intrare:

Ieșire:

Explicație: L₅ = 11 (șirul: 2, 1, 3, 4, 7, 11...)

Cum gândim soluția:

Citim n
Tratezi separat n=0 și n=1
Pentru n ≥ 2, iterezi cu 2 variabile (L0, L1)
Afișezi Ln

Cum funcționează pentru n=5:

InițialL0=2, L1=1

i=2Ln=3 → L0=1, L1=3

i=3Ln=4 → L0=3, L1=4

i=4Ln=7 → L0=4, L1=7

i=5Ln=11 → L0=7, L1=11

REZULTATL₅ = 11 ✓

De ce metoda iterativă și nu recursivă?

Pentru n mare (până la 45), recursivitatea ar fi ineficientă. Metoda iterativă este O(n).

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

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

    if (n == 0) { cout << 2; return 0; }
    if (n == 1) { cout << 1; return 0; }

    long long L0 = 2, L1 = 1, Ln = 0;

    for (int i = 2; i <= n; i++) {
        Ln = L0 + L1;
        L0 = L1;
        L1 = Ln;
    }

    cout << Ln;
    return 0;
}

Varianta cu vector:

#include <iostream>
using namespace std;

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

    long long L[50];
    L[0] = 2;
    L[1] = 1;

    for (int i = 2; i <= n; i++) {
        L[i] = L[i-1] + L[i-2];
    }

    cout << L[n];
    return 0;
}

Ce învățăm:

Lucas: L₀=2, L₁=1
Iterativ: eficient
Cazuri speciale: n=0, n=1

EXERCIȚII PRACTICE - 10 minute

Exercițiul Practic: Diverse șiruri recurente

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida cunoștințele despre șiruri recurente

Sarcina 1: Comparație factorial iterativ vs recursiv

Scrie un program care:

Citește un număr n (0 ≤ n ≤ 10)
Calculează n! folosind ambele metode (iterativ și recursiv)
Afișează ambele rezultate și verifică dacă sunt egale

Scrie codul complet al programului:

Soluție pentru Sarcina 1:

#include <iostream>
using namespace std;

// Factorial iterativ
long long factorialIterativ(int n) {
    long long fact = 1;
    for (int i = 2; i <= n; i++) fact *= i;
    return fact;
}

// Factorial recursiv
long long factorialRecursiv(int n) {
    if (n <= 1) return 1;
    return n * factorialRecursiv(n - 1);
}

int main() {
    int n;
    cout << "Introduceți n (0-10): ";
    cin >> n;

    if (n < 0 || n > 10) {
        cout << "n trebuie să fie între 0 și 10";
        return 0;
    }

    long long factIterativ = factorialIterativ(n);
    long long factRecursiv = factorialRecursiv(n);

    cout << n << "! calculat iterativ: " << factIterativ << endl;
    cout << n << "! calculat recursiv: " << factRecursiv << endl;

    if (factIterativ == factRecursiv) cout << "✓ Cele două metode dau același rezultat!" << endl;
    else cout << "✗ Există o eroare în implementare!" << endl;

    cout << "\nPrimele " << n+1 << " factoriale: ";
    for (int i = 0; i <= n; i++) cout << factorialIterativ(i) << " ";

    return 0;
}

Observații:

n=0 → 0!=1
Iterativ = mai rapid, recursiv = mai „elegant”
Test recomandat: n=5 → 120

Sarcina 2: Generare comparativă Fibonacci vs Lucas

Cerință: Scrie un program care:

Citește un număr n (n ≤ 20)
Generează și afișează primele n termeni pentru ambele șiruri
Calculează și afișează diferența dintre termenii corespunzători
Verifică relația: Lₙ = Fₙ₋₁ + Fₙ₊₁ pentru fiecare n ≥ 1

Cod C++ complet:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "Introduceți n (max 20): ";
    cin >> n;

    if (n <= 0 || n > 20) {
        cout << "n trebuie să fie între 1 și 20!";
        return 0;
    }

    long long F[25];
    long long L[25];

    F[0] = 0; F[1] = 1;
    L[0] = 2; L[1] = 1;

    // Generare până la n și încă un pic (pentru F[i+1])
    int lim = (n + 2 < 25) ? (n + 2) : 24;
    for (int i = 2; i < lim; i++) {
        F[i] = F[i-1] + F[i-2];
        L[i] = L[i-1] + L[i-2];
    }

    cout << "\nComparație Fibonacci vs Lucas:\n";
    cout << "i\tF[i]\t\tL[i]\t\tL[i]-F[i]\tVerificare L_i = F_{i-1}+F_{i+1}\n";
    cout << "--------------------------------------------------------------------------------\n";

    for (int i = 0; i < n; i++) {
        long long dif = L[i] - F[i];

        cout << i << "\t" << F[i] << "\t\t" << L[i] << "\t\t" << dif << "\t\t";

        if (i >= 1) {
            long long suma = F[i-1] + F[i+1];
            cout << ((L[i] == suma) ? "✓" : "✗");
        } else {
            cout << "-";
        }

        cout << endl;
    }

    // Exemplu explicit
    if (n > 5) {
        cout << "\nDemonstrație pentru i=4:\n";
        cout << "L4 = " << L[4] << "\n";
        cout << "F3 + F5 = " << F[3] << " + " << F[5] << " = " << (F[3] + F[5]) << "\n";
    }

    return 0;
}

Ce învățăm:

Generare cu vectori
Relația Lucas–Fibonacci
Afișare tabelară clară

Ce vei învăța astăzi?

Șirul factorial - n!

Observații importante:

Analogii pentru factorial:

Farfurii în bufet

Persoane la coadă

Cărți pe raft

Piese de șah

Implementarea factorialului în C++

Execuție pentru n=5:

Șirul lui Lucas

Relația dintre Fibonacci și Lucas:

Exercițiu de completare - Factorial recursiv:

Completează funcția recursivă pentru calculul factorialului:

Bancă de cuvinte:

Test de înțelegere: Care este valoarea corectă?

Test rapid - șiruri recurente:

Alte șiruri recurente importante

Capcane comune și soluții pentru șiruri recurente

Greșeli frecvente la lucrul cu șiruri recurente:

Best Practices pentru șiruri recurente:

Încălzire (2 minute)

PbInfo #1159 - Factorial

Enunț:

Date de intrare:

Date de ieșire:

Exemplu:

Cum gândim soluția:

Execuție pentru n=5:

Ce trebuie să verifici mereu?

Scrie soluția în C++:

Soluție corectă:

Varianta cu verificare:

PbInfo #1160 - Șirul lui Lucas

Enunț:

Date de intrare:

Date de ieșire:

Exemplu:

Cum gândim soluția:

Cum funcționează pentru n=5:

De ce metoda iterativă și nu recursivă?

Scrie soluția în C++:

Soluție corectă:

Varianta cu vector:

Exercițiul Practic: Diverse șiruri recurente

Sarcini de lucru

Sarcina 1: Comparație factorial iterativ vs recursiv

Soluție pentru Sarcina 1:

Sarcina 2: Generare comparativă Fibonacci vs Lucas

Soluție pentru Sarcina 2:

Descarcă toate exercițiile și soluțiile