Fibonacci-reeks in Java gebruikmakend van recursie en lussen

Wat is de Fibonacci-reeks? Java?

A Fibonacci-serie in Java De Fibonacci-reeks is een reeks getallen waarbij het volgende getal de som is van de twee voorgaande getallen. De eerste twee getallen van de Fibonacci-reeks zijn 0 en 1. De Fibonacci-getallen worden veelvuldig gebruikt in de studie naar de rekentijd van het algoritme dat de grootste gemene deler van twee gehele getallen bepaalt.

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

De regel kan als formule worden uitgedrukt als F(n) = F(n-1) + F(n-2), waarbij F(0) = 0 en F(1) = 1. De onderstaande tabel laat zien hoe de eerste acht termen worden geproduceerd.

Fibonacci Series-programma in Java met behulp van For-lus

De iteratieve versie bewaart op elk moment slechts twee waarden in het geheugen, waardoor deze in lineaire tijd en met constante geheugenruimte werkt.

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

Output:

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

Programmalogica:

• previousNumber wordt geïnitialiseerd op 0 en nextNumber wordt geïnitialiseerd op 1.
• De Fibonacci-lus doorloopt de volgende stappen: maxNumber:
  • Toon het vorige nummer.
  • Bereken de som van previousNumber en nextNumber.
  • Werk de nieuwe waarden van previousNumber en nextNumber bij.

Fibonacci Series-programma in Java gebruik van While-lus

Je kunt ook een Java Fibonacci-reeks met behulp van een while lus in JavaDe rekenkundige bewerkingen zijn identiek, alleen de syntaxis van de lussen verandert.

//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++;
	        }

	}

}

Output:

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

Het enige verschil in de programmalogica is het gebruik van een while-lus om de Fibonacci-getallen af ​​te drukken. De teller moet vóór de lus worden gedeclareerd en binnen de lus worden verhoogd, anders eindigt de lus nooit.

Fibonacci-serie gebaseerd op de gebruikersinvoer

Het vastleggen van het aantal termen in de code is handig voor een demonstratie, maar in echte oefeningen wordt de waarde meestal van het toetsenbord gelezen. De Scanner-klasse handelt dat af in drie regels code, en de logica voor het genereren blijft ongewijzigd.

//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();
    }
}

Voorbeeld van een run:

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

Programmalogica:
De logica is hetzelfde als eerder. In plaats van het aantal elementen dat moet worden weergegeven vast te coderen in de Java De Fibonacci-reeks, de gebruiker wordt gevraagd een getal in te voeren.

Fibonacci-reeks met behulp van recursie in Java

Hieronder staat een programma uit de Fibonacci-reeks Java met behulp van recursie:

//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) +" ");
		}
	}
}

Output:

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

Programmalogica:

Een recursieve functie is een functie die zichzelf kan aanroepen.

fibonacciRecursie():

1. De Java De Fibonacci-recursiefunctie neemt een getal als invoer. Het controleert op 0, 1 en 2 en retourneert respectievelijk 0, 1 en 1, omdat de Fibonacci-reeks in Java begint met 0, 1, 1.
2. Als de invoer n 3 of groter is, roept de functie zichzelf recursief aan. De aanroep wordt twee keer gedaan. tracHieronder volgt de oproep voor een invoer van 4.

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

De basisgevallen stoppen de afdaling. Omdat 1 en 2 beide direct terugkeren, wordt de tak voor fibonacciRecursion(2) nooit verder uitgebreid, wat ervoor zorgt dat de trace eindig.

Geoptimaliseerde Fibonacci-reeks met behulp van memoization

Bij gewone recursie worden dezelfde termen vele malen opnieuw berekend. Het berekenen van term 40 vereist meer dan 200 miljoen aanroepen. Door elk resultaat direct na de eerste berekening op te slaan, wordt deze duplicatie volledig voorkomen.

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

Output:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Vergelijking van Fibonacci-methoden in Java

Alle vier programma's printen dezelfde reeks, dus de beslissing hangt af van hoeveel termen er nodig zijn.

Hetzelfde patroon van tellers en accumulatoren komt voor in verschillende verwante oefeningen. Ga verder met de Java palindroomprogramma Java programma om te controleren of een getal een priemgetal isen Programma om priemgetallen van 1 tot 100 af te drukken.Voor oefeningen met arrays, zie Bubble Sorteren in Java en Java arrays, en bekijk de voor elke lus in Java voor alternatieve lus-syntaxis.

Veelgestelde vragen