Fibonacci-Reihe in Java Verwendung von Rekursion und Schleifen

Was ist die Fibonacci-Reihe in Java?

A Fibonacci-Serie in Java Die Fibonacci-Folge ist eine Zahlenfolge, in der die nächste Zahl die Summe der beiden vorhergehenden Zahlen ist. Die ersten beiden Zahlen der Fibonacci-Folge sind 0 und 1. Die Fibonacci-Zahlen spielen eine wichtige Rolle bei der Laufzeitanalyse des Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier ganzer Zahlen.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Als Formel ausgedrückt lautet die Regel F(n) = F(n-1) + F(n-2), wobei F(0) = 0 und F(1) = 1. Die folgende Tabelle zeigt, wie die ersten acht Glieder berechnet werden.

Fibonacci-Reihenprogramm in Java Verwenden einer For-Schleife

Die iterative Version speichert zu jedem Zeitpunkt nur zwei Werte im Speicher, weshalb sie in linearer Zeit und konstantem Speicherplatz läuft.

//Using  For Loop
public class FibonacciExample {
	public static void main(String[] args)
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10;
		 int previousNumber = 0;
		 int nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */


	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
	}
}

Ausgang:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Programmlogik:

• previousNumber wird mit 0 initialisiert und nextNumber mit 1.
• Die Fibonacci-for-Schleife durchläuft die maxNumber:
  • Die vorherige Nummer anzeigen.
  • Berechne die Summe von previousNumber und nextNumber.
  • Aktualisiere die neuen Werte von previousNumber und nextNumber.

Fibonacci-Reihenprogramm in Java Verwenden der While-Schleife

Sie können auch ein/eine generieren Java Fibonacci-Folge unter Verwendung einer while einhängen JavaDie Arithmetik ist identisch, nur die Schleifensyntax ändert sich.

//Using  While Loop
public class FibonacciWhileExample {
	public static void main(String[] args)
	{
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");

	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }

	}

}

Ausgang:

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Der einzige Unterschied in der Programmlogik besteht in der Verwendung einer while-Schleife zur Ausgabe der Fibonacci-Zahlen. Der Zähler muss vor der Schleife deklariert und innerhalb der Schleife inkrementiert werden, da die Schleife sonst nie endet.

Fibonacci-Reihe basierend auf der Benutzereingabe

Die feste Codierung der Termanzahl ist für Demonstrationszwecke praktisch, in realen Übungen wird der Wert jedoch üblicherweise von der Tastatur eingelesen. Die Scanner-Klasse erledigt dies in drei Zeilen, die Generierungslogik bleibt dabei unverändert.

//fibonacci series based on the user input
import java.util.Scanner;

public class FibonacciUserInput {

    public static void main(String[] args)
    {
        int maxNumber = 0;
        int previousNumber = 0;
        int nextNumber = 1;

        System.out.println("How many numbers you want in Fibonacci:");
        Scanner scanner = new Scanner(System.in);
        maxNumber = scanner.nextInt();
        System.out.print("Fibonacci Series of " + maxNumber + " numbers:");

        for (int i = 1; i <= maxNumber; ++i)
        {
            System.out.print(previousNumber + " ");
            /* On each iteration, we are assigning the second number
             * to the first number and assigning the sum of the last two
             * numbers to the second number
             */

            int sum = previousNumber + nextNumber;
            previousNumber = nextNumber;
            nextNumber = sum;
        }

        scanner.close();
    }
}

Beispielausführung:

How many numbers you want in Fibonacci:
7
Fibonacci Series of 7 numbers:0 1 1 2 3 5 8

Programmlogik:
Die Logik ist dieselbe wie zuvor. Anstatt die Anzahl der anzuzeigenden Elemente fest zu kodieren, wird nun Folgendes verwendet: Java Fibonacci-Folge, der Benutzer wird aufgefordert, eine Zahl einzugeben.

Fibonacci-Reihe mit Rekursion in Java

Unten sehen Sie ein Fibonacci-Reihenprogramm in Java mit Rekursion:

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

Ausgang:

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

Programmlogik:

Eine rekursive Funktion ist eine Funktion, die sich selbst aufrufen kann.

fibonacciRecursion():

1. Das Java Die Fibonacci-Rekursionsfunktion nimmt eine Eingabezahl entgegen. Sie prüft auf 0, 1 und 2 und gibt jeweils 0, 1 und 1 zurück, da die Fibonacci-Folge in Java beginnt mit 0, 1, 1.
2. Wenn der Eingabewert n gleich 3 oder größer ist, ruft sich die Funktion rekursiv selbst auf. Der Aufruf erfolgt zweimal. tracIm Folgenden wird nach einer Eingabe von 4 gefragt.

fibonacciRecursion(4)
    = fibonacciRecursion(2) + fibonacciRecursion(3)

    fibonacciRecursion(2) = 1                    // base case, no further calls
    fibonacciRecursion(3) = fibonacciRecursion(1) + fibonacciRecursion(2)
                          = 1 + 1
                          = 2

    Result: 1 + 2 = 3

Die Basisfälle stoppen den Abstieg. Da 1 und 2 beide sofort zurückkehren, expandiert der Zweig für fibonacciRecursion(2) nie weiter, wodurch die trace endlich.

Optimierte Fibonacci-Folge mittels Memoisation

Einfache Rekursion berechnet dieselben Terme viele Male neu. Die Berechnung des 40. Terms erfordert mehr als 200 Millionen Aufrufe. Durch das Speichern jedes Ergebnisses bei der ersten Berechnung wird diese Duplizierung vollständig vermieden.

public class FibonacciMemo {

    static long[] cache;

    public static long fib(int n) {
        if (n <= 1) {
            return n;
        }
        // return the stored value when it exists
        if (cache[n] != 0) {
            return cache[n];
        }
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }

    public static void main(String[] args) {
        int maxNumber = 90;
        cache = new long[maxNumber + 1];

        System.out.println("Term 50 is: " + fib(50));
        System.out.println("Term 90 is: " + fib(90));
    }
}

Ausgang:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Vergleich der Fibonacci-Methoden in Java

Alle vier Programme geben die gleiche Sequenz aus, daher hängt die Entscheidung davon ab, wie viele Terme benötigt werden.

Das gleiche Zähler- und Akkumulatormuster taucht in mehreren verwandten Übungen auf. Fahren Sie mit der Java Palindromprogramm, hat das Java Programm zur Überprüfung einer Primzahlund die Programm zum Ausgeben von Primzahlen von 1 bis 100Für die Array-basierte Praxis siehe Bubble Sortieren in Java und Java Arraysund überprüfen Sie die für jede Schleife in Java für alternative Schleifensyntax.

Häufig gestellte Fragen