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:

Ciąg Fibonacciego – wzór rekurencyjny

• 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:

Ciąg Fibonacciego – wzór rekurencyjny

• 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.

Fibonacci – rekurencja

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<BigInteger, BigInteger> 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

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 kwadratów, których długości boków są kolejnymi liczbami Fibonacciego

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