Comment vérifier si un nombre est un nombre de Fibonacci en Java

Introduction

Dans ce laboratoire (lab), vous apprendrez à vérifier si un nombre donné est un nombre de Fibonacci en Java. Nous explorerons trois approches différentes pour y parvenir.

Tout d'abord, vous apprendrez à générer la suite de Fibonacci jusqu'à un nombre spécifié de termes. Ensuite, vous implémenterez une méthode pour vérifier si un nombre donné existe dans la suite générée. Enfin, nous optimiserons le processus de vérification en utilisant une formule mathématique qui peut déterminer efficacement si un nombre est un nombre de Fibonacci sans générer toute la suite.

Skills Graph

Générer la suite de Fibonacci

Dans cette étape, nous allons écrire un programme Java pour générer la suite de Fibonacci jusqu'à un certain nombre de termes. La suite de Fibonacci est une série de nombres où chaque nombre est la somme des deux précédents, généralement commençant par 0 et 1. La suite ressemble à ceci : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc.

Nous allons créer un nouveau fichier Java et écrire le code pour générer cette suite.

1. Ouvrez le WebIDE s'il n'est pas déjà ouvert. Vous devriez être dans le répertoire ~/project par défaut. Sinon, ouvrez le Terminal en bas et tapez :

   cd ~/project

2. Créez un nouveau fichier nommé Fibonacci.java dans le répertoire ~/project. Vous pouvez le faire en cliquant avec le bouton droit dans l'Explorateur de fichiers à gauche et en sélectionnant "Nouveau fichier", puis en tapant Fibonacci.java.

3. Ouvrez le fichier Fibonacci.java dans l'éditeur et copiez-collez le code Java suivant :

   import java.util.Scanner;
   
   public class Fibonacci {
   
       public static void main(String[] args) {
   
           Scanner scanner = new Scanner(System.in);
           System.out.print("Enter the number of terms for Fibonacci sequence: ");
           int n = scanner.nextInt();
   
           if (n <= 0) {
               System.out.println("Please enter a positive integer.");
           } else if (n == 1) {
               System.out.println("Fibonacci sequence up to 1 term:");
               System.out.println("0");
           } else {
               System.out.println("Fibonacci sequence up to " + n + " terms:");
   
               int firstTerm = 0;
               int secondTerm = 1;
   
               System.out.print(firstTerm + ", " + secondTerm);
   
               for (int i = 3; i <= n; ++i) {
                   int nextTerm = firstTerm + secondTerm;
                   System.out.print(", " + nextTerm);
                   firstTerm = secondTerm;
                   secondTerm = nextTerm;
               }
               System.out.println(); // Print a newline at the end
           }
   
           scanner.close();
       }
   }

   Comprenons rapidement les parties clés de ce code :

   • import java.util.Scanner; : Importe la classe Scanner pour lire l'entrée utilisateur.
   • public class Fibonacci : Déclare la classe principale nommée Fibonacci.
   • public static void main(String[] args) : La méthode principale où l'exécution du programme commence.
   • Scanner scanner = new Scanner(System.in); : Crée un objet Scanner pour lire l'entrée depuis la console.
   • System.out.print("Enter the number of terms... "); : Invite l'utilisateur à entrer le nombre de termes.
   • int n = scanner.nextInt(); : Lit l'entrée entière de l'utilisateur et la stocke dans la variable n.
   • Le bloc if-else if-else gère différents cas pour le nombre de termes (n).
   • int firstTerm = 0; int secondTerm = 1; : Initialise les deux premiers termes de la suite.
   • System.out.print(firstTerm + ", " + secondTerm); : Affiche les deux premiers termes.
   • La boucle for calcule et affiche les termes suivants.
   • int nextTerm = firstTerm + secondTerm; : Calcule le terme suivant en additionnant les deux précédents.
   • firstTerm = secondTerm; secondTerm = nextTerm; : Met à jour firstTerm et secondTerm pour l'itération suivante.
   • scanner.close(); : Ferme l'objet Scanner.

4. Enregistrez le fichier Fibonacci.java (Ctrl+S ou Cmd+S).

5. Maintenant, compilez le programme Java en utilisant la commande javac dans le Terminal :

   javac Fibonacci.java

   S'il n'y a pas d'erreurs, cette commande créera un fichier Fibonacci.class dans le répertoire ~/project.

