Identifici recurența
Explici cum un termen poate fi obținut din termeni anteriori.
9.2. Generarea secvențelor recurente
Termeni obținuți din valori inițiale și termeni anteriori
INIȚIAL
→REGULĂ
→TERMEN
→REPETĂ
01
OBIECTIVE
La finalul lecției vei putea...
Generezi secvențe recurente
Construiești liste folosind valori inițiale și o relație de recurență.
Urmărești termenii
Simulezi evoluția variabilelor și verifici ordinea termenilor.
Testezi soluția
Alegi cazuri-limită și valori relevante pentru algoritmii de generare.
✓
Checkpoint
Ce este esențial pentru o secvență recurentă?
02
EXPLICAȚIE
Generarea termenilor prin recurență
Nu toate secvențele au o formulă simplă care exprimă direct fiecare termen. Uneori următorul termen se obține din unul sau mai mulți termeni calculați anterior. În acest caz folosim o relație de recurență.
Un exemplu simplu
Considerăm secvența 2, 5, 8, 11, ... . Primul termen este 2, iar fiecare termen următor se obține adăugând 3: a₁ = 2, aᵢ = aᵢ₋₁ + 3.
De ce memorăm termenul curent?
La generarea unui termen avem nevoie de informația calculată anterior. Variabila care păstrează termenul curent este actualizată după fiecare pas.
Recurență cu doi termeni anteriori
Șirul lui Fibonacci este un exemplu cunoscut: 1, 1, 2, 3, 5, 8, ..., unde fiecare termen, începând cu al treilea, este suma celor doi termeni anteriori.
✓
Checkpoint
De ce sunt necesare valorile inițiale într-o recurență?
03
EXEMPLU INTUITIV
Un aparat care produce următoarea valoare
Imaginează-ți un aparat care primește o valoare, aplică o regulă și produce următoarea valoare. Pentru 2, 5, 8, 11, ... aparatul „adaugă 3”. Rezultatul devine noua valoare de intrare pentru pasul următor.
Construiește recurența
2, 5, 8, 11, 14, 17
Observă mecanismul
Fiecare termen nou este termenul anterior + pasul.
04
PYTHON
Recurență cu un termen anterior
n = int(input())
a = 2
valori = []
for i in range(n):
valori.append(a)
a = a + 3
print(valori)Pentru n = 5, lista este [2, 5, 8, 11, 14]. Variabila a reprezintă termenul curent; după memorarea lui, îl actualizăm pentru următorul pas.
Fibonacci
n = int(input())
a = 1
b = 1
valori = []
for i in range(n):
valori.append(a)
c = a + b
a = b
b = c
print(valori)La fiecare pas, a devine termenul următor, iar b păstrează informația necesară pentru calculul următorului termen.
05
ALGORITM / PSEUDOCOD
Generarea unei recurențe
Recurență cu un termen anterior
citește n
a valoare inițială ←
valori []
pentru i 1,n execută
adaugă a la valori
a a + p ←
sfârșit pentru
scrie valoriRecurență cu doi termeni anteriori
citește n
a 1 ←
b 1 ←
valori []
pentru i 1,n execută
adaugă a la valori
c a + b ←
a b ←
b c ←
sfârșit pentru
scrie valori06
ATENȚIE!
Ordinea actualizărilor contează
Păstrează termenii înainte de actualizare
În Fibonacci, avem nevoie de vechile valori ale lui a și b pentru a calcula c.
Nu pierde informația
Dacă modifici a prea devreme, nu mai poți calcula corect următorul termen.
Numărul de termeni trebuie controlat
Pentru exact n termeni, bucla trebuie să se execute de n ori.
Testează primele valori
O eroare în valorile inițiale se propagă în toată secvența.
07
EXEMPLU REZOLVAT
Primele n numere Fibonacci
Problemă
Se citește n. Generați lista primelor n numere din secvența 1, 1, 2, 3, 5, 8, ....
Analiză
Intrare: n. Ieșire: lista termenilor. Idee: pornim cu a = 1 și b = 1. Memorăm a, apoi calculăm c = a + b și deplasăm perechea.
Algoritm
citește n
a 1; b 1
valori []
pentru i 1,n execută
adaugă a la valori
c a + b
a b
b c
sfârșit pentru
scrie valoriPython
n = int(input())
a = 1
b = 1
valori = []
for i in range(n):
valori.append(a)
c = a + b
a = b
b = c
print(valori)Urmărirea variabilelor pentru n = 6
| Pas | a memorat | b după actualizare | listă |
|---|---|---|---|
| 1 | 1 | 2 | [1] |
| 2 | 1 | 3 | [1, 1] |
| 3 | 2 | 5 | [1, 1, 2] |
| 4 | 3 | 8 | [1, 1, 2, 3] |
| 5 | 5 | 13 | [1, 1, 2, 3, 5] |
| 6 | 8 | 21 | [1, 1, 2, 3, 5, 8] |
Testare
| Test | Date | Rezultat așteptat |
|---|---|---|
| Caz-limită | n = 1 | [1] |
| Caz normal | n = 6 | [1, 1, 2, 3, 5, 8] |
| Valoare relevantă | n = 8 | [1, 1, 2, 3, 5, 8, 13, 21] |
Justificarea soluției: după fiecare pas,
a și b reprezintă doi termeni consecutivi, iar c = a + b produce exact următorul termen.08
EXERCIȚII DE BAZĂ
Aplică recurența
- Generați n termeni ai secvenței 2, 5, 8, 11, ... .
- Generați n termeni ai secvenței 10, 7, 4, 1, ... .
- Generați primele n numere Fibonacci.
- Se citesc primul termen, pasul și n. Generați n termeni ai secvenței obținute prin adăugarea repetată a pasului.
- Urmăriți valorile variabilelor pentru n = 5 în algoritmul Fibonacci.
09
EXERCIȚII DE APROFUNDARE
Combină recurența cu proprietăți ale termenilor
- Generați n termeni ai unei secvențe în care fiecare termen se obține adăugând 4 la precedentul și determinați suma lor.
- Generați primele n numere Fibonacci și determinați câte sunt pare.
- Generați termenii unei secvențe recurente până când termenul depășește o valoare dată, dacă regula este „adaugă p”.
- Comparați generarea unei progresii aritmetice prin formulă cu generarea prin recurență.
- Documentați, prin exemple, apariția șirului lui Fibonacci în natură, artă sau știință și precizați ce relație de recurență îl definește.
10
VERIFICARE
Quiz final
1. Ce este o relație de recurență?
2. Pentru 2,5,8,11,... care este pasul?
3. În Fibonacci, termenul următor este:
4. De ce folosim variabila c în exemplul Fibonacci?
5. Câte valori produce for i in range(n)?
6. Ce trebuie testat cu atenție la o recurență?
11
MINI-PROIECT
Generator de secvențe recurente
MISIUNE
Laboratorul secvențelor
Realizați o aplicație care permite alegerea unei secvențe definite prin recurență. Programul trebuie să pornească de la valorile inițiale, să genereze n termeni, să îi memoreze și să afișeze lista. Pentru o variantă, folosiți Fibonacci; pentru alta, o secvență cu pas constant.
Cerințe
valori inițiale01
relație de recurență02
n termeni03
listă generată04
urmărire și teste05
Ai terminat lecția?
Verifică primele termene și ordinea actualizării variabilelor.