P-Programowanie

Ciąg (liczby) Fibonacciego

4 stycznia 2013, 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.

Komentarze:

Użytkownik Michał napisał/a:

25 stycznia 2013


Dzięki, przydatny artykuł.

Użytkownik DarkGL napisał/a:

02 września 2013


Użytkownik Pershing napisał/a:

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ł/a:

18 maja 2014


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

Zachęcam Cię do zostawienia komentarza!

Ilość znaków: 0

Zachęcam Cię do polubienia bloga na facebooku! Dając lajka wspierasz moją pracę - wszystkie artykuły na blogu są za darmo!