Fibonacci, débordement d'entier, mémorisation et un exagero

Faisons un exercice.
Ci-dessous je laisse un code qui renvoie le nombre en position n de la séquence de Fibonacci :

public static int fib(int n){
   if (n <= 1){
     return n;
   }
   return fib(n-1) + fib(n-2);
}

Que diriez-vous d'essayer d'afficher dans notre terminal tous les nombres de la séquence de Fibonacci inférieurs à 2147483647 ?

    public static int fib(int n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        int position = 1;
        int currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Les problèmes

Lors de l'exécution du code, vous remarquerez deux problèmes principaux :

• Notre boucle ne se termine jamais, et, étrangement, des nombres négatifs commencent à apparaître dans la console.
  

• Le code devient de plus en plus lent à mesure que le temps passe.

Problème 1 : nombres négatifs

Ignorez tous ces trucs de Fibonacci pendant un moment et regardez ce code.

public static void main(String[] args) {
   int a = 2_000_000_000;
   int b = 2_000_000_000;
   System.out.println(a + b);
}

À votre avis, quel sera le résultat de cela ? 2 milliards 2 milliards = 4 milliards, n'est-ce pas ? Donc dans notre code le résultat sera de 4 milliards... non ?

FAUX !

La solution était en fait la suivante :

La raison de ce résultat est le débordement. Le type int a une limite maximale de 2147483647 (ou 2^31 - 1). Lorsque cette limite est dépassée, la valeur "revient" à la valeur la plus basse possible de type int, qui est -2147483648.

Pourquoi notre boucle ne s'est-elle pas arrêtée ?

Notre boucle était censée s'arrêter lorsque nous atteignions un nombre supérieur ou égal à 2147483647, mais à mesure que les valeurs de Fibonacci dépassaient la limite int, des nombres négatifs ont commencé à être générés. Comme nous n’avons jamais atteint un nombre supérieur à 2147483647, la boucle ne s’est jamais arrêtée.

Solution au problème 1

Pour garder les choses simples, je vais simplement changer le type de retour de notre fonction fib de int à long qui a une limite beaucoup plus grande. Notre code ressemblera à ceci :

    public static long fib(long n){
       if (n <= 1){
           return n;
       }
       return fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Maintenant, avec le type long, nous pouvons imprimer correctement les nombres de Fibonacci jusqu'au plus grand nombre inférieur à 2147483647.

Résoudre le problème 2 : la lenteur

Avez-vous déjà remarqué quelque chose ? À chaque itération de notre boucle, la fonction fib recalcule tous les nombres précédents de la séquence. En d’autres termes, nous répétons des calculs inutiles.

Comment éviter les recalculs inutiles ? Je vous présente : Mémoisation. La technique de mémorisation est un moyen de sauvegarder les résultats déjà calculés afin de ne pas recommencer le processus de calcul.

Implémentons un HashMap pour stocker les valeurs déjà trouvées, où la clé sera la position et la valeur est le nombre lui-même.

    static HashMap<Long, Long> memo = new HashMap<>();

    public static long fib(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            return n;
        }
        long result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        long position = 1;
        long currentNumber = fib(position);

        while (currentNumber < 2147483647) {
            System.out.println(currentNumber);
            position++;
            currentNumber = fib(position);
        }
    }

Magnifique ! Maintenant, notre code s'exécute beaucoup plus rapidement et nous avons résolu notre problème.

L'exagération

En fait, la mémorisation n'était pas nécessaire ici. Je voulais juste apporter ce concept pour enseigner. Nous pourrions simplement calculer chaque nombre de Fibonacci jusqu'à ce que nous ayons terminé notre condition comme ceci :

    public static void main(String[] args) {
        long prev1 = 0;
        long prev2 = 1;
        long current;

        System.out.println(prev1);

        while (prev2 < 2147483647) {
            System.out.println(prev2);
            current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
    }

J'en ai fini avec le plaisir, n'est-ce pas ? Désolé! Mais au moins tu as appris quelque chose de nouveau.

---

Couverture de l'article par : Gerd Altmann de Pixabay

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!