Ce vei învăța astăzi?
După această lecție vei învăța să determini formula termenului general al unui șir recurent și să o folosești pentru a calcula direct orice termen, fără a genera toți termenii anteriori.
Ce este un șir recurent
Definiție: Un șir recurent este un șir în care fiecare termen se calculează din termenii anteriori, printr-o relație de recurență (relația matematică după care un termen se obține din valorile precedente), pornind de la una sau mai multe condiții inițiale (valorile de pornire ale șirului).
De exemplu, șirul definit prin a(0) = 3 și a(n) = 2 * a(n-1) are relația de recurență a(n) = 2 * a(n-1) și condiția inițială a(0) = 3.
De ce ne folosim?
Este ca un șir de temperaturi zilnice: temperatura de azi depinde de cea de ieri, care depinde de cea de alaltăieri. Fiecare valoare se obține din cea anterioară după o regulă simplă.
Se calculează din cea de ieri, după o regulă dată
Este punctul de plecare, de exemplu temperatura din prima zi
Formula termenului general
Pentru unele șiruri recurente putem găsi o formulă a termenului general: o expresie care calculează termenul a(n) direct, în funcție doar de n.
Pentru șirul a(0) = 3, a(n) = 2 * a(n-1) observăm că fiecare termen dublează precedentul, deci formula termenului general este a(n) = 3 * 2 ** n.
Exemplu: generarea primilor n termeni
n = int(input())
a = 3
for i in range(1, n + 1):
print(a, end=" ")
a = 2 * a
Observă: pentru n = 5 programul afișează 3 6 12 24 48. Fiecare termen se obține dublându-l pe cel anterior.
| n | Termen generat (buclă) | Termen din formula 3 * 2 ** n |
|---|---|---|
| 0 | 3 | 3 |
| 1 | 6 | 6 |
| 2 | 12 | 12 |
| 3 | 24 | 24 |
| 4 | 48 | 48 |
Reține: bucla generează termenii unul câte unul, iar formula calculează un termen direct. Când avem formula, nu mai e nevoie să trecem prin toți termenii anteriori.
Aplicație: dobânda bancară (procentul aplicat anual unei sume de bani)
Un șir recurent clasic din viața reală este creșterea unui sold bancar. După fiecare an, soldul se actualizează după regula sold = sold * (1 + dobanda / 100), unde dobanda este exprimată în procente.
Condiția inițială este suma depusă, iar relația de recurență transformă soldul de la un an la următorul.
Exemplu: după câți ani soldul depășește o valoare
s = float(input())
d = float(input())
t = float(input())
ani = 0
while s < t:
s = s * (1 + d / 100)
ani = ani + 1
print(ani)
Observă: nu știm dinainte câți ani sunt necesari, deci folosim o buclă while care rulează cât timp soldul nu a depășit valoarea țintă.
Exercițiu de completare
Completează definiția unui șir recurent:
Un șir recurent este definit printr-o relație de ______ și o ______ inițială. Fiecare termen depinde de termenii ______. Când numărul de termeni este cunoscut dinainte, folosim bucla ______.
Bancă de cuvinte:
Exercițiu de completare
Completează formula termenului general:
Pentru șirul cu a(0) = 3 și a(n) = 2 * a(n-1), formula termenului general este a(n) = 3 * 2 la puterea ______. În Python, puterea se scrie cu operatorul ______. La dobânda bancară, soldul nou se obține cu sold = sold * (1 + ______ / 100). Când nu știm câți ani sunt necesari, folosim bucla ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - șiruri recurente:
1. Care este termenul a(2) pentru șirul a(n) = 2 * a(n-1) cu a(0) = 3?
2. Formula termenului general pentru a(0) = 3, a(n) = 2 * a(n-1) se calculează în Python cu:
3. Actualizarea soldului bancar cu dobânda anuală d se face cu:
3 * 2 ** n cu 3 ** (2 * n): prima dublează de n ori, a doua ridică la o putere uriașă. Verifică întotdeauna formula pe primii termeni (n = 0, 1, 2).Aprofundare
Pentru unele șiruri recurente, formula termenului general se găsește ușor; pentru altele, formula este complicată sau nu există o formulă simplă. Șirul lui Fibonacci, de exemplu, are o formulă închisă (formula lui Binet), dar termenii cresc atât de repede încât generarea iterativă rămâne metoda practică preferată.
- Formule tipice: dacă a(n) = a(n-1) + r (adunare constantă), atunci a(n) = a(0) + n * r; dacă a(n) = q * a(n-1) (înmulțire constantă), atunci a(n) = a(0) * q ** n. Recunoașterea acestor tipuri îți permite să sari direct la formula termenului general.
- Precizia float: pentru n mari, calculul cu
floatpoate pierde precizie; în Python, puterea3 * 2 ** nlucrează cu numere întregi exacte, oricât de mari. - Când nu există formulă simplă: pentru multe recurențe (de exemplu Fibonacci), generarea pas cu pas este singura metodă sigură; formula lui Binet folosește radicali și aproximări, deci nu este potrivită pentru valori exacte mari.
- Verificarea formulei: orice formulă a termenului general trebuie verificată pe primii termeni: înlocuiește n = 0, 1, 2 și compară cu valorile obținute prin recurență.
- Dobânda compusă: după n ani, soldul este s * (1 + d/100) ** n - o formulă închisă pentru o recurență de înmulțire; pentru a afla „după câți ani depășim o țintă", inversăm problema și folosim while.
PbInfo - Al n-lea termen al șirului
Enunț:
Cerință: Se citește numărul natural n. Să se afișeze termenul a(n) al șirului definit prin a(0) = 3 și a(n) = 2 * a(n-1), folosind fie formula termenului general, fie generarea termenilor cu o buclă.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa pe ecran valoarea termenului a(n).
Restricții și precizări:
n este un număr natural, cu 0 <= n <= 30, iar termenii sunt numere întregi.
Exemplu:
Intrare:
4
Ieșire:
48
Cum gândim soluția:
- Citim n cu
input()și îl transformăm cuint() - Folosim formula termenului general: a(n) = 3 * 2 ** n
- Alternativ, generăm termenii cu o buclă pornind de la a = 3
- Afișăm rezultatul cu
print()
Scrie soluția în Python:
Soluție corectă:
n = int(input()) print(3 * 2 ** n)
Ce învățăm: formula termenului general calculează orice termen direct, fără buclă. Putem verifica: pentru n = 4 rezultă 3 * 16 = 48.
PbInfo - Dobânda bancară
Enunț:
Cerință: Se dau suma inițială s (în lei), dobânda anuală d (în procente) și valoarea țintă t. Să se afișeze după câți ani soldul depășește valoarea țintă, știind că la fiecare an soldul se actualizează cu sold = sold * (1 + d / 100).
Date de intrare:
Programul citește de la tastatură trei numere reale: s, d și t.
Date de ieșire:
Programul va afișa pe ecran numărul minim de ani după care soldul depășește valoarea țintă.
Restricții și precizări:
s, d și t sunt numere reale pozitive, cu s < t.
Exemplu:
Intrare:
1000 10 2000
Ieșire:
8
Cum gândim soluția:
- Citim s, d și t cu
float(input()) - Inițializăm contorul ani = 0
- Cât timp soldul este mai mic decât ținta, actualizăm soldul și creștem contorul
- Afișăm numărul de ani cu
print()
Scrie soluția în Python:
Soluție corectă:
s = float(input())
d = float(input())
t = float(input())
ani = 0
while s < t:
s = s * (1 + d / 100)
ani = ani + 1
print(ani)
Ce învățăm: folosim o buclă while pentru că numărul de ani nu este cunoscut dinainte - el depinde de momentul în care soldul depășește ținta.
Exercițiul Practic: Șiruri recurente
Sarcini de lucru
Aplică relațiile de recurență în programe complete, cu citire de la tastatură.
Sarcina 1: Șirul x(n) = x(n-1) + n
Cerință: Scrie un program care citește n și afișează primii n termeni ai șirului definit prin x(1) = 1 și x(n) = x(n-1) + n.
Soluție:
n = int(input())
x = 1
print(x, end=" ")
for i in range(2, n + 1):
x = x + i
print(x, end=" ")
Verifică: pentru n = 5 se afișează 1 3 6 10 15. Fiecare termen adaugă poziția i la termenul anterior.
Sarcina 2: Șir Fibonacci generalizat
Cerință: Scrie un program care citește primii doi termeni a și b și numărul n, apoi afișează primii n termeni ai șirului în care fiecare termen este suma ultimilor doi termeni.
Soluție:
a = int(input())
b = int(input())
n = int(input())
print(a, end=" ")
print(b, end=" ")
for i in range(3, n + 1):
c = a + b
print(c, end=" ")
a = b
b = c
Verifică: pentru a = 1, b = 1 și n = 7 se afișează 1 1 2 3 5 8 13, adică șirul clasic Fibonacci.