Dându-se un număr natural n, să se verifice dacă este sau nu un termen al șirului Fibonacci.
Exemplu. Pentru n = 13, răspunsul este DA, pe când, pentru n = 14, răspunsul este NU.
Ce este șirul Fibonacci
Șirul Fibonacci este un faimos șir, care se generează pe baza următoarei reguli:
Astfel, primele elemente ale șirului sunt: 1, 1, 2, 3, 5, 8, 13, 21, ….
Explicarea algoritmului
Vom genera elementele șirului Fibonacci până când elementul curent este egal sau mai mare decât n (numărul pe care îl verificăm). Astfel, dacă atingem valoarea n, înseamnă că n este un termen Fibonacci. Dacă, în schimb, trecem peste valoarea n, înseamnă că n nu face parte din șirul Fibonacci.
Implementare C++
Iată secvența de cod care verifică dacă un număr n este sau nu număr Fibonacci.
#include <iostream>
using namespace std;
int main()
{
//Declarăm și citim numărul pe care îl verificăm, n
int n;
cin >> n;
if(n == 1) { //Caz particular
cout << "DA";
} else {
//Generăm șirul Fibonacci pentru a verifica dacă n face parte din șir
//Îl vom genera cu trei variabile: c = fn, b = fn-1, a = fn-2
int a = 1, b = 1, c;
int esteTermenFib = 0; //În caz că nu este termen Fibonacci, să afișăm NU la final
do {
c = a + b;
a = b;
b = c;
if(n == c) { //Este termen Fibonacci
esteTermenFib = 1;
cout << "DA";
break;
}
} while(c <= n);
if(esteTermenFib == 0) { //Nu este termen Fibonacci
cout << "NU";
}
}
return 0;
}