Algoritmi Elementari – Generarea Șirurilor Recurente 12

---

1. Obiectivele lecției:

• Să înțeleagă conceptul de șir recurent.
• Să cunoască metodele de generare a șirurilor recurente.
• Să implementeze algoritmi pentru generarea șirurilor recurente în C++.
• Să aplice conceptele pentru a genera șiruri matematice precum Fibonacci sau alte șiruri personalizate.

---

2. Conținutul lecției:

Ce este un șir recurent?

• Definiție: Un șir recurent este o succesiune de termeni unde fiecare termen se bazează pe unul sau mai mulți termeni anteriori conform unei formule de recurență.
• Exemple comune:
  • Șirul Fibonacci: Fn=Fn−1+Fn−2,F0=0,F1=1F_n = F_{n-1} + F_{n-2}, F_0 = 0, F_1 = 1Fn​=Fn−1​+Fn−2​,F0​=0,F1​=1
  • Șirul aritmetic: an=an−1+da_n = a_{n-1} + dan​=an−1​+d
  • Șirul geometric: gn=gn−1⋅rg_n = g_{n-1} \cdot rgn​=gn−1​⋅r

---

3. Exemple de șiruri recurente și algoritmi:

---

Exemplu 1: Generarea șirului Fibonacci

• Formula de recurență: Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn​=Fn−1​+Fn−2​
• Cod în C++ (iterativ):

#include <iostream>

using namespace std;

int main() {

    int n;

    cout << „Introdu numarul de termeni din sirul Fibonacci: „;

    cin >> n;

    int f0 = 0, f1 = 1, fn;

    cout << „Sirul Fibonacci: „;

    cout << f0 << ” ” << f1 << ” „;

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

        fn = f0 + f1;

        cout << fn << ” „;

        f0 = f1;

        f1 = fn;

    }

    cout << endl;

    return 0;

}

• Cod în C++ (recursiv):

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

    cout << „Introdu numarul de termeni din sirul Fibonacci: „;

    cin >> n;

    cout << „Sirul Fibonacci: „;

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

        cout << fibonacci(i) << ” „;

    }

    cout << endl;

    return 0;

}

---

Exemplu 2: Generarea unui șir aritmetic

• Formula de recurență: an=an−1+da_n = a_{n-1} + dan​=an−1​+d
• Cod în C++:

#include <iostream>

using namespace std;

int main() {

    int a0, d, n;

    cout << „Introdu primul termen (a0): „;

    cin >> a0;

    cout << „Introdu diferenta (d): „;

    cin >> d;

    cout << „Introdu numarul de termeni: „;

    cin >> n;

    cout << „Sirul aritmetic: „;

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

        cout << a0 + i * d << ” „;

    }

    cout << endl;

    return 0;

}

---

Exemplu 3: Generarea unui șir geometric

• Formula de recurență:

g_n​=g_n−1*r

• Cod în C++:

#include <iostream>

#include <math.h>

using namespace std;

int main() {

    int g0, r, n;

    cout << „Introdu primul termen (g0): „;

    cin >> g0;

    cout << „Introdu rata (r): „;

    cin >> r;

    cout << „Introdu numarul de termeni: „;

    cin >> n;

    cout << „Sirul geometric: „;

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

        cout << g0 * pow(r, i) << ” „;

    }

    cout << endl;

    return 0;

}

---

Exemplu 4: Șir definit personalizat

• Formula:

T_n​=T_n−1​+2⋅T_n−2​

• Cod în C++:

#include <iostream>

using namespace std;

int main() {

    int t0 = 1, t1 = 2, tn, n;

    cout << „Introdu numarul de termeni: „;

    cin >> n;

    cout << „Sirul personalizat: „;

    cout << t0 << ” ” << t1 << ” „;

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

        tn = t1 + 2 * t0;

        cout << tn << ” „;

        t0 = t1;

        t1 = tn;

    }

    cout << endl;

    return 0;

}

---

4. Activități practice pentru elevi:

1. Scrieți un program care generează primii n termeni ai unui șir definit astfel:

2. Realizați un program care calculează suma primilor n termeni ai unui șir geometric.
3. Scrieți un program care verifică dacă un termen specificat aparține unui șir Fibonacci.

---

5. Scheme logice:

1. Șir Fibonacci (iterativ):

  Start:

Începe execuția algoritmului.

  Inițializează F₀,F₁​:

Setează valorile de început ale șirului: F₀=0și F₁=1.

  Pentru i=2 la n:

Iterează de la i=2 până la i=n, unde n este indicele termenului final al șirului Fibonacci.

  Calculează F_i=F_i−1+F_i−2​:

Fiecare termen F_i​ este suma termenilor anteriori F_i−1​ și F_i−2​.

  Actualizează valorile F_i−1​ și F_i−2​:

După calcularea lui F_i​, mută valorile astfel:

F_i−2←F_i−1​,

F_i−1←F_i.

Acest pas pregătește termenii pentru calculul următorului F_i​.

  Stop:

2. Șir aritmetic:

Start:

Începem execuția algoritmului.

Inițializează a0​ și d:

Alegem valoarea primului termen al progresiei (a0​) și rația (d).

Pentru i=0 la n:

Iterăm prin termenii progresiei, de la indicele i=0(primul termen) până la indicele i=n (al n-lea termen).

Nota: n este numărul total de termeni pe care vrem să-i calculăm (sau indicele ultimului termen).

Calculează a_i=a₀+i⋅d:

Fiecare termen al progresiei se calculează prin adăugarea la a0​ a produsului dintre i și rația d.

Stop:

---

6. Concluzie:

• Șirurile recurente sunt esențiale pentru înțelegerea matematicii și programării algoritmice.
• Implementarea acestor șiruri ajută la înțelegerea conceptelor de recurență și dependență între termeni.
• Prin practică, elevii pot învăța să modeleze probleme complexe utilizând șiruri recurente.