Co to jest ciąg Fibonacciego?

Ciąg Fibonacciego to ciąg liczb naturalnych zdefiniowany rekurencyjnie: dwie pierwsze wartości to F₀ = 0 i F₁ = 1, a każda kolejna jest sumą dwóch poprzednich. Początkowe wyrazy to 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… Ciąg wydaje się prosty, ale ma niezwykłe właściwości matematyczne — stosunek kolejnych liczb zbliża się do złotej liczby φ ≈ 1,618, a jego wzorce można zaobserwować w przyrodzie, architekturze i sztuce.

Jak obliczyć liczby ciągu Fibonacciego?

Wzór rekurencyjny to F(n) = F(n−1) + F(n−2) dla n ≥ 2, z bazowymi F₀ = 0 i F₁ = 1. Aby obliczyć np. F₇, sumujemy F₅ (5) i F₆ (8) → 13. W praktyce naiwna rekurencja jest niewydajna (złożoność O(2ⁿ) — F(40) zajmuje sekundy, F(50) minuty). Lepiej liczyć iteracyjnie, trzymając tylko ostatnie dwie wartości — wtedy złożoność spada do O(n). Dla bardzo dużych n istnieje też zamknięty wzór Bineta oparty na złotej proporcji, działający w O(log n).

Gdzie ciąg Fibonacciego występuje w naturze?

Wzorzec pojawia się zaskakująco często: w spiralnym układzie nasion słonecznika i szyszek, w rozmieszczeniu liści wokół łodygi roślin (filotaksja), w skorupach ślimaków i muszlach małż, w rogach muflonów, w kształtach galaktyk spiralnych i nawet w torze huraganów. To nie przypadek — w wielu z tych przypadków układ wynika z optymalnego rozkładu energii lub miejsca. Liczba odgałęzień i liści u roślin często odpowiada kolejnym wyrazom ciągu, a kąt rozstawu zbliża się do złotego kąta 137,5°.

Jak złota liczba φ wiąże się z ciągiem Fibonacciego?

Dzieląc każdy wyraz ciągu Fibonacciego przez poprzedni (np. 13/8, 21/13, 34/21…), otrzymujemy wynik coraz bliższy złotej liczbie φ ≈ 1,61803398875. Im dalsze liczby w ciągu, tym dokładniejsze przybliżenie. φ to stosunek długości w „złotym podziale" — dłuższy odcinek do krótszego ma się tak, jak całość do dłuższego. Z tej proporcji powstaje złoty prostokąt i złoty kąt (≈137,5°). Ten ścisły związek tłumaczy, dlaczego wzorce ciągu pojawiają się tam, gdzie człowiek od wieków szuka harmonii.

Gdzie ciąg Fibonacciego znalazł zastosowanie w architekturze i sztuce?

Starożytni Egipcjanie wykorzystywali złotą proporcję przy budowie piramid, Grecy — w świątyniach (Partenon). Wieża Eiffla, Notre Dame i Tadż Mahal opierają fasady na złotym podziale. Leonardo da Vinci stosował ją w Monie Lizie, Ostatniej Wieczerzy i rysunku człowieka witruwiańskiego. Muzyka klasyczna — kompozytorzy zapisywali nuty według kolejnych wyrazów ciągu, otrzymując utwory uznawane za szczególnie harmonijne. Współcześnie projektanci graficzni używają jej w logo (Apple, Toyota, Pepsi, National Geographic) oraz układach kart bankomatowych i dowodów osobistych.

Jak wydajnie zaimplementować ciąg Fibonacciego w kodzie?

Trzy strategie do wyboru wg potrzeb. Dla n 10⁶ sięgnij po wzór Bineta z fast exponentiation (O(log n)) lub macierzowe potęgowanie. Naiwna rekurencja O(2ⁿ) staje się niewykonalna już dla n > 50, więc unikaj jej w produkcji.

Kto i kiedy jako pierwszy opisał ciąg Fibonacciego?

