Ce vei învăța astăzi?
După această lecție vei scrie funcția recursivă pentru șirul lui Fibonacci (șirul de numere în care fiecare termen este suma celor doi anteriori: 0, 1, 1, 2, 3, 5, ...), vei înțelege deficiențele de eficiență ale acestei variante și vei compara cu varianta iterativă.
Șirul lui Fibonacci
Definiție: Șirul lui Fibonacci începe cu valorile fib(0) = 0 și fib(1) = 1. Pentru n ≥ 2, fib(n) = fib(n - 1) + fib(n - 2).
Primele valori: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| fib(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
Funcția recursivă Fibonacci în C++
#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;
cout << "n = ";
cin >> n;
cout << fib(n);
return 0;
}
Arborele apelurilor pentru fib(5)
Eficiența: de ce recursivitatea simplă e lentă?
Apeluri repetate
În varianta recursivă simplă, aceeași valoare fib(k) este calculată de mai multe ori. De exemplu, pentru fib(5), fib(3) se calculează de două ori, iar fib(2) de trei ori.
#include <iostream>
using namespace std;
int main()
{
int n;
long long a = 0, b = 1, c;
cin >> n;
if (n == 0)
cout << 0;
else
{
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
cout << b;
}
return 0;
}
Observă: varianta iterativă folosește doar trei variabile și calculează fiecare termen o singură dată, deci este mult mai eficientă pentru n mare.
Exercițiu de completare
Completează enunțul despre Fibonacci cu cuvintele potrivite:
Șirul lui Fibonacci începe cu valorile fib(0) = ______ și fib(1) = ______. Pentru n ≥ 2, fib(n) = fib(n - 1) + fib(n - ______). Varianta recursivă simplă are ______, deci este mai puțin ______ decât cea iterativă.
Bancă de cuvinte:
Exercițiu de completare
Completează funcția fib din codul C++:
Bancă de cuvinte:
Test de înțelegere
Test rapid - Fibonacci:
1. Valoarea fib(6) este:
2. Care este cazul de bază al șirului lui Fibonacci?
3. De ce varianta recursivă simplă a lui Fibonacci este lentă?
Aprofundare
Ineficiența exponențială. Varianta recursivă clasică recalculează de foarte multe ori aceleași valori: pentru fib(40) se efectuează peste un miliard de apeluri, deși rezultatul este doar 102.334.155. Numărul de apeluri crește exponențial (aproximativ 1,618^n), deci timpul de execuție devine inacceptabil chiar și pentru n moderat.
Memorizarea rezultatelor (memoizare). Stocând fiecare rezultat calculat într-un vector f[n] și verificând înainte de apel dacă valoarea este deja cunoscută, complexitatea scade la O(n). Aceasta este cea mai simplă optimizare a recursivității Fibonacci și un exemplu clasic de programare dinamică.
Varianta iterativă. Cu două variabile a și b actualizate într-o buclă for, se obține același rezultat în O(n), fără riscul umplerii stivei. Pentru n mare (peste 92), chiar și long long este depășit, iar Fibonacci poate fi reprezentat doar cu numere mari.
Raportul de aur. Raportul dintre doi termeni consecutivi ai șirului tinde către φ ≈ 1,618, cunoscut ca numărul de aur, prezent în natură (spiralele cochiliilor, aranjarea frunzelor) și în artă.
PbInfo - Fibonacci
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze al n-lea termen din șirul lui Fibonacci (cu fib(0) = 0, fib(1) = 1), folosind un subprogram recursiv.
Date de intrare:
Programul citește de la tastatură numărul natural n.
Date de ieșire:
Programul va afișa pe ecran valoarea fib(n).
Restricții și precizări:
0 ≤ n ≤ 30. Rezultatul încape într-un număr de tip long long.
Exemplu:
Intrare:
10
Ieșire:
55
Cum gândim soluția:
- Definim funcția
fib(n)care întoarcelong long - Cazurile de bază:
n == 0întoarce 0,n == 1întoarce 1 - Altfel întoarcem
fib(n - 1) + fib(n - 2) - În main citim n și afișăm
fib(n)
Scrie soluția în C++:
Soluție corectă:
#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;
}
Ce învățăm: funcția are două cazuri de bază, iar pasul recursiv împarte problema în două subprobleme mai mici.
PbInfo - Termenii șirului Fibonacci
Enunț:
Cerință: Se citește un număr natural n. Să se afișeze primii n termeni ai șirului lui Fibonacci (începând cu fib(0)), pe aceeași linie, 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 pe ecran primii n termeni ai șirului, separați prin spații.
Restricții și precizări:
1 ≤ n ≤ 20. Valorile încap într-un număr de tip long long.
Exemplu:
Intrare:
6
Ieșire:
0 1 1 2 3 5
Cum gândim soluția:
- Definim funcția recursivă
fib(n) - În main parcurgem cu o buclă de la 0 la n - 1
- Afișăm
fib(i)pentru fiecare i, separat prin spații
Scrie soluția în C++:
Soluție corectă:
#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;
for (int i = 0; i < n; i++)
cout << fib(i) << " ";
return 0;
}
Ce învățăm: apelăm funcția recursivă în interiorul unei bucle pentru a genera o secvență de termeni.
Exercițiul Practic: Fibonacci în practică
Sarcini de lucru
Rezolvă sarcinile următoare despre șirul lui Fibonacci
Sarcina 1: Suma termenilor Fibonacci
Cerință: Scrie un program C++ care calculează suma fib(0) + fib(1) + ... + fib(n), folosind funcția recursivă fib. Pentru n = 4, suma este 0 + 1 + 1 + 2 + 3 = 7.
Soluție pentru Sarcina 1:
#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;
long long s = 0;
cin >> n;
for (int i = 0; i <= n; i++)
s = s + fib(i);
cout << s;
return 0;
}
Verifică: pentru n = 4, suma este 7.
Sarcina 2: Compară variantele
Cerință: Explică, în câteva propoziții, de ce varianta iterativă a lui Fibonacci este preferabilă variantei recursive pentru n = 40, chiar dacă ambele dau același rezultat.
Soluție pentru Sarcina 2:
Varianta recursivă calculează aceleași valori de foarte multe ori: numărul de apeluri crește exponențial, deci pentru n = 40 devine extrem de lentă și umple stiva. Varianta iterativă folosește doar trei variabile și calculează fiecare termen o singură dată, deci rulează aproape instantaneu chiar și pentru n foarte mare.