Ce qu'un programmeur Java devrait savoir sur les nombres de Fibonacci

Souvent, lors d'entretiens, notamment dans des entreprises étrangères, les gens peuvent être interrogés sur les algorithmes, et dans une situation de stress, se souvenir frénétiquement de quelque chose n'est pas toujours facile. Par conséquent, vous devez vous préparer. Pour commencer, rafraîchissez au moins votre mémoire des algorithmes de base. Aujourd'hui, nous analyserons un phénomène tel que les nombres de Fibonacci et les variantes les plus courantes des problèmes qui leur sont associés. Les nombres de Fibonacci sont une séquence de nombres naturels qui commence par les nombres zéro et un, et chaque nombre suivant est égal à la somme des deux précédents : F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0, n ∈Z

Il convient de noter que parfois 0 est omis et que la série commence par 1 1 2 3... En règle générale, dans les conditions du problème, il est immédiatement précisé par quels deux premiers nombres commence la série (0,1 ou 1,1), nous examinerons donc plus loin des solutions pour les deux cas.

Obtenir les n premiers nombres de Fibonacci en Java

Supposons que nous ayons pour tâche d’obtenir les n premiers nombres de Fibonacci.

• cas 0.1 :

  Un certain nombre n nous parvient :

  int[] arr = new int[n];
  arr[0] = 0;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Nous créons un tableau de taille n. Les deux premiers éléments seront égaux à zéro et un, et les éléments restants sont obtenus en parcourant cette boucle et en utilisant les nombres précédents du tableau.

  Et on affiche :

  for (int i = 0; i < arr.length; ++i) {
    System.out.println(arr[i]);
  }

  Définir int n = 10 ;

  Et on obtient :

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• pour le cas 1.1, la solution n'est en fait pas différente :

  int[] arr = new int[n];
  arr[0] = 1;
  arr[1] = 1;
  for (int i = 2; i < arr.length; ++i) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }

  Il suffisait de changer le premier élément du tableau arr[0] : de 0 à 1. En conséquence, les 10 premiers éléments seront :

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

N premiers nombres de Fibonacci via flux

Mais nous voulons montrer notre niveau. Voyons donc à quoi ressemblerait cette solution en utilisant stream .

• pour 0,1 :

  Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

  La méthode d'itération statique de la classe Stream renvoie un flux ordonné infini créé en appliquant la fonction au tableau initial arr. Dans notre cas, la fonction consiste à définir la règle de composition de chaque nouveau tableau, en fonction du précédent. En conséquence, nous obtiendrons un flux de tableaux :

  {0,1}
  {1,1}
  {1, 2}
  {2, 3}
  {3, 5}
  {5, 8}
  {8, 13}
  {13, 21}
  {21, 34}
  {34, 55}
  …..

  Mais il y en aura un nombre infini, et donc en utilisant .limit(n) on réduit le nombre d'éléments au premier n (dans notre cas à 10).

  Cependant, nous n'avons pas besoin d'un flux de tableaux, donc en utilisant .map(y -> y[0]) nous sélectionnons le premier élément de chaque tableau et obtenons un flux avec les nombres dont nous avons besoin et l'imprimons sur la console en utilisant forEach. .

  Ça a l'air plus cool, n'est-ce pas ?

  les premiers éléments étant 1,1, ce code sera également presque le même :

  Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

  Encore une fois, les différences résident dans l'élément initial : au lieu de {0, 1}, nous définissons {1, 1}

  En fait, les résultats seront les mêmes que dans l’exemple précédent.

Somme des nombres de Fibonacci

Et si on nous demandait d’obtenir la somme des nombres de Fibonacci jusqu’au nième élément inclus ? Cela ne devrait pas nous poser de difficultés. Prenons une solution avec un flux et remplaçons forEach par quelques autres méthodes :

• pour 0,1 :

  int n = 10;
  int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(t -> t[0])
       .mapToInt(Integer::intValue)
       .sum();
  System.out.println(result);

  En utilisant .mapToInt(Integer::intValue), nous convertissons notre flux en un IntStream numérique et utilisons sa méthode .sum() pour obtenir la somme de tous les éléments.

• pour le cas avec 1,1 éléments initiaux, au lieu de {0, 1} nous définissons {1, 1}.

Obtenir le nième nombre de la série de Fibonacci

Parfois, on vous demande d'imprimer non pas une série de nombres, mais spécifiquement le nième nombre de la série de Fibonacci. En règle générale, cela ne fait que faciliter la tâche, car vous pouvez facilement adapter les solutions précédentes à cet effet. Et si vous résolviez le problème par récursion ?

1. pour 0,1 :

   public int getFibonacciValue(int n) {
     if (n <= 1) {
        return 0;
     } else if (n == 2) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   Pour exécuter l'algorithme avec 0,1, il est nécessaire de préciser que lorsque nous essayons d'obtenir le premier élément, nous obtenons 0 et le second - 1. En fait, comme dans les solutions précédentes, nous devons définir les deux premiers éléments.

2. l'implémentation pour la version 1.1 sera légèrement différente :

   public int getFibonacciValue(int n) {
     if (n == 0) {
        return 0;
     } else if (n == 1) {
        return 1;
     } else  {
        return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
     }
   }

   Dans ce cas, il suffit de définir le premier élément sur 1, puisque le deuxième élément sera le même et la réponse de la méthode sera la même.

   En même temps, nous définissons la réaction de la méthode à 0, car si nous ne la définissons pas, alors lorsque 2 arrive en argument, la même méthode est appelée récursivement, mais avec l'argument 0. Ensuite, la même méthode sera lancée , mais avec des nombres négatifs, et ainsi de suite jusqu'à moins l'infini. En conséquence, nous recevrons un StackOverflowError .

Cependant, la méthode récursive n'est pas recommandée car contrairement aux méthodes précédentes, qui s'exécutent en temps linéaire O(n), la méthode récursive peut prendre beaucoup plus de temps. Pourquoi? La méthode récursive peut prendre beaucoup de temps, car pendant le processus de calcul, la fonction sera appelée plusieurs fois à partir du même argument. Par exemple, lors de l'évaluation de getFibonacciValue(7), la fonction effectuera des appels récursifs à getFibonacciValue(5) et getFibonacciValue(6), les deux appels récursifs appelleront getFibonacciValue(4)), ce qui entraînera l'appel des mêmes opérations plusieurs fois. Lors de l'entretien, vous pouvez présenter cette méthode comme une solution, mais en même temps parler de ses lacunes et proposer une autre méthode en retour. Il convient également de noter que le type int en Java permet de stocker de -2147483648 à 2147483647, vous ne pourrez donc calculer que les 46 premiers nombres de Fibonacci : si nous essayons d'obtenir le 47ème suivant, il y aura un débordement et nous obtiendrons un nombre négatif. Si nous utilisons le type de données long au lieu de int, nous pourrons calculer correctement les 91 premiers nombres de Fibonacci. Pour calculer les nombres de Fibonacci suivants, vous devez utiliser la classe BigInteger, qui implémente la logique de stockage et les opérations arithmétiques de très GRANDS nombres.