Ce vei învăța astăzi?
După această lecție, vei înțelege șirurile recurente și vei ști să generezi corect șirul lui Fibonacci în C++ (varianta iterativă) + vei ști să verifici răspunsul.
1) Ce este un șir recurent?
Definiție: Un șir recurent este un șir de numere în care fiecare termen se calculează folosind termenii de dinainte.
De ce e util? Pentru că unele reguli sunt ușor de scris matematic și ușor de implementat în program.
Analogie simplă:
Imaginează-ți că ai un joc în care primești puncte astfel: punctele de azi = punctele de ieri + punctele de alaltăieri. Ca să știi punctele de azi, trebuie să știi ultimele două zile.
Important: În algoritmi, recurența aproape întotdeauna se calculează iterativ (cu for), nu recursiv, pentru viteză și siguranță.
2) Definiția șirului lui Fibonacci
Ce înseamnă „n” la Fibonacci? (asta îi încurcă pe mulți)
În problemele cu Fibonacci există două formulări care par asemănătoare, dar sunt diferite:
- „Afișează primii n termeni” → afișezi
F(0), F(1), ..., F(n-1)(n valori). - „Calculează F(n)” → afișezi un singur număr: termenul de index n.
| Enunț | Ce afișezi | Exemplu (n=7) |
|---|---|---|
| „Primii n termeni” | n numere: F(0)..F(n-1) |
0 1 1 2 3 5 8 |
| „F(n)” | un singur număr: F(7) |
13 |
În lecția asta, când citim n, îl tratăm ca număr de termeni
(deci bucla corectă este i < n, nu i <= n).
Șirul lui Fibonacci este cel mai cunoscut șir recurent:
- 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...
În această lecție: când citim n, n înseamnă numărul de termeni afișați: F(0), F(1), ..., F(n-1).
Observă regula:
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
Capcană: Unele manuale folosesc F(1)=1, F(2)=1 (încep de la 1). Noi folosim F(0), F(1) pentru că așa e natural în programare (index de la 0).
3) Cum generăm Fibonacci? (Taburi: idee, iterativ, recursiv, greșeli)
Observație: Ca să calculezi următorul termen, ai nevoie doar de ultimele 2 valori.
De aceea, nu e obligatoriu să memorăm tot șirul într-un vector.
Analogie:
E ca și cum ai merge pe bicicletă și vrei să știi viteza acum. Nu ai nevoie de toate vitezele din trecut, ci doar de ultimele două măsurători dacă regula le folosește.
Variabilele pe care le folosim:
a = F(i-2), b = F(i-1), c = F(i)#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 0) return 0;
if (n == 1) {
cout << 0;
return 0;
}
if (n == 2) {
cout << 0 << " " << 1;
return 0;
}
long long a = 0, b = 1; // folosim long long ca sa nu "spargem" repede
cout << a << " " << b << " ";
for (int i = 2; i < n; i++) {
long long c = a + b;
cout << c << " ";
a = b;
b = c;
}
return 0;
}
De ce e bună varianta asta?
- Este rapidă: O(n)
- Folosește memorie mică: doar 3 variabile
- Este acceptată la problemele clasice (PbInfo / olimpiadă)
Recursiv înseamnă că o funcție se apelează pe ea însăși.
Formula Fibonacci arată recursiv: F(n) = F(n-1) + F(n-2). Dar implementarea recursivă naivă e lentă.
#include <iostream>
using namespace std;
long long fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
int main() {
int n;
cin >> n;
cout << fib(n);
return 0;
}
De ce e lent? Pentru că recalculează aceleași valori de multe ori.
Exemplu: ca să calculeze F(40), apelează F(39) și F(38). Dar ca să calculeze F(39), calculează iar F(38) etc. Se repetă masiv.
Concluzie: Pentru școală și concursuri, folosește varianta iterativă.
Capcane tipice când lucrezi cu Fibonacci:
- n mic (n=1, n=2) – trebuie tratat separat
- limite buclă (i < n) vs (i <= n)
- overflow – numerele cresc repede
Greșeli frecvente:
// GREȘIT (afișează n+1 termeni)
for (int i = 2; i <= n; i++) {
c = a + b;
cout << c << " ";
a = b;
b = c;
}
Corect: i < n dacă vrem exact n termeni (0..n-1).
F(47) nu încape în int (se strică valoarea). Folosește long long.
De reținut: Dacă vezi numere negative la Fibonacci, aproape sigur ai overflow.
În programare, e mai clar să începem cu F(0)=0, F(1)=1.
Aici ai traducerea „curată”: întâi pseudocod (pașii), apoi cod C++. Include și cele două cerințe diferite: primii n termeni și F(n).
int n;
cin >> n;
if (n <= 0) return 0;
if (n == 1) { cout << 0; return 0; }
if (n == 2) { cout << 0 << " " << 1; return 0; }
long long a = 0, b = 1;
cout << a << " " << b << " ";
for (int i = 2; i < n; i++) {
long long c = a + b;
cout << c << " ";
a = b;
b = c;
}
int n;
cin >> n;
if (n == 0) { cout << 0; return 0; }
if (n == 1) { cout << 1; return 0; }
long long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long long c = a + b;
a = b;
b = c;
}
cout << b;
int n;
cin >> n;
if (n <= 0) return 0;
long long fib[1000]; // pentru lecție; la concurs e bine să alegi limita din enunț
fib[0] = 0;
if (n > 1) fib[1] = 1;
for (int i = 2; i < n; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
for (int i = 0; i < n; i++) cout << fib[i] << " ";
Varianta cu 2 variabile este suficientă dacă doar afișezi / verifici. Varianta cu vector e utilă dacă ai întrebări de tip „câte valori Fibonacci sunt pare”, „găsește un termen anume”, „folosește termenii ulterior”.
Demo interactiv: generează Fibonacci pe ecran
Scrie n (câți termeni) și apasă „Generează”. Apoi poți apăsa „Pas cu pas” ca să vezi cum se schimbă a, b, c.
Hint: La „Pas cu pas”, vezi exact cum: c = a + b, apoi a ← b, b ← c.
4) Exercițiu de completare: Fibonacci iterativ
Completează codul C++ pentru a afișa primii n termeni Fibonacci:
Bancă de cuvinte:
Tip: Pentru n=2, acum avem și varianta „clară” (ramura dedicată), ca să fie mai ușor de reținut.
5) Test rapid: Fibonacci (quiz)
Răspunde la întrebări:
Q1. Dacă avem: 0, 1, 1, 2, 3, 5, 8... atunci F(7) este:
Q2. În algoritmul iterativ, după ce calculăm c = a + b, ce facem?
Q3. Dacă vrem exact n termeni, bucla corectă este:
Încălzire (2 minute)
Completează mental:
- F(0)=0, F(1)=1, F(2)=? → verifică
- F(5)=5, F(6)=8, F(7)=? → verifică
- Dacă a=13 și b=21, atunci c=a+b=? → verifică
Hint: fiecare termen = suma ultimelor două.
PbInfo - Fibonacci (primii n termeni)
Generează și afișează primii n termeni Fibonacci
Enunț:
Cerință: Se citește un număr n. Afișați primii n termeni ai șirului Fibonacci (începând de la F(0)).
Date de intrare:
Un număr natural n.
Date de ieșire:
Primii n termeni Fibonacci separați prin spații.
Exemplu:
Intrare:
7
Ieșire:
0 1 1 2 3 5 8
Cum gândim soluția:
- Tratezi cazurile mici: n=1 → afișezi 0, n=2 → afișezi 0 1
- Inițializezi a=0, b=1 și afișezi
- Buclă de la i=2 până la i<n:
- c=a+b
- afișezi c
- a=b; b=c
Execuție pentru n=6:
0 1 1 2 3 5Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 0) return 0;
if (n == 1) {
cout << 0;
return 0;
}
if (n == 2) {
cout << 0 << " " << 1;
return 0;
}
long long a = 0, b = 1;
cout << a << " " << b << " ";
for (int i = 2; i < n; i++) {
long long c = a + b;
cout << c << " ";
a = b;
b = c;
}
return 0;
}
Ce învățăm:
- Caz special n=1 și n=2
- Buclă cu limită i<n pentru exact n termeni
- Actualizare corectă a și b
- Folosim long long pentru siguranță
PbInfo - Verifică dacă x este Fibonacci
Problema tipică: „x aparține șirului Fibonacci?”
Enunț:
Cerință: Se citește un număr natural x. Să se afișeze DA dacă x este un număr Fibonacci, altfel NU.
Date de intrare:
Un număr natural x.
Date de ieșire:
DA sau NU.
Exemple:
Intrare:
21
Ieșire:
DA
Intrare:
22
Ieșire:
NU
Cum gândim soluția:
- Generăm Fibonacci în ordine crescătoare: 0,1,1,2,3...
- Ne oprim când termenul curent depășește x
- Dacă exact egal cu x → DA, altfel NU
Observație: Asta e o strategie de tip „căutare liniară” într-un șir generat. E ușoară și suficientă pentru valori normale de x.
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
long long x;
cin >> x;
if (x < 0) {
cout << "NU";
return 0;
}
long long a = 0, b = 1;
// x poate fi 0 sau 1
if (x == 0 || x == 1) {
cout << "DA";
return 0;
}
while (b < x) {
long long c = a + b;
a = b;
b = c;
}
if (b == x) cout << "DA";
else cout << "NU";
return 0;
}
Ce învățăm:
- Generare Fibonacci până la o limită
- Oprire când depășește x
- Verificare finală b==x
- Tratăm cazuri mici: x=0 sau x=1
Exercițiu practic: Fibonacci în viața reală (și în cod)
Sarcini de lucru
Consolidează: generare, paritate, limită, verificare, afișare corectă.
Sarcina 1: Completează analiza
Cerință: Pentru n=8, scrie șirul Fibonacci și arată cum se calculează ultimele 3 valori.
Soluție pentru Sarcina 1:
- Pentru n=8: 0 1 1 2 3 5 8 13
- Ultimele 3 calcule:
- F(5)=F(4)+F(3)=3+2=5
- F(6)=F(5)+F(4)=5+3=8
- F(7)=F(6)+F(5)=8+5=13
Sarcina 2: Program complet
Cerință: Citește n și afișează:
- Primii n termeni Fibonacci
- Câți dintre ei sunt pari
- Ultimul termen afișat (F(n-1))
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
if (n <= 0) return 0;
long long a = 0, b = 1;
int cntPar = 0;
if (n == 1) {
cout << "Sir: " << 0 << "\n";
cout << "Pare: " << 1 << "\n";
cout << "Ultimul: " << 0 << "\n";
return 0;
}
// Afisam primii doi
cout << "Sir: " << a << " " << b << " ";
if (a % 2 == 0) cntPar++;
if (b % 2 == 0) cntPar++;
long long last = b;
for (int i = 2; i < n; i++) {
long long c = a + b;
cout << c << " ";
if (c % 2 == 0) cntPar++;
a = b;
b = c;
last = c;
}
cout << "\nPare: " << cntPar << "\n";
cout << "Ultimul: " << last << "\n";
return 0;
}
Observație: Am adăugat mesaje („Sir:”, „Pare:”, „Ultimul:”) ca să fie clar la verificare. La PbInfo, de obicei se cere doar șirul.