Powszechnie przypisuje się to Leonardo z Pizy zwanym Fibonaccim — włoski matematyk opisał ciąg w dziele Liber abaci z 1202 roku, w kontekście modelu rozmnażania się królików. Jednak Fibonacci nie był pierwszym, który go odkrył: zachowane pisma indyjskie zapisane w sanskrycie pochodzące z III-II wieku p.n.e. dowodzą, że ciąg był znany matematykom Wschodu znacznie wcześniej. „Odkrycie" Fibonacciego oznaczało więc tylko wprowadzenie tego pojęcia do europejskiej matematyki nowożytnej.

Kontakt

Back-end

Ciąg Fibonacciego - wyjaśnienie pojęcia i przykłady zastosowania.

Ciąg Fibonacciego to ciąg liczb naturalnych, który zaczyna się od 0 i 1, a każda kolejna liczba jest sumą dwóch poprzednich. Ciąg ten został opisany przez włoskiego matematyka Leonardo Fibonacciego w XII wieku.

Tomasz Kozon

CEO

11 paź 2022

7 minut czytania

Ciąg Fibonacciego to jedno z ciekawszych zagadnień matematycznych. Nie jest on tylko dziełem wyobraźni matematyków, ale można go zauważyć w biologii czy zjawiskach przyrodniczych. Znajduje także zastosowanie w architekturze, muzyce, a także na rynkach finansowych oraz w tworzeniu nowoczesnych technologii.

Powiązane case study

Wynajem magazynu w minuty zamiast dni - automatyzacja umów i płatności

Klient: Balticon S.A.

Branża: Logistyka / LogTech

Tajemniczy ciąg Fibonacciego i złota liczba

Leonardo z Pizy, o przydomku Fibonacci, to włoski matematyk, któremu powszechnie przypisuje się „odkrycie” wyjątkowego ciągu liczb w dziele Liber abaci pochodzącym z 1202 roku, w którym omówił go w kontekście rozmnażania się królików. Ciąg Fibonacciego to ciąg liczb naturalnych, z których każda kolejna liczba jest określona rekurencyjnie, czyli jest zależna od poprzednich. Pierwsza liczba ciągu to F0 = 0, a druga F1 = 1, z kolei każda kolejna jest sumą dwóch poprzednich:

F2 = 0+1 = 1

F3 = 1+1 = 2

F4 = 2+1 = 3

F5 = 3+2 = 5

F6 = 5+3 = 8

F7 = 8+5 = 13

F8 = 8+13 = 21

F9 = 13+21 = 34

…

Najciekawsze jest to, że ciąg Fibonacciego ma ogromny związek ze złotą liczbą. Złota liczba oznacza podział odcinka na dwie części w bardzo specyficzny sposób: stosunek długości dłuższego odcinka do krótszego musi jest równy stosunkowi całego odcinka do dłuższego odcinka.

Ciąg Fibonacciego

Jest to tak zwany złoty podział i określany jest przez tzw. złotą liczbę oznaczaną gracką literę φ (czyt. „fi”), której wartość wynosi 1,61803398875... Dzieląc kolejne liczby ze złotego ciągu przez poprzednią otrzymamy liczby coraz bliższe złotej liczbie.

ciag — ilustracja artykułu

Bazując na złotej liczbie, możemy otrzymać złoty prostokąt, którego boki pozostają do siebie w stosunku złotej proporcji:

ciag — ilustracja artykułu

Możemy również skonstruować złoty kąt, czyli kąt środkowy oparty na mniejszym z dwóch łuków powstałych w wyniku złotego podziału okręgu. Jego miara w przybliżeniu wynosi 137,5 stopnia.

ciag — ilustracja artykułu

Powiązana usługa

Web development

