Ciąg Fibonacciego: algorytm, schemat blokowy i kalkulator

Jednym z zagadnień, które można określić jako podstawowe w zgłębianiu tajników algorytmiki, jest ciąg Fibonacciego. Pierwotnie został on opracowany przez włoskiego matematyka Leonarda z Pizy, który opisał przy jego pomocy proces rozmnażania się populacji królików. Warto jest ten ciąg poznać i zrozumieć, gdyż pozwala on na polepszenie zrozumienia różnic pomiędzy rekurencyjną, a iteracyjną metodą konstruowania algorytmów. Oprócz tego jest duża szansa, że trafi się on na maturze z informatyki oraz na studiach.

Co to jest ciąg Fibonacciego?

Z ciągiem Fibonacciego zetkniemy się również w dziedzinach pozainformatycznych. W biologii z jego pomocą opiszemy naturalne linie spiralne spotykane w roślinach. Wynika to z tego, że kąt wyrastania nowych organów (np. łodyg czy liści) jest równy proporcji, którą opisuje iloraz dwóch kolejnych liczb z ciągu Fibonacciego (a im większe liczby z ciągu weźmiemy na warsztat, tym dokładniejszą proporcję uzyskamy). Zależność tę nazywamy: „złotym kątem”.

Innym przykładem jest sztuka: kompozytorzy czasem tworzą swoje utwory w oparciu o zależności wyprowadzone z relacji pomiędzy kolejnymi liczbami Fibonacciego, zaś malarze potrafią planować rozłożenie elementów na obrazie w oparciu o estetykę odnoszącą się do tzw.: „złotego podziału”. Ten algorytm znajdziemy nawet na giełdzie, gdzie inwestorzy czasem wykorzystują zniesienia Fibonacciego przy szacowaniu korekt cen instrumentów finansowych.

Podstawowa zasada jest następująca: każda kolejna liczba ciągu jest sumą dwóch poprzednich wyrazów ciągu. Dlatego pierwsze dwie liczby musimy zdefiniować sami, zaś kolejne będą wynikać z poprzednich. Zakładamy, że są one równe 1. W takim razie:

F1 = 1

F2 = 1

Fn = Fn-1 + Fn-2

Z powyższego wzoru wynika, że początek ciągu będzie wyglądał następująco:

F = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…}

Ciąg Fibonacciego
W ciągu Fibonacciego, każdy kolejny wyraz jest sumą dwóch poprzednich.

Z punktu widzenia matury najważniejsza jest kwestia skonstruowania odpowiedniego algorytmu, który będzie wyliczał dla nas wartości konkretnych elementów ciągu. Musimy rozumieć zasadę działania na tyle, aby móc również rozwiązać zagadki oparte na ciągach zbliżonych do Fibonacciego. CKE często traktuje bazowy ciąg Fibonacciego jako inspirację pod algorytmy proponowane w zadaniach maturalnych, np. musimy być też gotowi na zrobienie podobnego ciągu, lecz opartego na sumowaniu trzech poprzednich elementów (takie rozwiązanie nazywamy ciągiem „Tribonacciego”). Omówmy wpierw wersję rekurencyjną algorytmu, a więc wprost wynikającą z definicji.

Kalkulator – wypisujący n-ty wyraz Ciągu Fibonacciego

Jeśli potrzebujesz sprawdzenia, czy Twój algorytm działa prawidłowo lub też zorientowania się czy prawidłowo rozumiesz ten rodzaj ciągu, skorzystaj z poniższego kalkulatora. Przekonasz się, jaką wartość posiada n-ty wyraz Ciągu Fibonacciego.

Kalkulator w opracowaniu

Algorytm rekurencyjny

Wariant rekurencyjny jest wersją prostszą w zapamiętaniu. Właściwie sprowadza się do przepisania definicji na język, w którym programujemy, oraz osadzenie go w funkcji. Zwróć uwagę, że definicje matematyczne bardzo często są łatwe w implementacji rekurencyjnej.

Schemat blokowy - Ciąg Fibonacciego rekurencja
Liczby Fibonacciego i wzorce z nimi związane są również używane w dziedzinach związanych z technologią, takich jak projektowanie interfejsów użytkownika, grafika komputerowa, animacje, czy wzornictwo stron internetowych.

W algorytmie zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku. Złożoność rekurencyjnej metody Fibonacciego wynosi O(2n).

Ciąg Fibonacciego – Pseudokod

Ciąg Fibonacciego – C++

Ciąg Fibonacciego – Python

Ciąg Fibonacciego – Java

ads banner

Algorytm iteracyjny

Cechą charakterystyczną tej wersji algorytmu jest to, że musimy wykorzystać w nim dodatkowe zmienne pomocnicze. Jest to konieczne, aby w trakcie wykonywania kolejnych operacji nie zgubić żadnej z wartości. Algorytm jest o tyle niewygodny, że wymaga swoistego „wachlowania” wartościami zmiennych.

