Algorytm Fibonacciego

by Arnold Basiński

Poprawię formatowanie, aby tekst był bardziej czytelny i przejrzysty. Oto poprawiona wersja artykułu na temat algorytmu Fibonacciego, z poprawnym podziałem na sekcje i lepszą czytelnością.

Spis odnośników

Ci ąg Fibonacciego – pełna analiza i implementacje w różnych językach

1. Wprowadzenie do algorytmu Fibonacciego

Algorytm Fibonacciego odnosi się do metod obliczania kolejnych wartości ciągu Fibonacciego – szeregu liczb, w którym każda kolejna wartość jest sumą dwóch poprzednich: [math]F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{dla } n > 1[/math]

Pierwsze wartości ciągu to:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

2. Historia algorytmu Fibonacciego

Historia ciągu Fibonacciego sięga starożytności. Po raz pierwszy podobny ciąg liczbowy pojawił się w matematyce indyjskiej ok. III wieku p.n.e. – Pingala, badając wzory metryczne w poezji sanskryckiej, opisał sekwencję odpowiadającą późniejszym liczbom Fibonacciego

W świecie zachodnim ciąg ten został spopularyzowany dopiero w średniowieczu za sprawą włoskiego matematyka Leonardo z Pizy, znanego jako Fibonacci. W 1202 roku opublikował on dzieło Liber Abaci, w którym omawia ciąg Fibonacciego w kontekście słynnej zagadki o rozmnażaniu królików

Zadał pytanie: ile par królików powstanie w ciągu roku z jednej pary, zakładając, że każdy nowo narodzony królik po miesiącu dojrzewa i od drugiego miesiąca wydaje na świat nową parę, a króliki żyją wiecznie. Okazało się, że liczba par w kolejnych miesiącach tworzy właśnie opisany wyżej ciąg (1, 1, 2, 3, 5, 8, 13, …). Ta łamigłówka stała się genezą nazwy „ciąg Fibonacciego” – choć sam ciąg znany był wcześniej, to Fibonacci jako pierwszy wprowadził go do matematyki europejskiej

Znaczenie w matematyce: Liczby Fibonacciego z czasem okazały się mieć ogromne znaczenie teoretyczne. Pojawiają się niespodziewanie w różnych działach matematyki – od teorii liczb, przez kombinatorykę, po geometrię. Istnieje nawet specjalistyczne czasopismo naukowe The Fibonacci Quarterly poświęcone wyłącznie badaniom nad własnościami tego ciągu

Jedną z najbardziej znanych właściwości jest związek ciągu Fibonacciego ze złotą proporcją. Istnieje wzór jawny (znany jako wzór Bineta), który wyraża [math]n[/math]-tą liczbę Fibonacciego za pomocą potęgi złotej liczby [math]\phi \approx 1,618 [/math](oraz jej dopełnienia [math]\psi \approx -0,618).[/math] Wynika z niego m.in., że stosunek kolejnych wyrazów ciągu dąży do stałej [math]\phi[/math] w granicy dla dużych [math]n[/math]

Ta „złota liczba” pojawia się w wielu kontekstach sztuki i architektury jako estetycznie przyjemna proporcja, co dodatkowo rozsławiło ciąg Fibonacciego w kulturze popularnej.

3. Zastosowania algorytmu Fibonacciego

📌 Informatyka

✔ Wyszukiwanie Fibonacciego – alternatywa dla wyszukiwania binarnego
✔ Kopiec Fibonacciego – struktura używana w algorytmach grafowych
✔ Generowanie losowych liczb – w niektórych systemach kryptograficznych

📌 Matematyka i nauka

✔ Teoria liczb – podział liczb na sumy liczb Fibonacciego
✔ Trójkąt Pascala – sumy przekątnych dają liczby Fibonacciego

📌 Biologia i natura

✔ Układ spirali w słonecznikach
✔ Rozmieszczenie liści na łodygach roślin
✔ Proporcje w strukturze DNA

📌 Finanse i giełda