Projektujemy i tworzymy dedykowane aplikacje webowe - od MVP, które pozwala szybko zweryfikować pomysł, po rozbudowane platformy i systemy rozwijane przez lata. Budujemy zarówno warstwę frontendową, jak i backend, API, bazy danych, panele administracyjne oraz integracje z zewnętrznymi systemami. Pracujemy m.in. z Next.js, React, Node.js, NestJS, Pythonem, PostgreSQL i MongoDB. Tworzymy rozwiązania dopasowane do konkretnego procesu biznesowego: aplikacje SaaS, systemy wewnętrzne, platformy sprzedażowe, serwisy internetowe, marketplace’y i systemy CMS.

Ciąg Fibonacciego – jakie ma zastosowanie?

Ciąg Fibonacciego oraz złota liczba pojawią się w przyrodzie, kosmosie, anatomii ludzkiego ciała, architekturze, inżynierii, sztuce, muzyce czy fizyce. Ruchy fal, huragany, skorupy ślimaków i małż, rogi muflonów, płatki roślin, galaktyki spiralne, a u wielu roślin w kolejnych latach na poszczególnych poziomach ich wzrostu liczba odgałęzień oraz liczba liści są odzwierciedleniem liczb Fibonacciego.

Jak się jednak okazuje owo „odkrycie” ciągu oznaczało jedynie wprowadzenie tego pojęcia do europejskiej matematyki nowożytnej. Istnieją bowiem pisma indyjskie zapisanie w sanskrycie pochodzące z III i II wieku p.n.e., które potwierdzają fakt, że ciąg Fibonacciego był już wówczas znany. Samą zasadę złotej proporcji znali starożytni Egipcjanie, opierając na niej budowę piramid. Także starożytni Grecy tworzyli swoje świątynie z prostokątów, które zbudowane są w oparciu o złoty podział np. Partenon. Liczby Fibonacciego i złotą proporcję wykorzystywali w architekturze także nowożytni, budując np.: wieżę Eiffla, Katedrę Notre Dame czy Tadż Mahal. To właśnie dzięki złotej proporcji budowle te mają być odbierane jako harmonijne i doskonałe w swojej formie. Sam Leonardo da Vinci wykorzystywał złotą proporcję do tworzenia swoich obrazów, takich jak: Mona Lisa, Ostatnia Wieczerza, Narodziny Wenus czy marmurowa rzeźba Wenus z Milo. Wykorzystał ją, tworząc słynnego człowieka witruwianskiego, którego części ciała dążą do zachowania złotej proporcji. Ze złotej proporcji czerpali także najwięksi kompozytorzy muzyki klasycznej — kolejne nuty były zapisywane jako kolejne liczby ciągu Fibonacciego, dzięki czemu powstały najbardziej znane harmonijne utwory.

Ciąg Fibonacciego i złoty podział wykorzystuje się także w projektach współczesnego świata. Szczególnie upodobali je sobie projektanci i graficy komputerowi, dlatego że właśnie projekty zbudowane w oparciu o nie najbardziej przypadają do gustu klientom. N podstawie proporcji złotego podziału zostały zaprojektowane wszystkie karty bankomatowe, prawo jazdy czy dowód osobisty. Z ciągu Fibonacciego korzystają także największe firmy, które złoty podział mają zawarty w swoim logo: Toyota, BP, PZU, Pepsi czy National Geographic. Złoty podział i liczby Fibonacciego wykorzystane są w projektach stron internetowych czy samochodów osobowych. Ciąg Fibonacciego w pełni docenił światowy gigant, jakim jest Apple, tworząc urządzenia elektroniczne oraz swoje logo, które uchodzą za wyjątkowo estetyczne i harmonijne dzięki temu, że oparte zostały o złoty podział. Także finansiści dostrzegli prawidłowości występujące na giełdzie oparte na liczbach Fibonacciego. Według niektórych długość przedziałów czasowych wyznaczających zachowanie cen akcji na rynku zachowują się jak kolejne liczby tego ciągu.

Implementacja w popularnych językach programowania