6. Enfin, exécutez le programme compilé en utilisant la commande java :

   java Fibonacci

   Le programme vous invitera à entrer le nombre de termes. Entrez un nombre (par exemple, 10) et appuyez sur Entrée pour voir la suite de Fibonacci.

   Enter the number of terms for Fibonacci sequence: 10
   Fibonacci sequence up to 10 terms:
   0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Vous avez réussi à écrire, compiler et exécuter un programme Java pour générer la suite de Fibonacci !

Vérifier si un nombre existe dans la suite

Dans cette étape, nous allons modifier notre programme Java pour vérifier si un nombre donné existe dans la suite de Fibonacci générée. Cela implique d'ajouter une logique pour comparer le nombre saisi par l'utilisateur avec les termes de la suite au fur et à mesure de leur génération.

1. Ouvrez le fichier Fibonacci.java dans l'éditeur du WebIDE.

2. Modifiez la méthode main pour inclure la logique de vérification de l'existence d'un nombre dans la suite. Remplacez la méthode main existante par le code suivant :

   import java.util.Scanner;
   
   public class Fibonacci {
   
       public static void main(String[] args) {
   
           Scanner scanner = new Scanner(System.in);
           System.out.print("Enter the number of terms for Fibonacci sequence: ");
           int n = scanner.nextInt();
   
           if (n <= 0) {
               System.out.println("Please enter a positive integer for the number of terms.");
               scanner.close();
               return; // Exit the program
           }
   
           System.out.print("Enter the number to check if it exists in the sequence: ");
           int checkNum = scanner.nextInt();
   
           System.out.println("Fibonacci sequence up to " + n + " terms:");
   
           int firstTerm = 0;
           int secondTerm = 1;
           boolean found = false;
   
           // Check the first two terms
           if (checkNum == firstTerm) {
               found = true;
           }
           System.out.print(firstTerm);
   
           if (n > 1) {
               if (checkNum == secondTerm) {
                   found = true;
               }
               System.out.print(", " + secondTerm);
           }
   
   
           // Generate and check subsequent terms
           for (int i = 3; i <= n; ++i) {
               int nextTerm = firstTerm + secondTerm;
               if (checkNum == nextTerm) {
                   found = true;
               }
               System.out.print(", " + nextTerm);
               firstTerm = secondTerm;
               secondTerm = nextTerm;
           }
           System.out.println(); // Print a newline at the end
   
           if (found) {
               System.out.println(checkNum + " exists in the Fibonacci sequence.");
           } else {
               System.out.println(checkNum + " does not exist in the Fibonacci sequence.");
           }
   
           scanner.close();
       }
   }

   Voici un détail des modifications :

   • Nous avons ajouté une invite pour demander à l'utilisateur le nombre qu'il souhaite vérifier (System.out.print("Enter the number to check...")).
   • Nous lisons ce nombre dans une nouvelle variable checkNum (int checkNum = scanner.nextInt();).
   • Une variable booléenne found est initialisée à false. Cette variable suivra si le nombre est trouvé dans la suite.
   • Nous vérifions si checkNum est égal au firstTerm ou au secondTerm avant la boucle.
   • À l'intérieur de la boucle for, après avoir calculé nextTerm, nous vérifions si checkNum est égal à nextTerm. Si c'est le cas, nous définissons found sur true.
   • Après la fin de la boucle, nous utilisons une instruction if-else pour afficher si le nombre a été trouvé en fonction de la valeur de la variable found.

3. Enregistrez le fichier Fibonacci.java.

4. Compilez le programme modifié dans le Terminal :

   javac Fibonacci.java

5. Exécutez le programme compilé :

   java Fibonacci

   Le programme demandera maintenant le nombre de termes, puis le nombre à vérifier.

   Exemple 1 (Le nombre existe) :

   Enter the number of terms for Fibonacci sequence: 10
   Enter the number to check if it exists in the sequence: 8
   Fibonacci sequence up to 10 terms:
   0, 1, 1, 2, 3, 5, 8, 13, 21, 34
   8 exists in the Fibonacci sequence.

   Exemple 2 (Le nombre n'existe pas) :

   Enter the number of terms for Fibonacci sequence: 10
   Enter the number to check if it exists in the sequence: 10
   Fibonacci sequence up to 10 terms:
   0, 1, 1, 2, 3, 5, 8, 13, 21, 34
   10 does not exist in the Fibonacci sequence.

Vous avez réussi à modifier votre programme pour vérifier si un nombre fait partie de la suite de Fibonacci générée.

Optimisation avec une formule mathématique

Dans les étapes précédentes, nous avons généré la suite de Fibonacci de manière itérative et vérifié si un nombre existe en le comparant avec chaque terme. Pour des nombres très grands, générer toute la suite peut être inefficace. Dans cette étape, nous allons explorer une propriété mathématique des nombres de Fibonacci qui nous permet de vérifier si un nombre est un nombre de Fibonacci sans générer la suite.

Un entier positif x est un nombre de Fibonacci si et seulement si soit 5*x^2 + 4 soit 5*x^2 - 4 est un carré parfait. Un carré parfait est un entier qui est le carré d'un entier (par exemple, 4 est un carré parfait car c'est 2*2).

