Ciąg Fibonacciego – Fibonacci, Liczby Fibonacciego

Liczby Fibonacciego i ciąg Fibonacciego – to zagadnienie, które fascynuje ludzi od lat – i mimo iż spotykamy się z nim na co dzień, często nawet nie zdajemy sobie z tego sprawy.
Przyjrzyjmy się dziś bliżej tym niezwykłym liczbom i jak przystało na prawdziwych programistów – spróbujmy zmierzyć się z algorytmami wykorzystującymi ciąg Fibonacciego w praktyce.

Ciąg Fibonacciego – wprowadzenie

Z tego materiału dowiesz się:

• Co to jest ciąg liczb Fibonacciego?
• Kim był Leonardo Fibonacci?
• Gdzie w przyrodzie, ciele człowieka oraz matematyce możemy spotkać liczby Fibonacciego?
• Jak zaimplementować algorytmy iteracyjne i rekurencyjne wykorzystujące liczby Fibonacciego?

Ciąg Fibonacciego

Ciąg Fibonacciego – to ciąg liczb naturalnych w którym:

• Pierwszy (czasem nazywany również zerowym – stąd rozbieżności w numeracji)
  wyraz jest równy 0;
• Drugi wyraz jest równy 1;
• Każdy kolejny element jest sumą dwóch poprzednich.

Fibonacci series | Fibonacci sequence

Przykładowo 6. element Ciągu Fibonacciego będzie miał wartość:

Liczby Fibonacciego (ang. Fibonacci numbers)

Lista 1000 kolejnych liczb ciągu Fibonacciego.

Ciąg Fibonacciego – implementacja

Skoro wiemy już, czym jest Ciąg Fibonacciego, to spróbujmy zaimplementować algorytm, który wyświetli nam kolejne elementy tego ciągu.

W tym celu posłużymy się dwoma niezależnymi podejściami: iteracyjnym oraz rekurencyjnym.

O obu podejściach możesz przeczytać w podlinkowanych materiałach – tutaj skupimy się już na samych liczbach Fibonacciego.

→ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

→ ZOBACZ 👉: Iteracja, iteracje – powtarzanie w programowaniu vs Rekurencja ➿

Ciąg Fibonacciego – wzór i implementacja rekurencyjna

Zgodnie ze wzorem rekurencyjnym – wiemy, że:

• Pierwszy wyraz jest równy 0;
• Drugi wyraz jest równy 1;
• Każdy kolejny element jest sumą dwóch poprzednich.

Czyli przekładając to na kod Javy – mamy metodę z zaimplementowanym algorytmem rekurencyjnym:

int fibo(int i) {
	if (i == 0) {
		return 0;
	}
	if (i == 1) {
		return 1;
	}

	return fibo(i - 2) + fibo(i - 1);
}

Ciąg Fibonacciego – podejście rekurencyjne a stos wywołań

Podejście rekurencyjne, mimo iż jest bardzo proste w implementacji – nie jest jednak pozbawione wad.

Zobacz, jak wygląda stos wywołań, gdybyśmy chcieli obliczyć 6. element tego ciągu.

Przy każdym wywołaniu funkcji deklarowane są kolejne zmienne, które są zwalniane, dopiero jak funkcja zwróci wartość.
W naszym wypadku do obliczenia mamy tylko 6. element ciągu Fibonacciego – wyobraź sobie jednak, jak wyglądałoby to dla 100. lub 1000. elementu...

Nie jest to jednak jedyny sposób, w jaki możemy podejść do tego problemu – alternatywny sposób opiera się o algorytm iteracyjny.

Ciąg Fibonacciego – implementacja iteracyjna

Poniżej fragment kodu w wersji iteracyjnej:

int fibIter(int n){
	int a = 0, b = 1, t = 1;

	for (int i = 0; i < n; i++) {
		t = a;
		a = a + b;
		b = t;
	}

	return a;
}

To rozwiązanie jest szczególnie wygodne jeżeli chcemy wyświetlić kolejne elementy ciągu – a nie tylko jeden z nich.

• Nasza funkcja przyjmuje argument, który określa który wyraz ciągu Fibonacciego mamy wyliczyć.
• Algorytm zaczynamy od zadeklarowanie zmiennych:
  • a – początkowo pierwszy wyraz ciągu
  • b – początkowo drugi wyraz ciągu
  • t – zmienna pomocnicza
• W kolejnych iteracjach naszej pętli:
  • przechowujemy w zmiennej pomocniczej wartość zmiennej a
  • zwiększamy wartość zmiennej a, o wartość b
  • ustawiamy wartość zmiennej b na wartość przechowaną w zmiennej pomocniczej
• Dzięki temu – zmienna a przechowuje wartość i-tego elementu ciągu, a zmienna b jego poprzednika.

Ciąg Fibonacciego – optymalizacja algorytmów

Obie implementacje – pod względem wydajności świetnie sobie radzą przy stosunkowo niedużych liczbach. Na moim komputerze dla 20. elementu ciągu Fibonacciego gołym okiem nie byłem w stanie zobaczyć różnicy.

Sprawa oczywiście zacznie nam się komplikować, gdy spróbujemy obliczyć dalsze elementy ciągu – jak, chociażby 100. czy 1000.

→ ZOBACZ 👉: Benchmark sposobem na wydajniejsze aplikacje – JMH

Wielkie liczby (ang. big numbers) – BigInteger

Pierwszym z problemów, na który trafiamy jest ograniczony zakres typu Integer.

Problem możemy lekko odsunąć w czasie, wykorzystując typ Long – jednak dopiero wykorzystaniem wbudowanych w Javie wielkich liczb i klasy BigInteger zapewnimy sobie wsparcie dla naprawdę dużego wyniku.