Algorytm Fibonacciego jest klasycznym ćwiczeniem na rozmowach kwalifikacyjnych — pozwala szybko ocenić znajomość rekursji, optymalizacji i elementów konkretnego języka. W Pythonie najczęściej używa się @lru_cache dla automatycznej memoizacji. W JavaScripcie iteracja z destructuringiem ([a, b] = [b, a + b]) jest najpopularniejsza. Java wymaga BigInteger dla n > 92 (przepełnienie long). Rust pozwala na funkcjonalne wzorce z pattern matching. Haskell pokazuje elegancję lazy evaluation: fibs = 0 : 1 : zipWith (+) fibs (tail fibs) — leniwa lista nieskończona wszystkich liczb Fibonacciego.

Każdy język uczy czegoś innego o tym algorytmie:

Python — pokazuje moc dekoratorów (@lru_cache redukuje O(2ⁿ) do O(n) jednym dekoratorem)
JavaScript — uczy o destructuring assignment i mutowaniu zmiennych w iteracji
Java — wymusza świadomość zakresów typów (long vs BigInteger)
Rust — naucza pattern matching i trait-based polymorphism
Haskell — demonstruje lazy evaluation i recursive infinite data structures

Dla projektów wymagających obliczeń Fibonacci na dużą skalę (np. financial trading, blockchain), bazy danych z funkcjami rekurencyjnymi mogą obliczać tę sekwencję bezpośrednio w SQL przez WITH RECURSIVE — eliminuje round-trip do aplikacji.

Złożoność czasowa — rekursja vs iteracja

Implementacja Fibonacciego w wersji rekurencyjnej (bez optymalizacji) jest klasycznym przykładem algorytmu o złożoności wykładniczej O(2ⁿ). Każde wywołanie generuje 2 kolejne wywołania, tworząc drzewo o głębokości n. Praktyczna konsekwencja: fib(40) trwa kilka sekund, fib(50) — kilkanaście minut, fib(100) — niewykonalne w czasie życia wszechświata.

Trzy strategie optymalizacji:

1. Memoizacja (top-down DP) — O(n) czas, O(n) pamięć: zapisuj wyniki kolejnych wywołań w tablicy. Każda wartość obliczana raz, kolejne odczytywane z cache. To podejście implementowane w Python @lru_cache lub JavaScript za pomocą Map.

2. Iteracja (bottom-up DP) — O(n) czas, O(1) pamięć: oblicz od F(0) wzwyż, trzymając tylko ostatnie 2 wartości. Najwydajniejsze dla pojedynczego wywołania, brak overhead'u stack frame.

3. Wzór Bineta — O(log n) czas (z fast exponentiation), O(1) pamięć: matematyczne rozwiązanie zamknięte oparte na złotej proporcji φ. Dla bardzo dużych n najszybsze. Zwracaj uwagę na precyzję floating-point.

W praktyce inżynierskiej:

Dla n < 30: dowolna metoda
Dla n < 1000: iteracja (najszybsza w stałej pamięci)
Dla n > 10⁶: wzór Bineta z BigDecimal lub macierzowe potęgowanie
Dla dynamicznych zapytań: memoizacja + persistent cache (Redis)

Pytanie o Fibonacciego na rozmowie kwalifikacyjnej często testuje czy kandydat zauważy problem rekursji bez optymalizacji — to typowy filtr między juniorem a midem.

FAQ

FAQ – najczęstsze pytania dotyczące ciągu Fibonacciego

