Números de Fibonacci en lenguaje Java

De hecho, los dos primeros números de Fibonacci están predefinidos. El primer número de Fibonacci es 0 y el segundo número de Fibonacci es 1. Con la indexación basada en cero y suponiendo que los números de Fibonacci están en una matriz, entonces:

y así.

En programación, la variable n, y no i, se usa para los índices de base cero para estos números de Fibonacci. Y con eso, los primeros doce números de Fibonacci son:

La segunda fila de la tabla proporciona los índices de base cero, cada uno de los cuales tendría la variable n en la programación. La primera fila da los números de Fibonacci correspondientes. Entonces, los números de Fibonacci no son cualquier número. La definición central comienza con 0, para el primer número de Fibonacci y 1 para el segundo número de Fibonacci. El resto de los números se producen a partir de ahí.

Los números de Fibonacci se pueden producir en tiempo O(n) y también en tiempo O(1). Para el tiempo O(n), si n es 12 por ejemplo, entonces se producirían los primeros doce números de Fibonacci. Para el tiempo O(1), solo se produce un número de Fibonacci. Por ejemplo, si n es 6, entonces se produciría el número de Fibonacci 8.

Este artículo explica estas dos formas de producir números de Fibonacci en Java.

Fórmula para un número de Fibonacci

Hay una fórmula matemática para un número de Fibonacci. Esta fórmula se puede escribir en tres líneas o en una línea. En tres líneas, se escribe como:

donde F _norte es el número de Fibonacci en el n de base cero ^el índice. Así es como se define el número de Fibonacci.

Producción de números de Fibonacci en tiempo O(n)

Si los números de Fibonacci se van a producir en O(3) veces, se producirían los números 0, 1, 1; esos son los tres primeros números de Fibonacci. El último n de base cero ^el índice aquí, es 2. Si los números de Fibonacci se van a producir en O(7) veces, se producirían los números, 0, 1, 1, 2, 3, 5, 8; esos son los primeros siete números de Fibonacci. El último n de base cero ^el índice aquí, es 6. Si los números de Fibonacci se van a producir en O(n) veces, se producirían los números, 0, 1, 1, 2, 3, 5, 8 – – -; esos son los primeros n números de Fibonacci. El último n de base cero ^el el índice aquí es n-1.

El método de Java en una clase para producir los primeros n números de Fibonacci es:

La clase, Fibonacci es privada. los fibonacci() El método toma la matriz P y devuelve vacío. El método comienza determinando la longitud de la matriz. Esta longitud de n es el número de números de Fibonacci necesarios. El primer y segundo número de Fibonacci se determinan explícitamente y se colocan en la primera y segunda posición de la matriz.

El resto de los números de Fibonacci a partir del tercero (índice, n = 2) se determinan en un bucle for y se colocan en sus posiciones en la matriz. Entonces, la función tiene que regresar vacía. La sentencia principal en el bucle for suma los dos números anteriores.

La variable de índice, i, se ha utilizado en lugar de n, con fines de claridad.

Una clase principal de Java adecuada (con el método principal de Java) es:

Una vez que el método fibonacci() ha producido los números, el método principal de Java los lee.

Producción de un número de Fibonacci en tiempo constante

Hay una fórmula matemática que se puede usar para producir un número de Fibonacci, cuando se le da el índice de base cero correspondiente, n. La fórmula es:

donde n es el índice de base cero y Fib _norte es el número de Fibonacci correspondiente. Tenga en cuenta que en el lado derecho de la ecuación, no es la raíz cuadrada de 5 la que está elevada a la potencia n; es la expresión entre paréntesis que está elevada a la potencia n. Hay dos de tales expresiones.

Si n es 0, Fib _norte sería 0. Si n es 1, Fib _norte sería 1. Si n es 2, Fib _norte sería 1. Si n es 3, Fib _norte sería 2. Si n es 4, Fib _norte sería 3 – y así sucesivamente. El lector puede verificar esta fórmula matemáticamente, sustituyendo diferentes valores por n y evaluando.

Cuando se codifica, esta fórmula produciría solo un número de Fibonacci para n. Si se requiere más de un número de Fibonacci, el código de la fórmula debe llamarse una vez para cada uno de los diferentes índices correspondientes.

En Java, el método para producir un solo número de Fibonacci es:

El paquete java.lang.* tuvo que ser importado al principio del programa. Esto se debe a que el paquete tiene la clase Math, que tiene los métodos de potencia (pow) y raíz cuadrada (sqrt). El método Java personalizado aquí implementa la fórmula matemática directamente.

La complejidad temporal de esta función es O(1), constante de una operación principal. Una clase principal de Java adecuada, con el método principal de Java para el método anterior es:

Se envía el índice n = 11 y se devuelve el número de Fibonacci, 89. La salida es:

Los dígitos decimales innecesarios se pueden eliminar, pero esa es una discusión para otro momento.

Conclusión

Los números de Fibonacci son una secuencia particular de números enteros. Para obtener el número actual, se suman los dos números correspondientes inmediatamente anteriores. Los dos primeros números de Fibonacci, 0 seguido de 1, están predeclarados para toda la secuencia. El resto de los números de Fibonacci se producen a partir de ahí.

Para producir números de Fibonacci desde el índice 2, hasta el que corresponde al índice n-1, use un ciclo for con la declaración principal:

donde currNo es el número de Fibonacci actual y P es la matriz para almacenar los n números.

Para producir solo un número de Fibonacci a partir de cualquier índice de base cero n, utilice la fórmula matemática: