Fibonacci-serien i Java brug af rekursion og løkker

Hvad er Fibonacci-serien i Java?

A Fibonacci-serien in Java er en talrække, hvor det næste tal er summen af ​​de to foregående tal. De første to tal i Fibonacci-rækken er 0 og 1. Fibonaccitallene bruges i vid udstrækning i den beregningsmæssige runtime-undersøgelse af algoritmen, der bestemmer den største fælles divisor af to heltal.

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

Udtrykt som en formel er reglen F(n) = F(n-1) + F(n-2), hvor F(0) = 0 og F(1) = 1. Tabellen nedenfor viser, hvordan de første otte led frembringes.

Fibonacci-seriens program i Java bruger For Loop

Den iterative version gemmer kun to værdier i hukommelsen ad gangen, hvilket er grunden til, at den kører i lineær tid og konstant rum.

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

Program logik:

• forrigeNummer initialiseres til 0, og næsteNummer initialiseres til 1.
• Fibonacci-løkken itererer igennem maxNumber:
  • Vis det forrige nummer.
  • Beregn summen af ​​forrige tal og næste tal.
  • Opdater de nye værdier for previousNumber og nextNumber.

Fibonacci-seriens program i Java bruger While Loop

Du kan også generere en Java Fibonacci-rækker ved hjælp af en while sløjfe ind JavaAritmetikken er identisk, og kun løkkesyntaksen ændres.

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

Den eneste forskel i programlogikken er brugen af ​​en while-løkke til at udskrive Fibonacci-tallene. Tælleren skal deklareres før løkken og øges indeni den, ellers slutter løkken aldrig.

Fibonacci-serien baseret på brugerinput

Det er praktisk at hardkode termantallet til en demonstration, men rigtige øvelser læser normalt værdien fra tastaturet. Scanner-klassen håndterer det i tre linjer, og genereringslogikken forbliver uændret.

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

Prøvekørsel:

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

Program logik:
Logikken er den samme som tidligere. I stedet for at fastkode antallet af elementer, der skal vises i Java Fibonacci-rækken, bliver brugeren bedt om at indtaste et tal.

Fibonacci-serien, der bruger rekursion i Java

Nedenfor er et program i Fibonacci-serien Java ved hjælp af 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) +" ");
		}
	}
}

Output:

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

Program logik:

En rekursiv funktion er en funktion, der har evnen til at kalde sig selv.

fibonacciRecursion():

1. Java Fibonacci-rekursionsfunktionen tager et inputtal. Den tjekker for 0, 1 og 2 og returnerer henholdsvis 0, 1 og 1, fordi Fibonacci-sekvensen i Java starter med 0, 1, 1.
2. Når inputtet n er 3 eller større, kalder funktionen sig selv rekursivt. Kaldet foretages to gange. trace nedenfor følger opfordringen til et input på 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

Basistilfældene stopper nedstigningen. Fordi 1 og 2 begge vender tilbage med det samme, udvider grenen for fibonacciRecursion(2) sig aldrig yderligere, hvilket er det, der holder trace endelig.

Optimerede Fibonacci-serier ved hjælp af memoisering

Almindelig rekursion genberegner de samme termer mange gange. Beregning af term 40 kræver mere end 200 millioner kald. Ved at gemme hvert resultat første gang det beregnes, fjernes denne duplikering fuldstændigt.

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

Sammenligning af Fibonacci-metoder i Java

Alle fire programmer udskriver den samme sekvens, så beslutningen afhænger af, hvor mange termer der er nødvendige.

Det samme tæller- og akkumulatormønster forekommer i flere relaterede øvelser. Fortsæt med Java palindromprogram, Java program til at kontrollere et primtal, og Program til at udskrive primtal fra 1 til 100For array-baseret øvelse, se Bubble Sortér i Java og Java arrays, og gennemgå for hver løkke i Java for alternativ løkkesyntaks.

Ofte Stillede Spørgsmål