Cómo verificar si un número es un número de Fibonacci en Java

Introducción

En este laboratorio, aprenderás cómo verificar si un número dado es un número de Fibonacci en Java. Exploraremos tres enfoques diferentes para lograr esto.

Primero, aprenderás cómo generar la secuencia de Fibonacci hasta un número especificado de términos. Luego, implementarás un método para verificar si un número dado existe dentro de la secuencia generada. Finalmente, optimizaremos el proceso de verificación utilizando una fórmula matemática que puede determinar de manera eficiente si un número es un número de Fibonacci sin generar toda la secuencia.

Skills Graph

Generar la secuencia de Fibonacci

En este paso, escribiremos un programa en Java para generar la secuencia de Fibonacci hasta un cierto número de términos. La secuencia de Fibonacci es una serie de números en la que cada número es la suma de los dos números anteriores, generalmente comenzando con 0 y 1. La secuencia se ve así: 0, 1, 1, 2, 3, 5, 8, 13, 21, y así sucesivamente.

Crearemos un nuevo archivo Java y escribiremos el código para generar esta secuencia.

1. Abre el WebIDE si no está abierto. Por defecto, deberías estar en el directorio ~/project. Si no lo estás, abre la Terminal en la parte inferior y escribe:

   cd ~/project

2. Crea un nuevo archivo llamado Fibonacci.java en el directorio ~/project. Puedes hacer esto haciendo clic derecho en el Explorador de archivos de la izquierda y seleccionando "Nuevo archivo", luego escribiendo Fibonacci.java.

3. Abre el archivo Fibonacci.java en el editor y copia y pega el siguiente código Java:

   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();
       }
   }

   Vamos a entender rápidamente las partes clave de este código:

   • import java.util.Scanner;: Importa la clase Scanner para leer la entrada del usuario.
   • public class Fibonacci: Declara la clase principal llamada Fibonacci.
   • public static void main(String[] args): El método principal donde comienza la ejecución del programa.
   • Scanner scanner = new Scanner(System.in);: Crea un objeto Scanner para leer la entrada desde la consola.
   • System.out.print("Enter the number of terms... ");: Solicita al usuario que ingrese el número de términos.
   • int n = scanner.nextInt();: Lee la entrada entera del usuario y la almacena en la variable n.
   • El bloque if-else if-else maneja diferentes casos para el número de términos (n).
   • int firstTerm = 0; int secondTerm = 1;: Inicializa los dos primeros términos de la secuencia.
   • System.out.print(firstTerm + ", " + secondTerm);: Imprime los dos primeros términos.
   • El bucle for calcula e imprime los términos subsiguientes.
   • int nextTerm = firstTerm + secondTerm;: Calcula el siguiente término sumando los dos términos anteriores.
   • firstTerm = secondTerm; secondTerm = nextTerm;: Actualiza firstTerm y secondTerm para la siguiente iteración.
   • scanner.close();: Cierra el objeto Scanner.

4. Guarda el archivo Fibonacci.java (Ctrl+S o Cmd+S).

5. Ahora, compila el programa Java utilizando el comando javac en la Terminal:

   javac Fibonacci.java

   Si no hay errores, este comando creará un archivo Fibonacci.class en el directorio ~/project.

6. Finalmente, ejecuta el programa compilado utilizando el comando java:

   java Fibonacci

   El programa te pedirá que ingreses el número de términos. Ingresa un número (por ejemplo, 10) y presiona Enter para ver la secuencia 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

¡Has escrito, compilado y ejecutado con éxito un programa Java para generar la secuencia de Fibonacci!

Verificar si un número existe en la secuencia

En este paso, modificaremos nuestro programa Java para verificar si un número dado existe dentro de la secuencia de Fibonacci generada. Esto implica agregar lógica para comparar el número de entrada del usuario con los términos de la secuencia a medida que se generan.

1. Abre el archivo Fibonacci.java en el editor del WebIDE.

