Dziś kolejne zadanie z cyklu JavaByExample. Dziś będziemy omawiać ciąg Fibonacciego. W poprzedniej lekcji z serii omawialiśmy przykład zliczania poszczególnych znaków z daniu. Dostałem na ten temat komentarz, iż zadania da się rozwiązać znacznie łatwiej niż zostało to przeze mnie przedstawione, używając Stremów. Bardzo dziękuję za ten komentarz! Poprzednie zadanie zostało zaktualizowane o rozwiązanie oparte na Streamach! Update znajdziecie we wpisie, jak i na GitHubie! 😊
01. Zadanie - Ciąg Fibonacciego
Dzisiejsze zadanie jest naprawdę klasykiem! 😊 Mała ciekawostka, kiedyś dostałem zadanie związane z ciągiem Fibonacciego na rozmowie rekrutacyjnej, jako zadnie na rozgrzewkę 😊 Warto zapoznać się o co chodzi 😊
Napisz program który policzy podany przez użytkownika element ciągu Fibonacciego.
Jak wygląda ten cały ciąg? Pierwsze dwie liczby to 1,1 a kolejna to suma dwóch poprzednich, czyli kolejnym elementem jest liczba 2! Mamy zatem 1,1,2 – kolejnym elementem jest 1+2 = 3 mamy teraz 1,1,2,3 – kolejny element 2+3=5 itd. Tak przedstawiają się kolejne elementy tego ciągu:
1,1,2,3,5,8,13,21,34,55,89… i tak w nieskończoność 😉
Przykład 1:
Użytkownik podaje liczbę: 6
Odpowiedź programu: 8
Przykład 2:
Użytkownik podaje liczbę: 10
Odpowiedź programu: 55
02. Uwaga!
Przede wszystkim – postaraj się rozwiązać to zadanie samodzielnie. Poniżej znajdziesz moje rozwiązanie, opis wraz z całym kodem źródłowym!
Przed rozpoczęciem mojego rozwiązania chciałbym przypomnieć o jednej bardzo ważnej sprawie. Pamiętaj o tym że nie ma jednego konkretnego sposobu na napisanie programu który rozwiązuje dany problem. Jak to powtarzał jeden z moich profesorów, konkretny program możemy napisać na milion sposobów i każdy z nich może być poprawny!
STOP -Poniżej znajdziesz moje rozwiązanie tego zadania – postaraj się rozwiązać najpierw samemu! W razie problemów możesz przeczytać moje rozwiązanie oraz zajrzeć na GitHuba!

03. Moje rozwiązanie
Zadanie można rozwiązać na wiele sposobów 😊 Naprawdę! Zadanie jest naprawdę klasyczne 😊 Wykładowcy lubią męczyć nim adeptów programowania, dziś przedstawię wam 3 różne sposoby rozwiązania, klasyczny z użyciem pętli, z użyciem rekurencji oraz z użyciem Stremów.
04. Fibonacci klasycznie
public static long fibClassic(int n) { long x1 = 1; long x2 = 1; for (int i = 3; i <= n; i++) { long temp = x1 + x2; x1 = x2; x2 = temp; } return x2; }
Opis: Tworzymy dwie zmienne którym nadajemy wartość 1, zgodnie z pierwszymi elementami ciągu. Zaczynamy pętle, początek pętli ustalamy na 3, pierwsze dwa elementy są znane, wiec sens wykonywania jakichkolwiek obliczeń mamy dopiero od trzeciego elementu. W pętli tworzymy tymczasową zmienną do której przypisujemy wynik sumy dwóch poprzednich elementów. Następnie dokonujemy „przesunięcia” nasze x1 dostaje wartość obecnego x2, natomiast x2 dostaje wyliczoną wartość. Użytkownikowi zwracamy x2 😊 będzie on miał przypisaną ostatnią wyliczoną wartość 😊
05. Fibonacci Rekursywnie
public static long fibRecursive(int n) { if(n <= 1) return n; return fibRecursive(n-2)+fibRecursive(n-1); }
Yeah, piękno rozwiązań rekursywnych 😉 Całe ciało metody zamknięte dosłownie w dwóch linijkach! Jeśli nigdy wcześniej nie spotkałeś się z metodami rekursywnymi już tłumaczę o co chodzi. W prostych słowach polega to na tym że metoda wywołuje sama siebie 😊 Metody rekursywne mają wiele pułapek, i łatwo stworzyć nieskończoną pętlę, trzeba ich używać ze szczególną ostrożnością.
Opis: Jeśli metoda dostanie liczbę 1 lub mniejszą, zwróci tą liczbę, jeśli dostanie liczbę większą od jeden zwraca sumę z wykonania metody dla dwóch poprzednich elementów (n-2 oraz n-1). Dla osób początkujących może być to ciężko do wyobrażenia więc spieszę z pomocnym rysunkiem! 😊 Żeby aż tak wiele nie rysować, przyjmiemy że użytkownik poprosił o 6 element ciągu (wynik 8) :

Okej! Rozrysowałem tylko jedną stronę 😉 ale myślę że z tego rysunku możecie sobie wyobrazić jak wygląda pozostała część 😊 Po prostu nie zmieściło mi się na rysunku 😊
Użytkownik podaje jako parametr wejściowy 6, zatem w zaczynamy naszą rekursywę fib(6-2)+fib(6-1). Czyli tak naprawdę fib(4)+fib(5). Rysunek przedstawia pełne drzewo dla fib(6-2) czyli dla fib(4), liczmy ostatnie gałęzie:
fib(4)= 0+1+1+0+1 = 3
Druga gałąź wyglądała by bardzo podobnie: fib(5)= fib(3)+fib(4) zwróć uwagę że fib(3) mamy policzone na rysunku i wynosi fib(3)=2, fib(4) również mamy policzone i wynosi fib(4)= 3, podstawiając liczby fib(5) = 2+3 = 5
Podstawiamy wszystkie policzone liczby fib(6) = fib(4) + fib(5) = 3+5 = 8
Uwaga! Rozwiązanie rekursywne jest bardzo wolne! Jest to spowodowane że niektóre wartości liczone są wielokrotnie.
06. Fibonacci Stream
public static long fibStream(int n) { return Stream.iterate(new int[]{1,1}, x -> new int[]{x[1], x[0]+x[1]}) .limit(n) .map(x->x[0]) .collect(Collectors.toList()) .get(n-1); }
Taka trochę ciekawostka że się po prostu da 😊 Nie uważam żeby to rozwiązanie było specjalnie atrakcyjne taka ciekawostka!
Podsumowanie
Ok! 3 całkowicie różne podejścia do rozwiązania danego problemu 🙂 Pamiętajcie że jeśli wasze może się różnić od mojego i nie ma w tym nic złego! Bonus! Na GitHubie dodałem porównanie wydajności poszczególnych metod, oraz jak Java radzi sobie z optymalizacją podobnych zadań 😉 fajnie to widać na Streamach!