Przypomnienie wiadomości

Nim dowiemy się, jak zdefiniować ciąg Fibonacciego, przypomnijmy sobie, na czym polega rekurencja. Mamy z nią do czynienia, gdy funkcja wywołuje samą siebie w celu rozwiązania konkretnego problemu.

Ciąg Fibonacciego jest ciągiem liczb naturalnych. Jego pierwszy wyraz ma wartość 0, drugi 1, a każdy kolejny jest sumą dwóch poprzednich wyrazów ciągu.

Definicja ciągu Fibonacciego ma następującą postać:

F n = { 0 dla  n = 0 1 dla  n = 1 F n 1 + F n 2 dla  n > 1

Przykład 1

Obliczmy wyraz ciągu Fibonacciego o indeksie 5.

FIndeks dolny 5 = FIndeks dolny 4 + FIndeks dolny 3

FIndeks dolny 4 = FIndeks dolny 3 + FIndeks dolny 2

FIndeks dolny 3 = FIndeks dolny 2 + FIndeks dolny 1

FIndeks dolny 2  Indeks dolny koniec= FIndeks dolny 1 + FIndeks dolny 0 = 1 + 0 = 1

FIndeks dolny 3  Indeks dolny koniec= FIndeks dolny 2 + FIndeks dolny 1 = 1 + 1 = 2

FIndeks dolny 4 = FIndeks dolny 3 + FIndeks dolny 2 = 2 + 1 = 3

FIndeks dolny 5 = FIndeks dolny 4 + FIndeks dolny 3 = 3 + 2 = 5

Przedstawione wywołania funkcji rekurencyjnej można zobrazować przy użyciu drzewa wywołań rekurencyjnych:

R1aysrpZyBaBW
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Jakie są wartości kilkunastu początkowych wyrazów ciągu Fibonacciego? Są nimi liczby: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

Postać rekurencyjna

Zapisany niżej algorytm opiera się na przedstawionej wcześniej definicji wyrazów ciągu Fibonacciego. Odpowiedni pseudokod wygląda następująco:

Linia 1. funkcja fibonacci otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeżeli n znak równości znak równości 0 wykonaj dwukropek. Linia 3. zwróć 0. Linia 4. w przeciwnym razie jeżeli n znak równości znak równości 1 wykonaj dwukropek. Linia 5. zwróć 1. Linia 6. w przeciwnym razie wykonaj dwukropek. Linia 7. zwróć Fibonacci otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus Fibonacci otwórz nawias okrągły n minus 2 zamknij nawias okrągły.

Rekurencyjny algorytm przedstawiony powyżej jest prosty. Niestety, program napisany z jego wykorzystaniem okazuje się mało wydajny: działa bardzo wolno i nadaje się jedynie do obliczania kilku pierwszych wyrazów ciągu. Wynika to z faktu, że w celu wyznaczenia wybranego elementu ciągu wielokrotnie są obliczane te same, poprzedzające go wartości. W rezultacie złożoność czasowa algorytmu jest wykładnicza. Tym samym czas działania programu będzie znacznie dłuższy dla coraz dalszych wyrazów. Istnieje ponadto ryzyko wystąpienia błędu przepełnienia pamięciprzepełnienie pamięciprzepełnienia pamięci z powodu zbyt dużej liczby wywołań funkcji rekurencyjnej. W związku z tym należy stosować wersję iteracyjną algorytmu, pozwalającego wyliczyć kolejne wyrazy ciągu Fibonacciego. Przedstawimy go w kolejnej sekcji materiału.

Co to jest złota liczba?

Elementy ciągu Fibonacciego mają ciekawą cechę. Ilorazy dwóch kolejnych wyrazów są w przybliżeniu równe 1,618. Jest to tym bardziej widoczne, im większe liczby dzielimy przez siebie: wraz ze zbliżaniem się do nieskończoności uzyskujemy lepsze przybliżenie wartości 1,618. Liczbę tę nazywamy „złotą proporcją” lub „złotą liczbą”.

Liczby Fibonacciego wokół nas

Liczba płatków kwiatu jest przeważnie liczbą Fibonacciego. Podobnie jest z ulistnieniem i właśnie dlatego tak trudno jest znaleźć czterolistną koniczynę. W normalnych warunkach, gdy nie zachodzi żadna hodowla, kwiaty mają: 1, 2, 3, 5, 8, 13, 21, a niektóre gatunki nawet po 34 płatki lub więcej, np. stokrotka.

Liczby Fibonacciego odnajdziemy także, przyglądając się niektórym proporcjom ludzkiego ciała. W proporcjach ciała harmonijnie rozwiniętego człowieka znajdziemy złotą proporcję. Co prawda, nie zawsze są one idealnie i dokładnie zachowane, ale są na pewno bardzo zbliżone.

Złotą liczbę otrzymasz m.in. z następujących stosunków:

  • odległość od pępka do czubka głowy do odległości od ramion do czubka głowy;

  • odległość od ramion do czubka głowy do odległości od brody do czubka głowy;

  • wysokość twarzy do jej szerokości;

  • odległość od kolana do pępka do odległości od kolana do stopy;

  • odległość od koniuszków palców do łokcia do odległości od nadgarstka do łokcia;

  • dzieląc wzrost człowieka przez odległość od stóp do pępka.

Ciąg Fibonacciego można również odnaleźć w muzyce. Wiele utworów, zarówno współczesnych, jak i tych starszych, jest opartych na kanonie Pachelbela. Nuty tego utworu są zapisane na podstawie ciągu Fibonacciego.

Przedstawiliśmy tylko kilka spośród wielu przypadków, w których da się zauważyć liczby Fibonacciego w otaczającym nas świecie. Napotkamy je też w literaturze, sztuce, ekonomii, architekturze czy religii.

Słownik

przepełnienie pamięci
przepełnienie pamięci

błąd polegający na przekroczeniu rozmiaru miejsca zarezerwowanego dla programu w pamięci komputera

rekurencja
rekurencja

technika programowania, w której funkcja wywołuje samą siebie, aż do napotkania przypadku podstawowego

złożoność czasowa
złożoność czasowa

miara czasu działania algorytmu, wyrażona jako funkcja ilości danych

złożoność pamięciowa
złożoność pamięciowa

miara zajętości pamięci wykorzystywanej przez algorytm, wyrażona jako funkcja ilości danych