Ciąg Fibonacciego to ciąg liczb naturalnych zdefiniowany rekurencyjnie: dwie pierwsze wartości to F₀ = 0 i F₁ = 1, a każda kolejna jest sumą dwóch poprzednich. Początkowe wyrazy to 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89… Ciąg wydaje się prosty, ale ma niezwykłe właściwości matematyczne — stosunek kolejnych liczb zbliża się do złotej liczby φ ≈ 1,618, a jego wzorce można zaobserwować w przyrodzie, architekturze i sztuce.
Wzór rekurencyjny to F(n) = F(n−1) + F(n−2) dla n ≥ 2, z bazowymi F₀ = 0 i F₁ = 1. Aby obliczyć np. F₇, sumujemy F₅ (5) i F₆ (8) → 13. W praktyce naiwna rekurencja jest niewydajna (złożoność O(2ⁿ) — F(40) zajmuje sekundy, F(50) minuty). Lepiej liczyć iteracyjnie, trzymając tylko ostatnie dwie wartości — wtedy złożoność spada do O(n). Dla bardzo dużych n istnieje też zamknięty wzór Bineta oparty na złotej proporcji, działający w O(log n).
Wzorzec pojawia się zaskakująco często: w spiralnym układzie nasion słonecznika i szyszek, w rozmieszczeniu liści wokół łodygi roślin (filotaksja), w skorupach ślimaków i muszlach małż, w rogach muflonów, w kształtach galaktyk spiralnych i nawet w torze huraganów. To nie przypadek — w wielu z tych przypadków układ wynika z optymalnego rozkładu energii lub miejsca. Liczba odgałęzień i liści u roślin często odpowiada kolejnym wyrazom ciągu, a kąt rozstawu zbliża się do złotego kąta 137,5°.
Dzieląc każdy wyraz ciągu Fibonacciego przez poprzedni (np. 13/8, 21/13, 34/21…), otrzymujemy wynik coraz bliższy złotej liczbie φ ≈ 1,61803398875. Im dalsze liczby w ciągu, tym dokładniejsze przybliżenie. φ to stosunek długości w „złotym podziale" — dłuższy odcinek do krótszego ma się tak, jak całość do dłuższego. Z tej proporcji powstaje złoty prostokąt i złoty kąt (≈137,5°). Ten ścisły związek tłumaczy, dlaczego wzorce ciągu pojawiają się tam, gdzie człowiek od wieków szuka harmonii.
Starożytni Egipcjanie wykorzystywali złotą proporcję przy budowie piramid, Grecy — w świątyniach (Partenon). Wieża Eiffla, Notre Dame i Tadż Mahal opierają fasady na złotym podziale. Leonardo da Vinci stosował ją w Monie Lizie, Ostatniej Wieczerzy i rysunku człowieka witruwiańskiego. Muzyka klasyczna — kompozytorzy zapisywali nuty według kolejnych wyrazów ciągu, otrzymując utwory uznawane za szczególnie harmonijne. Współcześnie projektanci graficzni używają jej w logo (Apple, Toyota, Pepsi, National Geographic) oraz układach kart bankomatowych i dowodów osobistych.
Trzy strategie do wyboru wg potrzeb. Dla n < 1000 najszybsza jest iteracja bottom-up w O(n) czasu i O(1) pamięci — trzymaj tylko ostatnie dwie wartości. Dla dynamicznych zapytań stosuj memoizację (Python @lru_cache, JS Map) — O(n) czas i pamięć. Dla n > 10⁶ sięgnij po wzór Bineta z fast exponentiation (O(log n)) lub macierzowe potęgowanie. Naiwna rekurencja O(2ⁿ) staje się niewykonalna już dla n > 50, więc unikaj jej w produkcji.
Powszechnie przypisuje się to Leonardo z Pizy zwanym Fibonaccim — włoski matematyk opisał ciąg w dziele Liber abaci z 1202 roku, w kontekście modelu rozmnażania się królików. Jednak Fibonacci nie był pierwszym, który go odkrył: zachowane pisma indyjskie zapisane w sanskrycie pochodzące z III-II wieku p.n.e. dowodzą, że ciąg był znany matematykom Wschodu znacznie wcześniej. „Odkrycie" Fibonacciego oznaczało więc tylko wprowadzenie tego pojęcia do europejskiej matematyki nowożytnej.

Assembler to niskopoziomowy język programowania, który umożliwia bezpośrednie manipulowanie sprzętem komputera. Choć coraz rzadziej używany, wciąż stanowi cenną umiejętność dla programistów zajmujących się optymalizacją lub tworzeniem oprogramowania wbudowanego.

Tomasz Kozon

20 maj 2023