Co programista Java powinien wiedzieć o liczbach Fibonacciego

Często podczas rozmów kwalifikacyjnych, szczególnie w firmach zagranicznych, można zapytać o algorytmy, a w stresującej sytuacji gorączkowe przypominanie sobie czegoś nie zawsze jest łatwe. Dlatego musisz się przygotować. Na początek przynajmniej odśwież pamięć podstawowych algorytmów. Dzisiaj przeanalizujemy takie zjawisko jak liczby Fibonacciego i najczęstsze warianty problemów z nimi związanych. Liczby Fibonacciego to ciąg liczb naturalnych rozpoczynający się od cyfr zero i jeden, a każda kolejna liczba jest równa sumie dwóch poprzednich: fa = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
fa ₀ = 0, fa ₁ = 1, fa _n = fa _{n - 1} + fa _{n - 2} ;
n ≥ 0, n ∈ Z

Warto zauważyć, że czasami pomija się 0, a szereg zaczyna się od 1 1 2 3... Z reguły w warunkach zadania od razu określa się, od których dwóch pierwszych liczb zaczyna się szereg (0,1 lub 1,1), więc dalej rozważymy rozwiązania dla obu przypadków.

Uzyskiwanie pierwszych n liczb Fibonacciego w Javie

Załóżmy, że mamy zadanie uzyskania n pierwszych liczb Fibonacciego.

• przypadek 0.1:

  Przychodzi do nas pewna liczba n:

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Tworzymy tablicę o rozmiarze n. Pierwsze dwa elementy będą równe zero i jeden, a pozostałe elementy uzyskamy przechodząc przez tę pętlę i korzystając z poprzednich liczb z tablicy.

  I wyświetlamy:

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  Ustaw int n = 10;

  I otrzymujemy:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• w przypadku 1.1 rozwiązanie właściwie nie jest inne:

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Jedyne, co musieliśmy zmienić, to pierwszy element tablicy arr[0]: z 0 na 1. Odpowiednio pierwszymi 10 elementami będzie:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Pierwsze n liczb Fibonacciego w strumieniu

Chcemy jednak pokazać nasz poziom. Zobaczmy więc, jak wyglądałoby to rozwiązanie przy użyciu stream .

• dla 0,1:

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  Statyczna metoda iteracyjna klasy Stream zwraca nieskończony uporządkowany strumień utworzony przez zastosowanie funkcji do początkowej tablicy arr. W naszym przypadku funkcja polega na ustaleniu reguły tworzenia każdej nowej tablicy na podstawie poprzedniej. W rezultacie otrzymamy strumień tablic:

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  Ale będzie ich nieskończona liczba, dlatego stosując .limit(n) redukujemy liczbę elementów do pierwszego n (w naszym przypadku do 10).

  Nie potrzebujemy jednak strumienia tablic, więc używając .map(y -> y[0]) wybieramy pierwszy element każdej tablicy, pobieramy strumień z potrzebnymi liczbami i drukujemy go na konsoli za pomocą forEach .

  Wygląda fajniej, prawda?

  z pierwszymi elementami wynoszącymi 1,1, ten kod będzie również prawie taki sam:

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  Ponownie różnice dotyczą elementu początkowego: zamiast {0, 1} ustawiamy {1, 1}

  Właściwie wyniki będą takie same jak w poprzednim przykładzie.

Suma liczb Fibonacciego

Co by było, gdybyśmy zostali poproszeni o obliczenie sumy liczb Fibonacciego aż do n-tego elementu włącznie? Nie powinno to nam sprawić żadnych trudności. Weźmy rozwiązanie ze strumieniem i zamień forEach na kilka innych metod:

• dla 0,1:

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  Używając .mapToInt(Integer::intValue) konwertujemy nasz strumień na numeryczny IntStream i używamy jego metody .sum() w celu uzyskania sumy wszystkich elementów.

• dla przypadku z 1,1 elementami początkowymi zamiast {0, 1} ustawiamy {1, 1}.

Uzyskanie n-tej liczby w ciągu Fibonacciego

Czasami zostaniesz poproszony o wydrukowanie nie serii liczb, ale konkretnie n-tej liczby w ciągu Fibonacciego. Z reguły to tylko ułatwia zadanie, ponieważ można łatwo dostosować do tego poprzednie rozwiązania. A co powiesz na rozwiązanie problemu poprzez rekurencję?

1. dla 0,1:

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   Aby uruchomić algorytm z wartością 0,1, należy określić, że przy próbie pobrania pierwszego elementu otrzymamy 0, a drugiego - 1. Tak naprawdę musimy, podobnie jak w poprzednich rozwiązaniach, ustawić dwa pierwsze elementy.

2. implementacja dla wersji 1.1 będzie nieco inna:

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   W tym przypadku wystarczy ustawić pierwszy element na 1, gdyż drugi element będzie taki sam i odpowiedź metody będzie taka sama.

   Jednocześnie ustawiamy reakcję metody na 0, bo jeśli jej nie ustawimy, to gdy jako argument przyjdzie 2, to ta sama metoda zostanie wywołana rekurencyjnie, ale z argumentem 0. Następnie zostanie uruchomiona ta sama metoda , ale z liczbami ujemnymi i tak dalej, aż do ujemnej nieskończoności. W rezultacie otrzymamy StackOverflowError .

Jednakże metoda rekurencyjna nie jest zalecana, ponieważ w przeciwieństwie do poprzednich metod, które działają w czasie liniowym O(n), wykonanie metody rekurencyjnej może zająć znacznie więcej czasu. Dlaczego? Metoda rekurencyjna może zająć dużo czasu, ponieważ w trakcie obliczeń funkcja będzie wywoływana wiele razy z tego samego argumentu. Na przykład podczas obliczania getFibonacciValue(7) funkcja będzie wykonywać rekurencyjne wywołania getFibonacciValue(5) i getFibonacciValue(6), oba wywołania rekurencyjne wywołają getFibonacciValue(4)), co spowoduje wielokrotne wywoływanie tych samych operacji. Na rozmowie kwalifikacyjnej możesz pokazać tę metodę jako rozwiązanie, ale jednocześnie porozmawiać o jej wadach i zaproponować w zamian inną metodę. Warto również zauważyć, że typ int w Javie pozwala na przechowywanie od -2147483648 do 2147483647, więc będziesz mógł obliczyć tylko pierwszych 46 liczb Fibonacciego: jeśli spróbujemy uzyskać kolejne 47, nastąpi przepełnienie i otrzymamy liczbę ujemną. Jeśli zamiast int zastosujemy typ danych long, będziemy w stanie poprawnie obliczyć pierwsze 91 liczb Fibonacciego. Aby obliczyć kolejne liczby Fibonacciego, należy skorzystać z klasy BigInteger, która implementuje logikę przechowywania i operacji arytmetycznych na naprawdę DUŻYCH liczbach.