Fibonacci, Integer-Überlauf, Auswendiglernen und Übertreibung

Lass uns eine Übung machen.
Unten hinterlasse ich einen Code, der die Zahl an Position n der Fibonacci-Folge zurückgibt:

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

Wie wäre es, wenn wir versuchen würden, in unserem Terminal alle Zahlen der Fibonacci-Folge anzuzeigen, die kleiner als 2147483647 sind?

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Die Probleme

Beim Ausführen des Codes werden Sie zwei Hauptprobleme bemerken:

• Unsere Schleife endet nie und seltsamerweise beginnen negative Zahlen in der Konsole zu erscheinen.
  

• Der Code wird mit der Zeit immer langsamer.

Problem 1: Negative Zahlen

Ignorieren Sie diesen ganzen Fibonacci-Zeug für einen Moment und schauen Sie sich diesen Code an.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

Wie hoch wird Ihrer Meinung nach das Ergebnis sein? 2 Milliarden 2 Milliarden = 4 Milliarden, oder? In unserem Code wird das Ergebnis also 4 Milliarden sein ... richtig?

FALSCH!

Der Ausweg war eigentlich dieser:

Der Grund für dieses Ergebnis ist ein Überlauf. Der int-Typ hat eine Höchstgrenze von 2147483647 (oder 2^31 - 1). Wenn dieser Grenzwert überschritten wird, „kehrt“ der Wert zum niedrigstmöglichen Wert vom Typ int zurück, nämlich -2147483648.

Warum hat unsere Schleife nicht aufgehört?

Unsere Schleife sollte stoppen, wenn wir eine Zahl größer oder gleich 2147483647 erreichten, aber als die Fibonacci-Werte das int-Limit überschritten, begannen negative Zahlen zu generiert werden. Da wir nie eine Zahl größer als 2147483647 erreichten, stoppte die Schleife nie.

Lösung für Problem 1

Der Einfachheit halber ändere ich einfach den Rückgabetyp unserer Fib-Funktion von int in long, was ein viel größeres Limit hat. Unser Code wird so aussehen:

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Jetzt können wir mit dem langen Typ die Fibonacci-Zahlen bis zur größten Zahl, die kleiner als 2147483647 ist, korrekt drucken.

Lösung von Problem 2: Langsamkeit

Ist dir schon etwas aufgefallen? Bei jeder Iteration unserer Schleife berechnet die fib-Funktion alle vorherigen Zahlen in der Sequenz neu. Mit anderen Worten: Wir wiederholen unnötige Berechnungen.

Wie vermeide ich unnötige Neuberechnungen? Ich präsentiere Ihnen: Memoisierung. Die Memoisierungstechnik ist eine Möglichkeit, bereits berechnete Ergebnisse zu speichern, um den Berechnungsprozess nicht erneut durchlaufen zu müssen.

Lassen Sie uns eine HashMap implementieren, um die bereits gefundenen Werte zu speichern, wobei der Schlüssel die Position und der Wert die Zahl selbst ist.

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Wunderschön! Jetzt läuft unser Code viel schneller und wir haben unser Problem gelöst.

Die Übertreibung

Eigentlich war das Auswendiglernen hier nicht nötig. Ich wollte dieses Konzept einfach in den Unterricht bringen. Wir könnten einfach jede Fibonacci-Zahl berechnen, bis wir unsere Bedingung wie folgt abgeschlossen haben:

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

Ich bin mit dem Spaß fertig, oder? Entschuldigung! Aber zumindest hast du etwas Neues gelernt.

Artikelcover von: Gerd Altmann von Pixabay

Das obige ist der detaillierte Inhalt vonFibonacci, Integer-Überlauf, Auswendiglernen und Übertreibung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!