Ciąg (liczby) Fibonacciego

kategoria: Zadania z programowania

Ciąg Fibonacciego to szczególny rodzaj ciągu liczb naturalnych. Liczby tego ciągu nazywane są liczbami Fibonacciego. Spotykane są w wielu dziedzinach i sytuacjach np. w matematyce, w przyrodzie, na rynkach giełdowych oraz na maturze z informatyki! Ciąg Fibonacciego można określić rekurencyjnie – dlatego jest często wykorzystywany we wszelkich zadaniach informatycznych.

Definicja liczb Fibonacciego

Rekurencyjne opisanie ciągu Fibonacciego:

Ciąg Fibonacciego to ciąg liczb, w którym pierwszy wyraz jest równy 0, drugi jest równy 1 a każdy następny jest sumą dwóch poprzednich.

\[\begin{cases} {F}_{0} = 0\\ {F}_{1} = 1\\ {F}_{n} = ({F}_{n-1}) + ({F}_{n-2}) \end{cases}\]

Istnieje pewna nieścisłość zależnie od przyjętych wytycznych. W jednym z zadań na egzaminie maturalnych z informatyki, ciąg rozpoczynał się od cyfry 1. Różni autorzy mają różne zadanie na ten temat. Dostając wzór do zadania, zwróć uwagę na jego parametry.

Obliczając n-ty wyraz ciągu, musisz posługiwać się wartościami poprzednimi czyli n-1, n-2 itd. aż dojdziesz do wartości które znasz. Są nimi wartości dla F0 i F1.

Obliczymy wartość 4 wyrazu ciągu Fibonacciego, wynosi ona:

\[{F}_{4}={F}_{4-1}+{F}_{4-2}={F}_{3}+{F}_{2}\]

Jest to nasza wartość dla 4 wyrazu ciągu. Zapisujemy ją lub zapamiętujemy. Wzór rekurencyjny nie dostarcza nam informacji o elemencie F3 i F2 więc musimy ponownie rozpisać te wyrazy posługując się wzorem na n:

\[{F}_{3}={F}_{3-1}+{F}_{3-2}={F}_{2}+{F}_{1}\\ {F}_{2}={F}_{2-1}+{F}_{2-2}={F}_{1}+{F}_{0}=1+0=1\]

Zgodnie z obliczeniami wartość dla F2 wynosi 1. Dzięki temu możemy obliczyć wartość dla F3 i F4:

\[{F}_{3}={F}_{2}+{F}_{1}=1+1=2\\ {F}_{4}={F}_{3}+{F}_{2}=2+1=3\]

Ostatecznie 4 wyraz ciągu liczb Fibonacciego wynosi 3.

Obliczanie n-tego wyrazu ciągu Fibonacciego C++ (rekurencyjnie)

Za pomocą poniższego kodu możemy wyznaczyć dowolny n-ty wyraz ciągu Fibonacciego. Jest to sposób rekurencyjny, ponieważ zawiera rekurencyjne wywołanie funkcji fib().

#include <iostream>
#include <cstdlib>

using namespace std;

unsigned int 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 << "Podaj numer wyrazu ciagu fibonacciego do obliczenia:" << endl;
    cin >> n;

    cout << fib(n) << endl;

    system("PAUSE");
    return(0);
}

Obliczanie n-tego wyrazu ciągu Fibonacciego C++ (iteracyjnie)

Obliczanie n-tego wyrazu ciągu fibonacciego iteracyjne jest trudniejsze, i mniej optymalne w porównaniu do metody rekurencyjnej.

#include <iostream>
#include <cstdlib>

using namespace std;

unsigned int fib(int n)
{
    int a, b;
    if(n == 0) return 0;

    a = 0; b = 1;
    for(int i=0; i < (n-1); i++)
    {
        swap(a, b);
        b += a;
    }
    return b;
}

int main()
{
    int n;

    cout << "Podaj wyraz ciagu fibonacciego do obliczenia:" << endl;
    cin >> n;

    cout << fib(n) << endl;

    system("PAUSE");
    return(0);
}

Wypisywanie n wyrazów ciągu Fibonacciego

Korzystając ponownie ze wzoru rekurencyjnego możemy w łatwy sposób wypisać na ekran dowolną ilość liczb ciągu fibonacciego. Wystarczy wywołać funkcję w pętli odpowiednią ilość razy i wyświetlać na ekran wartości zwracane:

#include <iostream>
#include <cstdlib>

using namespace std;

unsigned int fib(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fib(n-1)+fib(n-2);
}

int main()
{
    int ilosc;

    cout << "Podaj ile wyrazow wypisac:" << endl;
    cin >> ilosc;

    for (int i = 0; i<=ilosc; i++)
        cout << fib(i) << ", ";

    system("PAUSE >nul");
    return(0);
}

Uwaga! Należy zwrócić uwagę na treść zadania. Pierwszym wyrazem ciągu Fibonacciego może być 0 lub 1. Jeżeli masz wypisać 10 wyrazów wypisujesz wyrazy od F1 do F10. Natomiast jeżeli w zadaniu ciąg zaczyna się od cyfry 0, wtedy traktujemy 0 jako pierwszy wyraz. Wypisując 10 wyrazów wypisujemy od wyrazy od F0 do F9. Tak jak pisałem wcześniej jest to kwestia umowna.