
Al N-lea termen Fibonacci în C++
Dându-se un număr natural n
, să se determine al n
-lea termen din șirul
Fibonacci.
Exemplu. Pentru n = 9
, F(n) = F(9) = 34
.
Ce este șirul Fibonacci?
Șirul Fibonacci, cunoscut după matematicianul Leonardo Bonacci, este șirul definit astfel:
- primii doi termeni ai șirului,
F(1)
șiF(2)
, sunt egali cu1
. - următorii termeni ai șirului sunt definiți după relația
F(n) = F(n - 1) + F(n - 2)
.
Curiozități despre șirul Fibonacci
- Primii termeni ai șirului sunt
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
. - Doar primii
46
de termeni încap înint
— așadar de regulă se lucrează cu variabile de tiplong long
.
Cum se determină al n
-lea termen Fibonacci (cu vector)
Vom crea un vector în care al i
-lea element reprezintă al i
-lea termen
Fibonacci. Vom genera acest vector până la n
.
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim variabilele
int n, fibo[51];
cin >> n;
//Generăm șirul
fibo[1] = fibo[2] = 1;
for(int i = 3; i <= n; i++) {
fibo[i] = fibo[i - 1] + fibo[i - 2];
}
//Afișăm al n-lea termen
cout << fibo[n];
return 0;
}
Cum se determină al n
-lea termen Fibonacci (recursiv)
Soluția recursivă este foarte ineficientă, deoarece se recalculează aceeași termeni de multe ori. Cu toate acestea, este un exemplu bun de a demonstra recursivitatea:
#include <iostream>
using namespace std;
int fibo(int n) {
if(n == 1 || n == 2) { //Cazuri particulare
return 1;
}
return fibo(n - 1) + fibo(n - 2);
}
int main()
{
//Declarăm și citim
int n;
cin >> n;
//Afișăm al n-lea termen
cout << fibo(n);
return 0;
}
De ce nu este eficientă această soluție?
Să analizăm grafic ce se întâmplă dacă apelăm fibo(5)
:
Observăm că în timpul calculării lui fibo(5)
, apelăm fibo(4)
și fibo(3)
.
Când apelăm fibo(4)
, apelăm din nou fibo(3)
, pe care l-am calculat deja.
Acesta este un exemplu simplu în care se observă faptul că se repetă
calcularea anumitor termeni, dar pentru calcularea fibo(30)
, de exemplu,
poate lua până la un minut — operație ce, în fond, doar face 30
de sume.
Alte resurse și bibliografie
DS
Autorul acestei lecții
Dominic Satnoianu
Această lecție a fost redactată de către Dominic Satnoianu.
© 2021 – 2025 Aspire Education Labs SRL. Toate drepturile rezervate.
Așa cum este specificat și în termeni și condiții, conținutul acestei pagini este protejat de legea drepturilor de autor și este interzisă copierea sau modificarea acestuia fără acordul scris al autorilor.
Încălcarea drepturilor de autor este o infracțiune și se pedepsește conform legii.
Comentarii 0