lectiipenet.ro

Șirul lui Fibonacci și Sume cu Termen General Dat

Written by

admin

in

Bun, hai să vorbim despre unul dintre cele mai fascinante și utile șiruri din matematică și programare: ȘIRUL LUI FIBONACCI. Nu e doar despre numere (cuvânt rece) și secvențe. E despre o relație de recurență care apare peste tot în natură: la cochilii de melc, la așezarea frunzelor, la proporțiile corpului uman. Și apoi vom vorbi despre cum calculăm sume atunci când știm formula termenului general.

1. Ce este Șirul lui Fibonacci? “Suma Celor Doi Anteriori”

Definiție: Fiecare termen este suma celor doi termeni anteriori.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)  pentru n ≥ 2

Primii termeni:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Analogie cu Iepuri:

Luna 1: 1 pereche de iepuri (tineri)
Luna 2: încă 1 pereche (tineri devin adulți)
Luna 3: 2 perechi (adulții fac pui)
Luna 4: 3 perechi (și așa mai departe)

2. Calcul Fibonacci – Metoda Iterativă (cea mai bună!)

#include <iostream>
using namespace std;

int main() {
    int n = 10;  // Al câtelea termen vrem

    if(n == 0) {
        cout << "F(0) = 0" << endl;
        return 0;
    }
    if(n == 1) {
        cout << "F(1) = 1" << endl;
        return 0;
    }

    int a = 0;  // F(n-2)
    int b = 1;  // F(n-1)
    int c;      // F(n)

    cout << "F(0) = 0" << endl;
    cout << "F(1) = 1" << endl;

    for(int i = 2; i <= n; i++) {
        c = a + b;      // Termenul curent
        cout << "F(" << i << ") = " << c << endl;

        // Pregătim următorul pas
        a = b;
        b = c;
    }

    return 0;
}

3. Calcul Fibonacci – Metoda Recursivă (simplă dar ineficientă)

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;

    return fibonacci(n-1) + fibonacci(n-2);
}

int main() {
    int n = 10;
    cout << "F(" << n << ") = " << fibonacci(n) << endl;
    return 0;
}

Problemă cu recursivitatea: Calculează aceleași valori de multe ori!
Pentru F(5) calculează:

  • F(5) = F(4) + F(3)
  • F(4) = F(3) + F(2)
  • F(3) = F(2) + F(1)
  • F(2) = F(1) + F(0)

4. Fibonacci cu Memoizare (optimizat)

#include <iostream>
using namespace std;

int fib[100];  // Memorie pentru rezultate calculate

int fibonacciMemo(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;

    if(fib[n] != 0) {  // Dacă l-am calculat deja
        return fib[n];
    }

    fib[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2);
    return fib[n];
}

int main() {
    // Inițializează memoria cu 0
    for(int i = 0; i < 100; i++) {
        fib[i] = 0;
    }

    int n = 10;
    cout << "F(" << n << ") = " << fibonacciMemo(n) << endl;
    return 0;
}

5. Proprietăți interesante ale șirului Fibonacci

5.1 Suma primilor n termeni

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int suma = 0;

    int a = 0, b = 1;

    if(n >= 1) suma += a;  // F(0)
    if(n >= 2) suma += b;  // F(1)

    for(int i = 2; i <= n; i++) {
        int c = a + b;
        suma += c;
        a = b;
        b = c;
    }

    cout << "Suma primilor " << n+1 << " termeni Fibonacci: " << suma << endl;
    cout << "Formula: F(n+2) - 1 = " << (b - 1) << endl;  // b = F(n+1)

    return 0;
}

5.2 Numerele Fibonacci pare

#include <iostream>
using namespace std;

int main() {
    cout << "Numerele Fibonacci pare pana la 100:\n";

    int a = 0, b = 1;

    while(a <= 100) {
        if(a % 2 == 0) {
            cout << a << " ";
        }

        int c = a + b;
        a = b;
        b = c;
    }

    return 0;
}

6. Sume cu Termen General Dat

Când avem o formulă pentru termenul general, putem calcula sume eficient.

Exemplu 1: Suma pătratelor primelor n numere
Termen general: aₖ = k²
Suma: S = 1² + 2² + 3² + … + n²

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int suma = 0;

    // Metoda 1: Adună direct
    for(int k = 1; k <= n; k++) {
        suma += k * k;
    }
    cout << "Suma patratelor: " << suma << endl;

    // Metoda 2: Folosește formula
    // S = n(n+1)(2n+1)/6
    int sumaFormula = n * (n + 1) * (2*n + 1) / 6;
    cout << "Cu formula: " << sumaFormula << endl;

    return 0;
}

Exemplu 2: Suma cuburilor
Termen general: aₖ = k³
Formula: S = [n(n+1)/2]²

#include <iostream>
using namespace std;

int main() {
    int n = 10;

    // Cu buclă
    int sumaBucla = 0;
    for(int k = 1; k <= n; k++) {
        sumaBucla += k * k * k;
    }

    // Cu formula
    int sumaFormula = (n * (n + 1) / 2);
    sumaFormula = sumaFormula * sumaFormula;

    cout << "Suma cuburilor:\n";
    cout << "Cu bucla: " << sumaBucla << endl;
    cout << "Cu formula: " << sumaFormula << endl;

    return 0;
}

Exemplu 3: Suma puterilor lui 2
Termen general: aₖ = 2ᵏ
Suma: S = 2ⁿ⁺¹ – 2

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int suma = 0;
    int putere = 1;

    for(int k = 1; k <= n; k++) {
        putere *= 2;  // 2ᵏ
        suma += putere;
    }

    cout << "Suma: " << suma << endl;
    cout << "Cu formula 2^(n+1)-2: " << ( (1 << (n+1)) - 2 ) << endl;

    return 0;
}

