P-Programowanie

Ciąg (liczby) Fibonacciego

Ostatania modyfikacja: 22 marca 2015, kategoria: Matura z informatyki

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 wykorzystywanych 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().

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.

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:

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.

Użytkownik Michał napisał:

25 stycznia 2013


Dzięki, przydatny artykuł.

Użytkownik DarkGL napisał:

02 września 2013


Użytkownik Pershing napisał:

13 maja 2014


Dowolny wyraz możemy wyznaczyć również w prostszy sposób (bez iteracji, ani rekurencji):

fi = (1+sqrt(5))/2;
n-ty wyraz = (fi^n – (-fi^(-n)))/sqrt(5)

wyraz wystarczy zaokrąglić i mamy od razu piękny wynik

Użytkownik Ania napisał:

18 maja 2014


fajna stronka, akurat jest to co mam w liceum. I Pan jest ładny ;**

Użytkownik Maciek napisał:

04 marca 2018


Obliczanie ciągu fibonacciego rekurencyjnie to ogromna głupota, jedyną zaletą tego rozwiązania jest to, że jest intuicyjne. Skąd pomysł, że jest to „optymalne”? To brednia. Przecież liczysz wiele razy każdą z wartości. Spróbuj narysować sobie graficznie wywołania -> robi ci się z tego szybko rosnące drzewo. Metoda rekurencyjna ma złożoność klasy O(2^n). Rozwiązanie iteracyjne jest szybsze O(n), a optymalne to jest potęgowanie macierzy (przy odpowiedniej implementacji O(logn) ) :D

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0