Serie di Fibonacci in Java Utilizzo della ricorsione e dei cicli

In cosa consiste la serie di Fibonacci Java?

A Serie di Fibonacci in Java La successione di Fibonacci è una serie di numeri in cui il numero successivo è la somma dei due numeri precedenti. I primi due numeri della successione di Fibonacci sono 0 e 1. I numeri di Fibonacci sono ampiamente utilizzati nello studio computazionale dei tempi di esecuzione dell'algoritmo che determina il massimo comune divisore di due numeri interi.

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

Espressa come formula, la regola è F(n) = F(n-1) + F(n-2), con F(0) = 0 e F(1) = 1. La tabella seguente mostra come vengono prodotti i primi otto termini.

Programma della serie di Fibonacci in Java utilizzando il ciclo For

La versione iterativa mantiene in memoria solo due valori alla volta, motivo per cui la sua esecuzione ha una complessità temporale lineare e un'efficienza spaziale costante.

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

Produzione:

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

Logica del programma:

• previousNumber viene inizializzato a 0 e nextNumber viene inizializzato a 1.
• Il ciclo for di Fibonacci itera attraverso maxNumber:
  • Visualizza il numero precedente.
  • Calcola la somma di previousNumber e nextNumber.
  • Aggiorna i nuovi valori di previousNumber e nextNumber.

Programma della serie di Fibonacci in Java utilizzando il ciclo While

Puoi anche generare un Java serie di Fibonacci utilizzando un while entrare JavaI calcoli sono identici, cambia solo la sintassi del ciclo.

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

	}

}

Produzione:

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

L'unica differenza nella logica del programma è l'utilizzo di un ciclo while per stampare i numeri di Fibonacci. Il contatore deve essere dichiarato prima del ciclo e incrementato al suo interno, altrimenti il ​​ciclo non termina mai.

Serie di Fibonacci basate sull'input dell'utente

Inserire manualmente il conteggio dei termini è comodo per una dimostrazione, ma negli esercizi reali il valore viene solitamente letto da tastiera. La classe Scanner gestisce questa operazione in tre righe, e la logica di generazione rimane invariata.

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

Esecuzione di esempio:

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

Logica del programma:
La logica è la stessa di prima. Invece di codificare in modo fisso il numero di elementi da mostrare nel Java Serie di Fibonacci: all'utente viene chiesto di inserire un numero.

Serie di Fibonacci utilizzando la ricorsione in Java

Di seguito è riportato un programma della serie di Fibonacci in Java utilizzando la ricorsione:

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

Produzione:

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

Logica del programma:

Una funzione ricorsiva è una funzione che ha la capacità di richiamare se stessa.

ricorsione di fibonacci():

1. Migliori Java La funzione ricorsiva di Fibonacci prende un numero in input. Controlla se è 0, 1 e 2 e restituisce rispettivamente 0, 1, 1, perché la sequenza di Fibonacci in Java inizia con 0, 1, 1.
2. Quando l'input n è 3 o maggiore, la funzione chiama se stessa ricorsivamente. La chiamata viene effettuata due volte. trace di seguito segue la richiesta di un input di 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

I casi base arrestano la discesa. Poiché 1 e 2 restituiscono entrambi immediatamente, il ramo per fibonacciRecursion(2) non si espande mai ulteriormente, ed è questo che mantiene il trace finito.

Serie di Fibonacci ottimizzata tramite memorizzazione

La ricorsione semplice ricalcola gli stessi termini molte volte. Il calcolo del termine 40 richiede oltre 200 milioni di chiamate. Memorizzare ogni risultato la prima volta che viene calcolato elimina completamente questa duplicazione.

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

Produzione:

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Confronto dei metodi di Fibonacci in Java

Tutti e quattro i programmi stampano la stessa sequenza, quindi la decisione dipende dal numero di termini necessari.

Lo stesso schema di contatore e accumulatore appare in diversi esercizi correlati. Continua con il Java programma palindromo, il Java programma per verificare un numero primo Programma per stampare i numeri primi da 1 a 100Per la pratica basata sugli array, vedere Bubble Ordina in Java and Java array, e rivedere il per ogni ciclo in Java per una sintassi di ciclo alternativa.

DOMANDE FREQUENTI