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! 😊

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

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!

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.

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ść 😊

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.

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!

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!