2. Modifica el método main para incluir la lógica para verificar si un número existe en la secuencia. Reemplaza el método main existente con el siguiente código:

   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();
       }
   }

   Aquí está un desglose de los cambios:

   • Agregamos una solicitud para preguntar al usuario por el número que desea verificar (System.out.print("Enter the number to check...")).
   • Leemos este número en una nueva variable checkNum (int checkNum = scanner.nextInt();).
   • Se inicializa una variable booleana found en false. Esta variable llevará la cuenta de si el número se encuentra en la secuencia.
   • Verificamos si checkNum es igual al firstTerm o secondTerm antes del bucle.
   • Dentro del bucle for, después de calcular nextTerm, verificamos si checkNum es igual a nextTerm. Si lo es, establecemos found en true.
   • Después de que el bucle termine, usamos una declaración if-else para imprimir si el número se encontró o no en función del valor de la variable found.

3. Guarda el archivo Fibonacci.java.

4. Compila el programa modificado en la Terminal:

   javac Fibonacci.java

5. Ejecuta el programa compilado:

   java Fibonacci

   El programa ahora solicitará el número de términos y luego el número a verificar.

   Ejemplo 1 (El número 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.

   Ejemplo 2 (El número no existe):

   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.

Has modificado con éxito tu programa para verificar si un número es parte de la secuencia de Fibonacci generada.

Optimizar con una fórmula matemática

En los pasos anteriores, generamos la secuencia de Fibonacci de forma iterativa y verificamos si un número existe comparándolo con cada término. Para números muy grandes, generar toda la secuencia puede ser ineficiente. En este paso, exploraremos una propiedad matemática de los números de Fibonacci que nos permite verificar si un número es un número de Fibonacci sin generar la secuencia.

Un entero positivo x es un número de Fibonacci si y solo si 5*x^2 + 4 o 5*x^2 - 4 es un cuadrado perfecto. Un cuadrado perfecto es un entero que es el cuadrado de otro entero (por ejemplo, 4 es un cuadrado perfecto porque es 2*2).

Crearemos un nuevo programa Java que utilice esta fórmula para verificar si un número es un número de Fibonacci.

1. Crea un nuevo archivo llamado CheckFibonacci.java en el directorio ~/project.

2. Abre CheckFibonacci.java y copia y pega el siguiente código Java:

   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();
       }
   }

   Veamos las nuevas partes de este código:

   • public static boolean isPerfectSquare(int n): Esta es una función auxiliar que toma un entero n y devuelve true si n es un cuadrado perfecto, y false en caso contrario. Calcula la raíz cuadrada entera y verifica si al elevarla al cuadrado se obtiene el número original.
   • public static boolean isFibonacci(int n): Esta función implementa la fórmula matemática. Calcula 5*n*n + 4 y 5*n*n - 4 y utiliza la función isPerfectSquare para verificar si cualquiera de los resultados es un cuadrado perfecto. El operador || significa "o".
   • El método main ahora solicita al usuario un número, llama a la función isFibonacci e imprime el resultado.

3. Guarda el archivo CheckFibonacci.java.

4. Compila el nuevo programa en la Terminal:

   javac CheckFibonacci.java

5. Ejecuta el programa compilado:

   java CheckFibonacci

   El programa te pedirá que ingreses un número. Ingresa un número (por ejemplo, 13) y presiona Enter.

   Ejemplo 1 (Número de Fibonacci):

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

   Ejemplo 2 (No es un número de Fibonacci):

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

Este método es mucho más eficiente para verificar si un solo número grande es un número de Fibonacci en comparación con la generación de la secuencia hasta ese número.

Resumen

En este laboratorio, aprendimos cómo verificar si un número es un número de Fibonacci en Java. Comenzamos generando la secuencia de Fibonacci hasta un cierto número de términos utilizando un enfoque iterativo simple. Esto implicó entender la definición de la secuencia de Fibonacci e implementar la lógica para calcular e imprimir los términos.

A continuación, exploramos cómo verificar si un número dado existe dentro de la secuencia de Fibonacci generada. Finalmente, aprendimos sobre un enfoque optimizado que utiliza una fórmula matemática para determinar de manera eficiente si un número es un número de Fibonacci sin generar explícitamente toda la secuencia. Esto implicó entender las propiedades de los números de Fibonacci y aplicar la fórmula para realizar la verificación.