Nous allons créer un nouveau programme Java qui utilise cette formule pour vérifier si un nombre est un nombre de Fibonacci.

1. Créez un nouveau fichier nommé CheckFibonacci.java dans le répertoire ~/project.

2. Ouvrez CheckFibonacci.java et copiez-collez le code Java suivant :

   import java.util.Scanner;
   
   public class CheckFibonacci {
   
       // Function to check if a number is a perfect square
       public static boolean isPerfectSquare(int n) {
           if (n < 0) {
               return false;
           }
           int sqrt = (int) Math.sqrt(n);
           return (sqrt * sqrt == n);
       }
   
       // Function to check if a number is a Fibonacci number
       public static boolean isFibonacci(int n) {
           // n is Fibonacci if 5*n^2 + 4 or 5*n^2 - 4 is a perfect square
           return isPerfectSquare(5 * n * n + 4) ||
                  isPerfectSquare(5 * n * n - 4);
       }
   
       public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);
           System.out.print("Enter a number to check if it is a Fibonacci number: ");
           int num = scanner.nextInt();
   
           if (isFibonacci(num)) {
               System.out.println(num + " is a Fibonacci number.");
           } else {
               System.out.println(num + " is not a Fibonacci number.");
           }
   
           scanner.close();
       }
   }

   Examinons les nouvelles parties de ce code :

   • public static boolean isPerfectSquare(int n) : Il s'agit d'une fonction auxiliaire qui prend un entier n et renvoie true si n est un carré parfait, et false sinon. Elle calcule la racine carrée entière et vérifie si son carré donne le nombre original.
   • public static boolean isFibonacci(int n) : Cette fonction implémente la formule mathématique. Elle calcule 5*n*n + 4 et 5*n*n - 4 et utilise la fonction isPerfectSquare pour vérifier si l'un des résultats est un carré parfait. L'opérateur || signifie "ou".
   • La méthode main invite maintenant l'utilisateur à saisir un nombre, appelle la fonction isFibonacci et affiche le résultat.

3. Enregistrez le fichier CheckFibonacci.java.

4. Compilez le nouveau programme dans le Terminal :

   javac CheckFibonacci.java

5. Exécutez le programme compilé :

   java CheckFibonacci

   Le programme vous demandera d'entrer un nombre. Entrez un nombre (par exemple, 13) et appuyez sur Entrée.

   Exemple 1 (Nombre de Fibonacci) :

   Enter a number to check if it is a Fibonacci number: 13
   13 is a Fibonacci number.

   Exemple 2 (Pas un nombre de Fibonacci) :

   Enter a number to check if it is a Fibonacci number: 10
   10 is not a Fibonacci number.

Cette méthode est beaucoup plus efficace pour vérifier si un seul grand nombre est un nombre de Fibonacci par rapport à la génération de la suite jusqu'à ce nombre.

Résumé

Dans ce laboratoire (lab), nous avons appris à vérifier si un nombre est un nombre de Fibonacci en Java. Nous avons commencé par générer la suite de Fibonacci jusqu'à un certain nombre de termes en utilisant une approche itérative simple. Cela impliquait de comprendre la définition de la suite de Fibonacci et de mettre en œuvre la logique pour calculer et afficher les termes.

Ensuite, nous avons exploré comment vérifier si un nombre donné existe dans la suite de Fibonacci générée. Enfin, nous avons appris une approche optimisée utilisant une formule mathématique pour déterminer efficacement si un nombre est un nombre de Fibonacci sans générer explicitement toute la suite. Cela impliquait de comprendre les propriétés des nombres de Fibonacci et d'appliquer la formule pour effectuer la vérification.