Ce vei învăța astăzi?
După această lecție vei înțelege ce este o recurență și vei putea genera primii n termeni ai șirului lui Fibonacci, dar și ai altor șiruri recurente.
Ce este o recurență?
Definiție: O recurență este o regulă prin care un termen al unui șir se calculează folosind termenii anteriori. Pentru a începe, avem nevoie de primii termeni (valorile de pornire).
Analogia cu scara
Este ca o scară: fiecare treaptă se sprijină pe treptele de sub ea. Nu poți urca treapta a 5-a fără să fi urcat treptele 3 și 4.
Șirul lui Fibonacci
Șirul lui Fibonacci este cel mai cunoscut șir recurent:
F1 = 1, F2 = 1, iar pentru n > 2: Fn = F(n-1) + F(n-2).
Fiecare termen este suma celor doi termeni dinaintea lui: 1, 1, 2, 3, 5, 8, 13, ...
Exemplu: primii n termeni Fibonacci
n = int(input())
a = 1
b = 1
for i in range(1, n + 1):
print(a, end=" ")
a, b = b, a + b
Observă: păstrăm doar ultimele două valori (a și b). La fiecare pas, noul termen este a + b, iar perechea avansează: a, b = b, a + b.
1
1
2
3
5
Aplicații în natură și proporția de aur
Șirul lui Fibonacci apare des în natură: în numărul de petale la multe flori, în spirala cochiliilor de melc sau în dispunerea semințelor la floarea-soarelui.
Raportul a două valori consecutive se apropie de proporția de aur, aproximativ 1,618, considerată estetică în artă și arhitectură.
| Exemplu | Legătura cu Fibonacci |
|---|---|
| Petalele florilor | Multe flori au 3, 5, 8, 13 petale (termeni Fibonacci) |
| Cochilia melcului | Spirala urmează rapoarte Fibonacci |
| Proporția de aur | Raportul Fn / F(n-1) tinde către 1,618 |
Șiruri recurente cu alte reguli
Recurențele nu sunt doar pentru Fibonacci. Orice regulă care folosește termenii anteriori definește un șir recurent.
Exemplu: a(n) = 2 * a(n-1), pornind de la a0 = 3, dă șirul 3, 6, 12, 24, ...
Exemplu: a(n) = 2 * a(n-1), a0 = 3
n = int(input())
a = 3
for i in range(1, n + 1):
print(a, end=" ")
a = 2 * a
Observă: aici fiecare termen depinde doar de unul anterior (a), nu de doi ca la Fibonacci.
Exercițiu de completare
Completează propozițiile despre șirul lui Fibonacci:
Șirul lui Fibonacci începe cu F1 = ______ și F2 = ______. Fiecare termen se calculează cu Fn = ______. Pentru a genera primii n termeni folosim o buclă ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - șiruri recurente:
1. Șirul Fibonacci: 1, 1, 2, 3, ... Următorul termen este:
2. F3 (al treilea termen Fibonacci) este:
3. O recurență definește un termen pe baza:
Test suplimentar - verifică ce ai reținut
Test rapid suplimentar - Fibonacci:
1. Relația de recurență a șirului lui Fibonacci este:
2. Șirul lui Fibonacci începe cu termenii:
3. Un șir recurent este definit cu ajutorul:
a = a + b pierde valoarea veche a lui a înainte de actualizare. Folosește actualizarea simultană (atribuirea ambelor variabile în aceeași instrucțiune, folosind vechile valori) a, b = b, a + b, pentru ca fiecare termen să se calculeze din valorile corecte.Aprofundare
Pentru șirul lui Fibonacci există și o formulă închisă, formula lui Binet, care calculează termenul F(n) direct, fără a genera termenii anteriori. Raportul dintre doi termeni consecutivi ai șirului tinde către proporția de aur, aproximativ 1,618, un număr care apare frecvent în artă, arhitectură și design.
- Memorie minimă: algoritmul folosește doar două variabile (a și b), indiferent cât de mare este n; memoria nu depinde de numărul de termeni.
- Creștere rapidă: termenii Fibonacci cresc foarte repede; F(30) depășește 1.300.000. În Python, numerele întregi nu au limită practică, deci programul rămâne corect chiar și pentru termeni uriași.
- Bucla while pentru „termeni mai mici decât x": când nu știm dinainte câți termeni afișăm, folosim o buclă
whilecu o condiție, exact ca la generarea termenilor Fibonacci mai mici decât o valoare dată. - Generalizarea: dacă primii doi termeni sunt a și b diferiți de 1, șirul rezultat este un Fibonacci generalizat; aceeași buclă
a, b = b, a + brămâne valabilă. - Recurența în altă formă: orice regulă de tipul
x(n) = x(n-1) + nsaux(n) = 2 * x(n-1)este tot o recurență; știm să o generăm cu aceeași tehnică: o variabilă actualizată în buclă.
PbInfo - Al n-lea termen Fibonacci
Enunț:
Cerință: Se citește numărul natural n. Să se afișeze al n-lea termen al șirului lui Fibonacci (F1 = 1, F2 = 1).
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa valoarea termenului Fn.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
7
Ieșire:
13
Cum gândim soluția:
- Citim n. Dacă n este 1 sau 2, răspunsul este 1
- Pornim cu a = 1, b = 1 și parcurgem i de la 3 la n
- La fiecare pas actualizăm: a, b = b, a + b
- La final, b este termenul căutat
Scrie soluția în Python:
Soluție corectă:
n = int(input())
if n <= 2:
print(1)
else:
a = 1
b = 1
for i in range(3, n + 1):
a, b = b, a + b
print(b)
Ce învățăm: scriem cod robust, tratând separat cazurile mici (n = 1, 2) și apoi actualizând perechea (a, b).
PbInfo - Primii n termeni Fibonacci
Enunț:
Cerință: Se citește numărul natural n. Să se afișeze pe o singură linie primii n termeni ai șirului lui Fibonacci, separați prin spații.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa primii n termeni ai șirului lui Fibonacci, separați prin spații.
Restricții și precizări:
n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.
Exemplu:
Intrare:
8
Ieșire:
1 1 2 3 5 8 13 21
Cum gândim soluția:
- Citim n și pornim cu a = 1, b = 1
- Parcurgem i de la 1 la n
- Afișăm a, apoi actualizăm: a, b = b, a + b
Scrie soluția în Python:
Soluție corectă:
n = int(input())
a = 1
b = 1
for i in range(1, n + 1):
print(a, end=" ")
a, b = b, a + b
Ce învățăm: generăm fiecare termen din perechea (a, b), afișând pe rând toți termenii șirului.
Exercițiul Practic: Șiruri recurente - Fibonacci
Sarcini de lucru
Aplică regula de recurență în programe complete, cu citire de la tastatură.
Sarcina 1: Termenii Fibonacci mai mici decât x
Cerință: Scrie un program care citește x și afișează toți termenii șirului Fibonacci mai mici sau egali cu x.
Soluție:
x = int(input())
a = 1
b = 1
while a <= x:
print(a, end=" ")
a, b = b, a + b
Verifică: pentru x = 20 se afișează 1 1 2 3 5 8 13. Bucla while se oprește când a depășește x.
Sarcina 2: Șirul a(n) = 2*a(n-1)
Cerință: Scrie un program care citește n și generează șirul recurent a(n) = 2 * a(n-1), pornind de la a0 = 3, afișând primii n termeni.
Soluție:
n = int(input())
a = 3
for i in range(1, n + 1):
print(a, end=" ")
a = 2 * a
Verifică: pentru n = 5 se afișează 3 6 12 24 48. Fiecare termen se obține înmulțind cu 2 pe cel anterior.