7. Progresii Aritmetice și Geometrice

7.1 Progresie Aritmetică (PA)
Termen general: aₖ = a₁ + (k-1) * r
Suma: S = n(a₁ + aₙ)/2

#include <iostream>
using namespace std;

int main() {
    int a1 = 3;  // Primul termen
    int r = 2;   // Rația
    int n = 10;  // Număr de termeni

    // Calcul cu buclă
    int suma = 0;
    int termen = a1;

    for(int i = 0; i < n; i++) {
        suma += termen;
        termen += r;  // Următorul termen
    }

    // Calcul cu formula
    int an = a1 + (n-1) * r;  // Ultimul termen
    int sumaFormula = n * (a1 + an) / 2;

    cout << "Suma PA: " << suma << " = " << sumaFormula << endl;

    return 0;
}

7.2 Progresie Geometrică (PG)
Termen general: aₖ = a₁ × rᵏ⁻¹
Suma: S = a₁(1 – rⁿ)/(1 – r) pentru r ≠ 1

#include <iostream>
using namespace std;

int main() {
    int a1 = 2;  // Primul termen
    int r = 3;   // Rația
    int n = 5;   // Număr de termeni

    // Calcul cu buclă
    int suma = 0;
    int termen = a1;

    for(int i = 0; i < n; i++) {
        suma += termen;
        termen *= r;  // Următorul termen
    }

    // Calcul cu formula
    int sumaFormula;
    if(r == 1) {
        sumaFormula = n * a1;
    } else {
        // a₁(1 - rⁿ)/(1 - r)
        int rn = 1;
        for(int i = 0; i < n; i++) {
            rn *= r;
        }
        sumaFormula = a1 * (1 - rn) / (1 - r);
    }

    cout << "Suma PG: " << suma << " = " << sumaFormula << endl;

    return 0;
}

8. Aplicații Practice cu Fibonacci

Aplicația 1: Verifică dacă un număr e Fibonacci

#include <iostream>
using namespace std;

int main() {
    int numar = 34;
    bool esteFibonacci = false;

    int a = 0, b = 1;

    while(a <= numar) {
        if(a == numar) {
            esteFibonacci = true;
            break;
        }

        int c = a + b;
        a = b;
        b = c;
    }

    if(esteFibonacci) {
        cout << numar << " este numar Fibonacci!" << endl;
    } else {
        cout << numar << " NU este numar Fibonacci!" << endl;
    }

    return 0;
}

Aplicația 2: Raportul a doi termeni Fibonacci consecutivi
Tinde către φ (phi) = (1+√5)/2 ≈ 1.618 (numărul de aur)

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

int main() {
    cout << fixed << setprecision(10);

    int a = 0, b = 1;

    cout << "Raportul F(n+1)/F(n) tinde catre phi (1.618...)\n\n";

    for(int i = 1; i <= 20; i++) {
        int c = a + b;

        if(a > 0) {  // Evită împărțirea la 0
            double raport = (double)b / a;
            cout << "F(" << i << ")/F(" << i-1 << ") = " 
                 << raport << endl;
        }

        a = b;
        b = c;
    }

    return 0;
}

Aplicația 3: Fibonacci pătrat – Proprietate interesantă
F(n) × F(n+1) ≈ F(n+1)² – F(n)²

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int a = 0, b = 1;

    for(int i = 0; i < n; i++) {
        int c = a + b;

        if(i >= 2) {
            int produs = a * b;
            int diferenta = b*b - a*a;

            cout << "F(" << i-1 << ")×F(" << i << ") = " << produs << endl;
            cout << "F(" << i << ")² - F(" << i-1 << ")² = " << diferenta << endl;
            cout << "Sunt " << (produs == diferenta ? "EGALE" : "DIFERITE") << "\n\n";
        }

        a = b;
        b = c;
    }

    return 0;
}

9. Exerciții Practice

Exercițiul 1: Completează codul pentru Fibonacci

int n = 8;
int f0 = 0, f1 = 1, fn;

if(n == 0) fn = f0;
else if(n == 1) fn = f1;
else {
    for(int i = 2; i <= n; i++) {
        fn = /* completează */;
        f0 = f1;
        f1 = /* completează */;
    }
}

cout << "F(" << n << ") = " << fn;

Soluție:

fn = f0 + f1;
f1 = fn;

Exercițiul 2: Calculează suma alternantă
S = F(1) – F(2) + F(3) – F(4) + … ± F(n)

#include <iostream>
using namespace std;

int main() {
    int n = 10;
    int suma = 0;
    int semn = 1;  // 1 pentru +, -1 pentru -

    int a = 0, b = 1;

    for(int i = 1; i <= n; i++) {
        suma += semn * b;
        semn = -semn;  // Schimbă semnul

        int c = a + b;
        a = b;
        b = c;
    }

    cout << "Suma alternanta: " << suma << endl;
    return 0;
}

Exercițiul 3: Numerele Fibonacci mai mici decât N

#include <iostream>
using namespace std;

int main() {
    int N = 100;

    cout << "Numere Fibonacci < " << N << ":\n";

    int a = 0, b = 1;

    while(a < N) {
        cout << a << " ";

        int c = a + b;
        a = b;
        b = c;
    }

    return 0;
}

În concluzie:

  • Fibonacci se calculează cel mai bine iterativ
  • Formulele pentru sume economisesc timp de calcul
  • Recurența F(n) = F(n-1) + F(n-2) e esența șirului

Reguli importante:

  1. Pentru Fibonacci, mereu începe cu F(0)=0, F(1)=1
  2. Varianta iterativă e mereu mai rapidă decât cea recursivă
  3. Când ai o formulă pentru termen general, folosește-o pentru sume!

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

More posts