Ciąg Fibonacciego

powrót

Ciąg Fibonacciego definiujemy następująco:

pierwszy i drugi element ciągu jest równy 1. Każdy następny otrzymujemy dodając do siebie dwa poprzednie. Matematycznie wygląda to następująco:

$$F_n=\left\{\begin{matrix} 1 & ,\ dla\ n=1\\ 1 & ,\ dla\ n=2\\ F_{n-2}\ + F_{n-1}& ,\ dla\ n>2\\ \end{matrix}\right.$$

Inna definicja przedstawia zerowy numer ciągu jako wartość 0, pierwszy jako wartość 1, a każdy następny otrzymujemy dodając dwa poprzednie:

$$F_n=\left\{\begin{matrix} 0 & ,\ dla\ n=0\\ 1 & ,\ dla\ n=1\\ F_{n-2}\ + F_{n-1}& ,\ dla\ n>1\\ \end{matrix}\right.$$

Kilka kolejnych wyrazów tego ciągu według pierwszej definicji przedstawia się następująco:

$$1,1,2,3,5,8,13,21,...$$

Pierwsze rozwiązanie zostanie przedstawione metodą iteracyjną, która jest wydajna i bez problemu wyznaczymy wszystkie wyrazy ciągu, które mieszczą się w dowolnym typie w C++.

Strategia jest następująca. Zmienna $$a$$ będzie przechowywać wyraz o numerze $$n-2$$, zmienna $$b$$ wyraz o numerze $$n-1$$. W każdym przejściu pętli, zmienna $$b$$ przeskoczy na element następny, czyli sumę elementów $$a$$ i $$b$$

$$b=a+b$$,

natomiast zmienna $$a$$ przechowa to co przechowywała zmienna $$b$$ czyli

$$a = b - a = (a+b) - a = b. $$.

#include<iostream>
using namespace std;

void fibonacci(int n)
{    
     long long a = 0, b = 1;
  
     for(int i=0;i<n;i++)
     {
            cout<<b<<" ";
            b += a; //pod zmienną b przypisujemy wyraz następny czyli a+b
            a = b-a; //pod zmienną a przypisujemy wartość zmiennej b
     }     
}

int main()
{
    int n;
    
    cout<<"Podaj ile chcesz wypisać wyrazów ciągu fibonacciego: ";
    cin>>n;
    
    fibonacci(n);
    
    return 0;
}

Postać rekurencyjną przedstawimy do wyświetlenia pojedynczego wyrazu, ponieważ algorytm jest bardzo niewydajny i nadaje się tylko do wyznaczania niewielkiej ilości elementów ciągu.

#include<iostream>
using namespace std;

int fib(int n)
{
	if(n<3)
		return 1;
	
	return fib(n-2)+fib(n-1);
}

int main()
{
	
	int n;
	
	cout<<"Podaj nr wyrazu ciągu: ";
	cin>>n;
	
	cout<<n<<" wyraz ciągu ma wartość "<<fib(n)<<endl;

	return 0;
}

Przeanalizujmy powyższy algorytm dla $$n=5$$:

$$wynik=fib(5) = \underbrace{fib(4)}_{\underbrace{fib(3)}_{\underbrace{fib(1)}_1+\underbrace{fib(2)}_1}+\underbrace{fib(2)}_1}+\underbrace{fib(3)}_{\underbrace{fib(1)}_1+\underbrace{fib(2)}_1}=5$$