Lekcja 12: Ciag Fibonacciego - obliczanie iteracyjne elementow ciagu

Historia ciagu Fibonacciego

Ciag Fibonacciego to jeden z najslynniejszych ciagow liczbowych w matematyce. Odkryl go wloski matematyk Leonardo Fibonacci (ok. 1170-1250) w swoim dziele "Liber Abaci" z 1202 roku. Fibonacci, znany rowniez jako Leonardo z Pizy, analizowal problem rozmnazania krolikow i doszedl do ciagu, w ktorym kazdy kolejny element jest suma dwoch poprzednich. Chociaz ciag ten nosi imie Fibonacciego, matematycy indyjscy znali go juz wczesniej - Virahanka opisal go w VI wieku w kontekscie metryki poetyckiej.

Ciag Fibonacciego fascynuje matematykow, przyrodnikow i artystow od stuleci. Pojawia sie w zaskakujaco wielu miejscach w naturze - od ukladow lisci na lodygach roslin (filotaksja), przez spirale w slonecznikach i muszelkach slimakow, az po proporcje w ciele czlowieka. Ten zwiazek miedzy matematyka a natura sprawia, ze ciag Fibonacciego jest jednym z najbardziej eleganckich przykladow polaczenia abstrakcyjnej matematyki ze swiatem rzeczywistym.

Definicja matematyczna

Ciag Fibonacciego definiujemy rekurencyjnie za pomoca nastepujacego wzoru. Pierwsze dwa wyrazy sa z gory ustalone (F(0) = 0, F(1) = 1), a kazdy kolejny wyraz powstaje jako suma dwoch poprzednich:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)   dla n >= 2

Poczatkowe wyrazy ciagu:
n:    0  1  2  3  4  5  6   7   8   9  10  11   12   13   14
F(n): 0  1  1  2  3  5  8  13  21  34  55  89  144  233  377

Algorytm iteracyjny - pseudokod

Obliczamy kolejne wyrazy ciagu iteracyjnie, przechowujac tylko dwa ostatnie wyrazy. Ta metoda jest bardzo wydajna - wymaga jedynie stalej ilosci pamieci (dwie zmienne) i wykonuje dokladnie n-1 operacji dodawania. W porownaniu z wersja rekurencyjna, ktora moze wykonac miliard operacji dla n=40, wersja iteracyjna radzi sobie w ulamku sekundy:

ALGORYTM Fibonacci_Iteracyjny(n):
  JESLI n = 0: ZWROC 0
  JESLI n = 1: ZWROC 1

  a = 0    // F(0)
  b = 1    // F(1)

  DLA i OD 2 DO n:
    c = a + b    // nowy wyraz = suma dwoch poprzednich
    a = b        // przesuwamy "okno"
    b = c
  ZWROC b

Implementacja w Pythonie

def fibonacci(n):
    """Zwraca n-ty wyraz ciagu Fibonacciego (iteracyjnie)."""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

def wypisz_fibonacci(n):
    """Wypisuje pierwsze n+1 wyrazow ciagu."""
    a, b = 0, 1
    print(a, end=" ")
    if n >= 1:
        print(b, end=" ")
    for _ in range(2, n + 1):
        a, b = b, a + b
        print(b, end=" ")

# Test
print(fibonacci(10))  # 55
wypisz_fibonacci(10)   # 0 1 1 2 3 5 8 13 21 34 55

Dlaczego NIE rekurencja (na tym etapie)?

Istnieje tez wersja rekurencyjna, ale jest dramatycznie nieefektywna. Dla n=40 wersja rekurencyjna wykonuje ponad miliard operacji, podczas gdy wersja iteracyjna - tylko 39 dodawan. Problem polega na tym, ze rekurencja wielokrotnie oblicza te same wartosci, np. F(5) jest obliczane wiele razy przy obliczaniu F(10).

Ciag Fibonacciego w przyrodzie i technice

Ciag Fibonacciego zaskakujaco czesto pojawia sie w otaczajacym nas swiecie. Oto najciekawsze przyklady jego wystepowania:

• Uklad lisci na lodydze (filotaksja) - spirale w slonecznikach, szyszkach sosnowych, ananasach
• Spirala Fibonacciego - widoczna w muszlach slimakow (nautilus), huraganach, galaktykach spiralnych
• Informatyka - kopce Fibonacciego (zaawansowana struktura danych), analiza algorytmu Euklidesa
• Gielda - poziomy Fibonacciego w analizie technicznej (23.6%, 38.2%, 61.8%)
• Muzyka - proporcje w utworach Bacha, Bartoka i Debussy'ego
• Architektura - zlota proporcja w budowlach (Partenon, piramidy w Gizie)