Implémentation de la suite de Fibonacci

Aujourd’hui nous allons voir comment implémenter la suite de Fibonacci de façon simple.

Description mathématique  

La suite de Fibonacci est une suite d’entier dont la valeur de chaque terme est égale à la somme des valeurs des deux termes précédents. C’est donc une suite récurrente.

Par convention on a l’habitude de définir le premier terme par 0 ou par 1, dans notre cas nous initialiserons les deux premières valeurs de la suite par 0 et 1. Nous obtiendrons donc par exemple pour les 7 premiers éléments de la suite : 0;1;1;2;3;5;8. En effet, si on appelle E_x le x^ième terme de la suite on aura :

x₀ = 0 (Convention)

x₁ =  1 (Convention)

x₂ = 0 + 1 = 1

x₃ = 1 + 1= 2

x₄ = 1 + 2 = 3

x₅ = 2 + 3 = 5

x₆ = 3 + 5 = 8

 On peut donc établir la formule de récurrence : 

Pour tout n supérieur ou égal à 0 : 

x₀=0

x₁=1

x_n+2=x_n+x_n+1

 Ou encore : x_n=x_n-2+x_n-1

Implémentation 

Déclaration des variables : 

– On déclare une variable ind de type entier qui nous servira d’indice.

– On déclare une variable de type entier qui va recevoir les valeurs successives de la suite de Fibonacci : fib

– On déclare deux variables de type entier qui vont garder en mémoire les deux termes précédents l’élément de fibonacci que l’on calcule : terme_prec1 et terme_prec2

terme_prec1 sera le terme à l’étape i-1 et terme_prec2 sera le terme de l’étape i-2

– On déclare enfin une variable qui va contenir le nombre d’éléments de la suite que l’utilisateur souhaite afficher.

Remarque :  Dans notre algorithme, nous n’afficherons pas les termes d’initialisation donc par exemple, si l’utilisateur demande d’afficher les 5 premiers éléments de la suite, le résultat sera : 1;2;3;5;8

public class Fibonacci {
   
  
  public static void main(String [] args)  {
  
    int ind;
    int nb_element;
  
    int fib = 1;
    int terme_prec1 = 2;
    int terme_prec2 = 1;
}

Intéraction avec l’utilisateur

Nous allons demander à l’utilisateur de saisir le nombre d’éléments qu’il souhaite afficher et récupérer sa saisie clavier. (on utilisera à nouveau la classe clavier disponible en pièce jointe mais vous pouvez utiliser un scanner standard).

Et nous allons afficher le message de sortie.

System.out.println("Nombre de nombres de Fibonacci a calculer?");
    nb_element = Clavier.saisirInt();
	System.out.println("Les "+nb_element+" premiers éléments de la suite de Fibonacci sont : ");
    

Algorithme de la suite de Fibonacci

Nous allons maintenant écrire l’algorithme qui permettra à l’ordinateur de calculer les éléments successifs de la suite. On aura donc :

Terme de Fibonacci à l’étape n = Terme de Fibonacci à l’étape n-1 + Terme de Fibonacci à l’étape n-1

Soit avec nos notations :

fib=terme_prec1 + terme_prec2;

Et on prépare l’étape suivante, l’élément terme_prec2 devient l’élément terme_prec1 et l’élément terme_prec1 devient l’élément fib.

fib = terme_prec1 + terme_prec2;
terme_prec2 = terme_prec1;
terme_prec1 = fib;

Remarque : On va initialiser manuellement les 2 premiers termes de la suite on aurait très bien pu déclarer deux variables ini1=0 et ini2=1 et démarrer le calcul directement.

Ce qui nous donne :

for ( ind = 1 ; ind <= nb_element ; ind++ ) {
  
      if ( ind == 2 ) {
        fib = 2; }
  
      if ( ind > 2 ) {
        fib = terme_prec1 + terme_prec2;
        terme_prec2 = terme_prec1;
        terme_prec1 = fib; }
  
      System.out.print(fib+";"); }
  }

Pièce jointe : Class Clavier