Was ein Java-Programmierer über Fibonacci-Zahlen wissen sollte

Bei Vorstellungsgesprächen, insbesondere bei ausländischen Unternehmen, werden die Leute häufig nach Algorithmen gefragt, und in einer Stresssituation ist es nicht immer einfach, sich hektisch an etwas zu erinnern. Daher müssen Sie sich vorbereiten. Frischen Sie zunächst zumindest Ihr Gedächtnis über die grundlegenden Algorithmen auf. Heute werden wir ein Phänomen wie die Fibonacci-Zahlen und die häufigsten damit verbundenen Problemvarianten analysieren. Fibonacci-Zahlen sind eine Folge natürlicher Zahlen, die mit den Zahlen Null und Eins beginnt und jede nachfolgende Zahl gleich der Summe der beiden vorherigen ist: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈ Z

Es ist erwähnenswert, dass manchmal 0 weggelassen wird und die Reihe mit 1 1 2 3 beginnt... In den Bedingungen der Aufgabe wird in der Regel sofort angegeben, mit welchen ersten beiden Zahlen die Reihe beginnt (0,1 oder 1,1), Daher werden wir im Folgenden Lösungen für beide Fälle prüfen.

Erste n Fibonacci-Zahlen in Java ermitteln

Angenommen, wir haben die Aufgabe, die ersten n Fibonacci-Zahlen zu ermitteln.

• Fall 0.1:

  Eine bestimmte Zahl n kommt zu uns:

  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];
  }

  Wir erstellen ein Array der Größe n. Die ersten beiden Elemente sind gleich Null und Eins, und die restlichen Elemente werden erhalten, indem man diese Schleife durchläuft und die vorherigen Zahlen aus dem Array verwendet.

  Und wir zeigen:

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

  Setze int n = 10;

  Und wir bekommen:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• Für Fall 1.1 ist die Lösung eigentlich nicht anders:

  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];
  }

  Alles, was wir ändern mussten, war das erste Element des Arrays arr[0]: von 0 auf 1. Dementsprechend sind die ersten 10 Elemente:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Erste n Fibonacci-Zahlen per Stream

Aber wir wollen unser Niveau zeigen. Sehen wir uns also an, wie diese Lösung mit stream aussehen würde .

• für 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));

  Die statische Iterate-Methode der Stream- Klasse gibt einen unendlich geordneten Stream zurück, der durch Anwenden der Funktion auf das anfängliche Array arr erstellt wird. In unserem Fall besteht die Funktion darin, die Regel für die Zusammenstellung jedes neuen Arrays basierend auf dem vorherigen festzulegen. Als Ergebnis erhalten wir einen Stream von Arrays:

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

  Aber es wird unendlich viele davon geben, und deshalb reduzieren wir mit .limit(n) die Anzahl der Elemente auf das erste n (in unserem Fall auf 10).

  Allerdings benötigen wir keinen Stream von Arrays, also wählen wir mit .map(y -> y[0]) das erste Element jedes Arrays aus, erhalten einen Stream mit den benötigten Zahlen und geben ihn mit forEach auf der Konsole aus .

  Sieht cooler aus, oder?

  Da die ersten Elemente 1,1 sind, ist dieser Code auch fast derselbe:

  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));

  Auch hier liegen die Unterschiede im Anfangselement: Anstelle von {0, 1} setzen wir {1, 1}

  Tatsächlich werden die Ergebnisse dieselben sein wie im vorherigen Beispiel.

Summe der Fibonacci-Zahlen

Was wäre, wenn wir gebeten würden, die Summe der Fibonacci-Zahlen bis zum n-ten Element einschließlich zu ermitteln? Dies sollte uns keine Schwierigkeiten bereiten. Nehmen wir eine Lösung mit einem Stream und ersetzen Sie forEach durch ein paar andere Methoden:

• für 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);

  Mit .mapToInt(Integer::intValue) konvertieren wir unseren Stream in einen numerischen IntStream und verwenden seine .sum()-Methode, um die Summe aller Elemente zu erhalten.

• Für den Fall mit 1,1 Anfangselementen setzen wir statt {0, 1} {1, 1}.

Ermitteln der n-ten Zahl in der Fibonacci-Reihe

Manchmal werden Sie aufgefordert, nicht eine Zahlenreihe, sondern speziell die n-te Zahl in der Fibonacci-Reihe zu drucken. Dies erleichtert in der Regel nur die Aufgabe, da Sie bisherige Lösungen hierfür problemlos anpassen können. Nun, wie wäre es mit der Lösung des Problems durch Rekursion?

1. für 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);
     }
   }

   Um den Algorithmus mit 0,1 auszuführen, muss angegeben werden, dass wir beim Versuch, das erste Element zu erhalten, 0 und das zweite 1 erhalten. Tatsächlich müssen wir, wie in vorherigen Lösungen, die ersten beiden festlegen Elemente.

2. Die Implementierung für 1.1 wird etwas anders sein:

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

   In diesem Fall müssen wir nur das erste Element auf 1 setzen, da das zweite Element dasselbe ist und die Antwort der Methode dieselbe ist.

   Gleichzeitig setzen wir die Reaktion der Methode auf 0, denn wenn wir sie nicht setzen, wird bei 2 als Argument dieselbe Methode rekursiv aufgerufen, jedoch mit Argument 0. Als nächstes wird dieselbe Methode gestartet , aber mit negativen Zahlen und so weiter bis zur negativen Unendlichkeit. Als Ergebnis erhalten wir einen StackOverflowError .

Die rekursive Methode wird jedoch nicht empfohlen, da die rekursive Methode im Gegensatz zu den vorherigen Methoden, die in linearer O(n)-Zeit ausgeführt werden, erheblich länger dauern kann. Warum? Die rekursive Methode kann lange dauern, da die Funktion während des Berechnungsprozesses viele Male mit demselben Argument aufgerufen wird. Wenn die Funktion beispielsweise getFibonacciValue(7) auswertet, führt sie rekursive Aufrufe an getFibonacciValue(5) und getFibonacciValue(6) durch. Beide rekursiven Aufrufe rufen getFibonacciValue(4) auf, was dazu führt, dass dieselben Operationen mehrmals aufgerufen werden. Im Vorstellungsgespräch können Sie diese Methode als Lösung aufzeigen, gleichzeitig aber auch über ihre Mängel sprechen und im Gegenzug eine andere Methode anbieten. Es ist auch erwähnenswert, dass der int-Typ in Java das Speichern von -2147483648 bis 2147483647 ermöglicht, sodass Sie nur die ersten 46 Fibonacci-Zahlen berechnen können: Wenn wir versuchen, die nächste 47. zu erhalten, kommt es zu einem Überlauf und wir erhalten eine negative Zahl. Wenn wir den Datentyp long anstelle von int verwenden, können wir die ersten 91 Fibonacci-Zahlen korrekt berechnen. Um nachfolgende Fibonacci-Zahlen zu berechnen, müssen Sie die Klasse BigInteger verwenden, die die Logik zum Speichern und für arithmetische Operationen wirklich GROßER Zahlen implementiert.