BigInteger fibo(int i) {
	if (i == 0) {
		return BigInteger.ZERO;
	}

	if (i == 1) {
		return BigInteger.ONE;
	}

	return fibo(i - 1).add(fibo(i - 2));
}

Ta prosta zmiana pozwala nam się cieszyć większymi wynikami bez konieczności martwienia się o zakres zmiennych.

Nie rozwiązuje to jednak problemów związanych z wydajnością i baaaardzo długim czasem oczekiwania na nasz wynik 🙂

Programowanie dynamiczne

Kolejną optymalizacją, którą możemy zastosować, jest programowanie dynamiczne.

Sama idea jest dosyć prosta i polega na identyfikacji problemów w ten sposób, by ich obliczenia wykonywać tylko raz – co w przypadku wersji rekurencyjnej ma BARDZO duże znaczenie.

Map results = new HashMap<>();

BigInteger fibo(int i) {
	if (i == 0) {
		return BigInteger.ZERO;
	}

	if (i == 1) {
		return BigInteger.ONE;
	}

	if (results.containsKey(BigInteger.valueOf(i))) {
		return results.get(BigInteger.valueOf(i));
	}

	BigInteger result = fibo(i - 1).add(fibo(i - 2));

	results.put(BigInteger.valueOf(i), result);

	return result;
}

Więcej na temat programowania dynamicznego możesz przeczytać w podlinkowanym wpisie:

→ ZOBACZ 👉: Programowanie dynamiczne – rekurencja ➿

Rekurencja ogonowa

Dobre wyniki optymalizacji daje również wprowadzenie rekurencji ogonowej.
Ta na pierwszy rzut oka niewielka zmiana w wersji algorytmu rekurencyjnego daje możliwość kompilatorowi wprowadzić znaczące optymalizacje i uniknąć kosztownego budowania ogromnego stosu wywołań.

public long fibo(int n) {
	return fibo(n, 1, 0);
}

private long fibo(int n, long a, long b) {
	if (n == 0) {
		return b;
	}

	return fibo(n - 1, a + b, a);
}

Temat rekurencji ogonowej rozwijam w poniższym wpisie:

→ ZOBACZ 👉: Rekurencja ogonowa

Fibonacci – Leonardo Fibonacci

Leonardo Fibonacci – żył w latach 1175 – 1250.
Był to włoski matematyk pochodzący z Pizy.

To dzięki niemu między innymi posługujemy się cyframi arabskimi – jednak jego najbardziej znanym dziełem jest wzór określający kolejne wyrazy ciągu Fibonacciego.

Złota proporcja

Złota proporcja – podział harmoniczny, złoty podział, boska proporcja – czy też złoty środek 😃

Niezależnie od nazw, których jak widzimy, jest sporo – chodzi o zależność, która jak się okazało, występuje w bardzo wielu miejscach – w przyrodzie, w matematyce i również w ciągu Fibonacciego.

Jeżeli podzielimy odcinek na 2 części (lub weźmiemy odpowiadające jego długości 2 kolejne elementy ciągu Fibonacciego) – to stosunek długości dłuższego z nich do krótszego jest taki sam jak całego odcinka do części dłuższej.

Przykładowo:

• Mamy elementy ciągu: 1, 1, 2, 3, 5 – rozważmy 3 i 5
• (5+3) / 5 = (powinno być równe) = 5/3
• 8/5 = 5/3
• 1,6 = 1,67
• Mniej więcej się zgadza 😉

Okazuje się, że im większe wyrazy ciągu podzielimy, tym dokładniejsze przybliżenie uzyskamy.

Powstałą w ten sposób liczbę nazywamy właśnie – „złotą liczbą” i oznaczamy grecką literą φ (czyt. „fi”).

Właśnie ten stosunek udało się odnaleźć w bardzo wielu miejscach – zarówno w przyrodzie, jak i w matematyce.

Ciąg Fibonacciego w przyrodzie

Dla „idealnego drzewa” – gdyby ponumerować gałęzie zgodnie z wysokością, na której wyrosły – to okazuje się, że liczba gałęzi na tym poziomie jest liczbą Fibonacciego.

Spirala Fibonacciego (ang. Fibonacci spiral)

Przykładem spirali Fibonacciego w przyrodzie są muszle.

Ciało człowieka

A ciało człowieka?

Okazuje się, że liczb Fibonacciego można również doszukać się w naszym ciele – np. stosunek wzrostu człowieka do odległości od stóp do pępka też pasuje do złotej proporcji.

Ciąg liczb Fibonacciego na giełdzie

Liczby Fibonacciego znajdują również swoje zastosowanie między innymi w analizie technicznej na rynkach finansowych. Tzw. zniesienia Fibonacciego to linie odpowiadające poszczególnym wartościom procentowym, wynikającym z operacji na liczbach ciągu Fibonacciego.

Ciąg Fibonacciego – podsumowanie

W ramach tego materiału przećwiczyliśmy wyliczanie liczb ciągu Fibonacciego, wykorzystując algorytm rekurencyjny oraz iterację. Dowiedzieliśmy się również więcej o tzw. złotym środku, a także gdzie w otaczającym nas świecie możemy „dopatrzeć się” liczb Fibonacciego.

Jeżeli spodobał Ci się ten materiał lub jeśli dopiero co zaczynasz swoją przygodę z programowaniem i chcesz dobrze wejść w świat deweloperów, zapraszam Cię do zapoznania się z moim programem dotyczącym Javy:

→ ZOBACZ 👉: Java od podstaw