✔ Zniesienia Fibonacciego – analiza techniczna rynków finansowych
✔ Projekcje Fibonacciego – przewidywanie trendów giełdowych

4. Analiza złożoności różnych metod obliczania Fibonacciego

❌ 1. Naiwna rekurencja (wolna, wykładnicza: [math]O(2n)O(2^n)[/math])

1
2
3
4
def fibonacci_recursive(n):

    if n &lt; 2:

        return n

    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

➡ Bardzo wolna dla dużych nn, ponieważ liczba operacji rośnie wykładniczo.

✅ 2. Iteracyjne podejście (zalecane dla większości przypadków, [math]O(n)O(n)[/math])

1
2
3
4
5
def fibonacci_iterative(n):

    a, b = 0, 1

    for _ in range(n):

        a, b = b, a + b

    return a

➡ Szybka i efektywna metoda, działa w czasie liniowym [math]O(n)O(n)[/math].

✅ 3. Optymalizacja poprzez memoizację (rekurencja z pamięcią, [math]O(n)O(n)[/math]

1
2
3
4
5
6
from functools import lru_cache

@lru_cache(maxsize=None)

def fibonacci_memoized(n):

    if n &lt; 2:

        return n

    return fibonacci_memoized(n-1) + fibonacci_memoized(n-2)

➡ Działa dużo szybciej niż zwykła rekurencja.

✅ 4. Algorytm macierzowy (szybkie potęgowanie, [math]O(log⁡n)O(\log n)[/math])

1
2
3
4
import numpy as np

def fibonacci_matrix(n):

    M = np.array([[1, 1], [1, 0]], dtype=object)

    return np.linalg.matrix_power(M, n)[0, 1]

➡ Najwydajniejsza metoda dla bardzo dużych nn.

5. Implementacje algorytmu w różnych językach

Python (iteracyjna wersja)

1
2
3
4
5
def fib(n):

    a, b = 0, 1

    for _ in range(n):

        a, b = b, a + b

    return a

JavaScript

1
2
3
4
5
6
7
function fib(n) {

    let a = 0, b = 1;

    for (let i = 0; i &lt; n; i++) {

        [a, b] = [b, a + b];

    }

    return a;

}

PHP

1
2
3
4
5
6
7
8
9
10
11
&lt;?php

function fib($n) {

    $a = 0; $b = 1;

    for ($i = 0; $i &lt; $n; $i++) {

        $temp = $a;

        $a = $b;

        $b = $temp + $b;

    }

    return $a;

}

?&gt;

Free Pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
function Fibonacci(n: Integer): Int64;

var a, b, temp: Int64;

begin

  a := 0; b := 1;

  while n &gt; 0 do

  begin

    temp := a;

    a := b;

    b := temp + b;

    n := n - 1;

  end;

  Fibonacci := a;

end;

6. Optymalizacje i porównanie wydajności metod

Metoda	Złożoność czasowa	Zalety	Wady
Rekurencja (naiwna)	O(2n)O(2^n)	Prosta implementacja	Bardzo wolna dla dużych nn
Iteracyjna	O(n)O(n)	Efektywna, szybka	Brak możliwości memoizacji
Memoizacja	O(n)O(n)	Rekurencja + optymalizacja	Większe zużycie pamięci
Macierzowa	O(log⁡n)O(\log n)	Bardzo szybka dla dużych nn	Skomplikowana implementacja

7. Podsumowanie

🔹 Najlepsza metoda dla małych i średnich wartości: iteracyjna wersja – szybka i oszczędna pamięciowo.
🔹 Dla dużych nn: metoda macierzowa lub szybkie potęgowanie działają w czasie O(log⁡n)O(\log n).
🔹 Rekurencja bez optymalizacji jest niewydajna i niezalecana.

Ciąg Fibonacciego to nie tylko ciekawostka matematyczna, ale również istotne narzędzie w algorytmice, analizie rynków i biologii. Znajomość różnych metod jego obliczania uczy optymalizacji i myślenia algorytmicznego, co jest kluczowe w programowaniu. 🚀