W przykładzie posłużymy się następującymi zmiennymi: a i b będą służyły do przechowywania poprzedniego oraz bieżącego wyrazu ciągu, przy założeniu, że b zachowuje właściwy wynik dla każdej iteracji (więc co do zasady będzie „tą większą liczbą”). Żeby operacja była możliwa, musimy również przy każdym powtórzeniu przechować jej wartość tak, aby na skutek wyliczania kolejnej sumy, nie utracić jej wartości, bowiem przy kolejnej iteracji to „ta większa” będzie musiała stać się „tą mniejszą”. Wykorzystamy do tego zmienną temp (skrót od temporary czyli tymczasowa).

Schemat blokowy - Ciąg Fibonacciego Iteracja
Co ciekawe liczby Fibonacciego znalazły zastosowanie w teorii muzyki i kompozycji. Wykorzystanie wzorców opartych na ciągu Fibonacciego może nadać muzyce ciekawszy i harmonijny charakter.

Tak samo jak w wersji rekurencyjnej, zakładamy, że argument n na wejściu jest numerem wyrazu ciągu, który chcemy otrzymać w wyniku. Złożoność czasowa iteracyjnej metody Fibonacciego wynosi O(n).

Ciąg Fibonacciego – Pseudokod

Ciąg Fibonacciego – C++

Ciąg Fibonacciego – Python

Ciąg Fibonacciego – Java

Podsumowanie

Jeżeli opracujesz i w pełni zrozumiesz obie wersje algorytmu, bez problemu poradzisz sobie również z algorytmami podobnymi do ciągu Fibonacciego. Zadania tego typu możesz napotkać zarówno w zadaniach teoretycznych jak i praktycznych na egzaminie maturalnym, więc nigdy nie ucz się algorytmów na pamięć – najważniejsze jest ich zrozumienie. Bądź też gotowy do wykorzystania zarówno wersji rekurencyjnej jak i iteracyjnej. Może być bowiem tak, że w zadaniu teoretycznym natrafisz na polecenie, które już na wstępie precyzuje, w jakiej wersji musisz skonstruować algorytm. Dlatego nigdy nie pomijaj zagadnień niewygodnych, lecz wykorzystaj je, aby poszerzyć swoje umiejętności.

Najczęściej zadawane pytania o Ciąg Fibonacciego

Jakie są różnice między iteracyjnym a rekurencyjnym podejściem do obliczania ciągu Fibonacciego?
  • Rekurencyjne podejście bez optymalizacji może prowadzić do wielokrotnego obliczania tych samych wartości, co powoduje znaczny narzut czasowy. Dodatkowo też wymaga dużej ilości pamięci.
  • Iteracyjne podejście jest bardziej wydajne i eliminuje potrzebę wielokrotnego obliczania tych samych wartości, co jest możliwe dzięki korzystaniu z pętli. Na dodatek potrzebuje mniejszych zasobów pamięci.
Na czym polegają zastosowania ciągu Fibonacciego?
  • Algorytmy optymalizacyjne – ciąg Fibonacciego jest stosowany w rozwiązaniach, takich jak optymalizacja wyszukiwania binarnego, wyszukiwanie złotego punktu, czy optymalizacja jednowymiarowych funkcji jednomodalnych.
  • Finanse i ekonomia – wykorzystuje się go w analizie rynków finansowych, prognozowaniu cen akcji i innych instrumentów finansowych.
  • Architektura i sztuka – wzory bazujące na ciągu Fibonacciego są stosowane w projektowaniu architektonicznym, wzornictwie, sztuce i wzornictwie wnętrz, tworząc estetyczne proporcje.
Jakie są właściwości matematyczne ciągu Fibonacciego?
  • Złoty podział (Golden Ratio) – stosunek kolejnych liczb Fibonacciego zbliża się do wartości stałej matematycznej zwanej “złotym podziałem”. Stała ta jest bliska wartości 1.61803398875. W miarę zwiększania wartości n, stosunek kolejnych liczb Fibonacciego jest coraz bliższy tej stałej.
  • Wzór bineta – to wzór matematyczny, który pozwala obliczyć n-tą liczbę Fibonacciego bez potrzeby iteracyjnych obliczeń. Wzór ten wykorzystuje Złoty Stosunek i potęgi liczby 1,618. Jest to bardziej wydajna metoda obliczania dużych wartości z ciągu Fibonacciego.
  • Liczby Fibonacciego w przyrodzie – liczby Fibonacciego można zaobserwować w różnych wzorach wzrostu w przyrodzie, takich jak kształt muszli ślimaków, układ liści roślin, wzory rozkwitających kwiatów, itp. Wzorce te są znane jako “fraktale”.
Jak zoptymalizować ciąg Fibonacciego?

Memoizacja (Memoization) – używa się tablicy, która służy do zapisywania już obliczonych wartości ciągu Fibonacciego. W momencie obliczania n-tej liczby, sprawdzane jest, czy wartość ta została już obliczona i zapisana w tablicy. Jeśli tak, używany jest zapisany wynik bez konieczności ponownego obliczania. To ogranicza liczbę rekurencyjnych wywołań i zwiększa wydajność obliczeń.

ads banner

Wpisy, które mogą Cię zainteresować: