Série de Fibonacci dans Java Utilisation de la récursivité et des boucles

Qu'est-ce que la série de Fibonacci Java?

A Série Fibonacci in Java La suite de Fibonacci est une série de nombres où chaque nombre est la somme des deux précédents. Les deux premiers nombres de la suite de Fibonacci sont 0 et 1. Les nombres de Fibonacci sont largement utilisés dans l'étude du temps d'exécution de l'algorithme qui détermine le plus grand commun diviseur de deux entiers.

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

Exprimée sous forme de formule, la règle est F(n) = F(n-1) + F(n-2), avec F(0) = 0 et F(1) = 1. Le tableau ci-dessous montre comment les huit premiers termes sont produits.

Programme de la série Fibonacci dans Java en utilisant la boucle For

La version itérative ne conserve que deux valeurs en mémoire à un instant donné, ce qui explique son exécution en temps linéaire et en espace constant.

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

Sortie :

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

Logique du programme :

• previousNumber est initialisé à 0 et nextNumber est initialisé à 1.
• La boucle for de Fibonacci itère sur maxNumber:
  • Afficher le numéro précédent.
  • Calculez la somme de previousNumber et nextNumber.
  • Mettez à jour les nouvelles valeurs de previousNumber et nextNumber.

Programme de la série Fibonacci dans Java en utilisant la boucle While

Vous pouvez également générer un Java Suite de Fibonacci utilisant une while boucle dans JavaLes calculs arithmétiques sont identiques, seule la syntaxe de la boucle change.

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

	}

}

Sortie :

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

La seule différence dans la logique du programme réside dans l'utilisation d'une boucle while pour afficher les nombres de Fibonacci. Le compteur doit être déclaré avant la boucle et incrémenté à l'intérieur de celle-ci, sinon la boucle ne se termine jamais.

Série de Fibonacci basée sur la saisie de l'utilisateur

Le codage en dur du nombre de termes est pratique pour une démonstration, mais dans les exercices réels, la valeur est généralement lue au clavier. La classe Scanner gère cela en trois lignes, et la logique de génération reste inchangée.

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

Exemple d'exécution :

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

Logique du programme :
La logique est la même qu'auparavant. Au lieu de coder en dur le nombre d'éléments à afficher dans le Java Dans la suite de Fibonacci, l'utilisateur est invité à saisir un nombre.

Série de Fibonacci utilisant la récursivité dans Java

Vous trouverez ci-dessous un programme de série de Fibonacci en Java en utilisant la récursivité :

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

Sortie :

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

Logique du programme :

Une fonction récursive est une fonction qui a la capacité de s'appeler elle-même.

fibonacciRecursion() :

1. Le Java La fonction de récursion de Fibonacci prend un nombre en entrée. Elle vérifie si ce nombre est 0, 1 ou 2 et renvoie respectivement 0, 1 et 1, car la suite de Fibonacci… Java commence par 0, 1, 1.
2. Lorsque l'entrée n est supérieure ou égale à 3, la fonction s'appelle elle-même de manière récursive. L'appel est effectué deux fois. tracLe texte ci-dessous fait suite à l'appel pour une entrée de 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

Les cas de base interrompent la descente. Comme 1 et 2 retournent immédiatement, la branche de fibonacciRecursion(2) ne se développe jamais davantage, ce qui empêche la progression de se poursuivre. trace fini.

Suite de Fibonacci optimisée par mémoïsation

La récursivité simple recalcule les mêmes termes de nombreuses fois. Le calcul du terme 40 nécessite plus de 200 millions d'appels. Stocker chaque résultat lors de son premier calcul élimine complètement cette duplication.

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

Sortie :

Term 50 is: 12586269025
Term 90 is: 2880067194370816120

Comparaison des méthodes de Fibonacci dans Java

Les quatre programmes impriment la même séquence, la décision dépend donc du nombre de termes nécessaires.

Le même schéma de compteur et d'accumulateur apparaît dans plusieurs exercices connexes. Continuez avec le Java programme palindrome, le Java programme pour vérifier si un nombre premierainsi que, Programme pour afficher les nombres premiers de 1 à 100Pour des exercices basés sur les tableaux, voir Bubble Trier dans Java et Java tableaux, et passez en revue le pour chaque boucle dans Java pour une syntaxe de boucle alternative.

FAQ