Implémentation de la suite de Fibonacci

book
date_range
comment0 commentaire
remove_red_eye9696 vues

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 Ex le xième terme de la suite on aura : 

x0 = 0 (Convention)

x1 =  1 (Convention)

x2 = 0 + 1 = 1

x3 = 1 + 1= 2

x4 = 1 + 2 = 3

x5 = 2 + 3 = 5

x6 = 3 + 5 = 8

 

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

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

x0=0

x1=1

 

xn+2=xn+xn+1

 Ou encore : xn=xn-2+xn-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

Articles similaires

Commentaires

Aucun commentaire

Ajouter un commentaire

Vous ne disposez pas les autorisations nécessaires pour poster un commentaire.