Numerele lui Fibonacci
3Exista probleme ce avem necesara calcularea numerelor lui Fibonacci.
Ce sunt numerele lui Fibonacci?
Este un sir de n numere care se afla prin calcularea sumei a ultimilor doua numere precedente al i`lui numar, i > 2. Putem scoate urmatoarea recurenta :
Fib (n) = 0 , daca n = 0; 1 , daca n = 1 sau n = 2; Fib(n-1) + Fib(n-2) , n > 2
Din aceasta recurenta putem crea un vector cu primele n numere ale sirului.
Calcularea unui sir de n numere,reprezentand sirul lui Fibonacci.
#include <stdio.h> int main() { int n,i,a[101]; // putem construi doar primele 100 de elemente scanf("%d",&n); a[0] = 0; a[1] = a[2] = 1; for(i = 2; i < = n; i++) { a[i] = a[i-1] + a[i-2]; } return 0; }
Calcularea celui de-al n-lea numar al sirului lui Fibonacci
#include <stdio.h> int main() { int n,x,y,z,d; scanf("%d",&n); x=1; y=1; z=1; for(d=3;d< =n;d++) { z=x+y; x=y; y=z; } printf("%d",z); return 0;
Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!
Algoritmul de calculare descris mai sus este algoritmul „brute force”, avand complexitatea O(N). Exista si un algoritm mai eficient cu complexitate O(log N) care se bazeaza pe faptul ca matricea (1 1/ 1 0)(am desparit liniile prin /) ridicata la puterea N = (F(N+1) F(N)/ F(N) F(N-1)) unde F(N) este al N-lea termen al sirului Fibonacci. Puteti vedea http://en.wikipedia.org/wiki/Fibonacci_number pt mai multe detalii
A oferit o solutie simpla si rapida de calculare.. sa o folosesti cand ai nevoie repede..
si acea problema cu iepuri care este o aplicatie la acest sir cum se rezolva?