Lo que un programador de Java debe saber sobre los números de Fibonacci

A menudo, durante las entrevistas, especialmente en empresas extranjeras, se puede preguntar a las personas sobre algoritmos y, en una situación estresante, recordar algo frenéticamente no siempre es fácil. Por lo tanto, es necesario prepararse. Para empezar, al menos actualice su memoria sobre los algoritmos básicos. Hoy analizaremos un fenómeno como los números de Fibonacci y las variantes más comunes de problemas relacionados con ellos. Los números de Fibonacci son una secuencia de números naturales que comienza con los números cero y uno, y cada número posterior es igual a la suma de los dos anteriores: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F ₀ = 0, F ₁ = 1, F _n = F _{n - 1} + F _{n - 2} ;
norte ≥ 0, norte ∈ Z

Vale la pena señalar que a veces se omite 0 y la serie comienza con 1 1 2 3... Como regla general, en las condiciones del problema se especifica inmediatamente con qué dos primeros números comienza la serie (0,1 o 1,1), Por lo tanto, consideraremos soluciones para ambos casos.

Obtener los primeros n números de Fibonacci en Java

Supongamos que tenemos la tarea de obtener los primeros n números de Fibonacci.

• caso 0.1:

  Nos llega un cierto número n:

  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];
  }

  Creamos una matriz de tamaño n. Los primeros dos elementos serán iguales a cero y uno, y los elementos restantes se obtienen siguiendo este ciclo y usando los números anteriores de la matriz.

  Y mostramos:

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

  Establecer int n = 10;

  Y obtenemos:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• para el caso 1.1 la solución en realidad no es diferente:

  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];
  }

  Todo lo que necesitábamos cambiar era el primer elemento de la matriz arr[0]: de 0 a 1. En consecuencia, los primeros 10 elementos serán:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Primeros n números de Fibonacci vía streaming

Pero queremos mostrar nuestro nivel. Entonces, veamos cómo se vería esta solución usando stream .

• para 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));

  El método de iteración estático de la clase Stream devuelve una secuencia ordenada infinita creada aplicando la función a la matriz inicial arr. En nuestro caso, la función es establecer la regla para componer cada nuevo array, en base al anterior. Como resultado, obtendremos un flujo de matrices:

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

  Pero habrá un número infinito de ellos y, por lo tanto, usando .limit(n) reducimos el número de elementos al primer n (en nuestro caso a 10).

  Sin embargo, no necesitamos una secuencia de matrices, por lo que usando .map(y -> y[0]) seleccionamos el primer elemento de cada matriz y obtenemos una secuencia con los números que necesitamos y la imprimimos en la consola usando forEach. .

  Se ve más genial, ¿no?

  siendo los primeros elementos 1,1, este código también será casi el mismo:

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

  Nuevamente, las diferencias están en el elemento inicial: en lugar de {0, 1} configuramos {1, 1}

  En realidad, los resultados serán los mismos que en el ejemplo anterior.

Suma de números de Fibonacci

¿Qué pasaría si nos pidieran obtener la suma de los números de Fibonacci hasta el enésimo elemento inclusive? Esto no debería causarnos ninguna dificultad. Tomemos una solución con una secuencia y reemplacemos forEach con un par de métodos más:

• para 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);

  Usando .mapToInt(Integer::intValue) convertimos nuestra secuencia en un IntStream numérico y usamos su método .sum() para obtener la suma de todos los elementos.

• para el caso con 1,1 elementos iniciales, en lugar de {0, 1} configuramos {1, 1}.

Obtener el enésimo número de la serie de Fibonacci

A veces se le pide que imprima no una serie de números, sino específicamente el enésimo número de la serie de Fibonacci. Por regla general, esto sólo facilita la tarea, ya que puede adaptar fácilmente soluciones anteriores para ello. Bueno, ¿qué pasa con la solución del problema mediante la recursividad?

1. para 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);
     }
   }

   Para ejecutar el algoritmo con 0,1, es necesario especificar que cuando intentamos obtener el primer elemento, obtenemos 0 y el segundo - 1. De hecho, nosotros, como en las soluciones anteriores, necesitamos configurar los dos primeros. elementos.

2. la implementación para 1.1 será ligeramente diferente:

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

   En este caso, sólo necesitamos establecer el primer elemento como 1, ya que el segundo elemento será el mismo y la respuesta del método será la misma.

   Al mismo tiempo, configuramos la reacción del método en 0, porque si no lo configuramos, cuando viene 2 como argumento, se llama al mismo método de forma recursiva, pero con el argumento 0. A continuación, se ejecutará el mismo método. , pero con números negativos, y así hasta el infinito negativo. Como resultado, recibiremos un StackOverflowError .

Sin embargo, no se recomienda el método recursivo porque, a diferencia de los métodos anteriores, que se ejecutan en un tiempo lineal O(n), el método recursivo puede tardar mucho más en completarse. ¿Por qué? El método recursivo puede llevar mucho tiempo, ya que durante el proceso de cálculo la función será llamada muchas veces desde el mismo argumento. Por ejemplo, al evaluar getFibonacciValue(7), la función realizará llamadas recursivas a getFibonacciValue(5) y getFibonacciValue(6), ambas llamadas recursivas llamarán a getFibonacciValue(4)), lo que resultará en llamar a las mismas operaciones varias veces. En la entrevista, puede mostrar este método como una solución, pero al mismo tiempo hablar de sus deficiencias y ofrecer otro método a cambio. También vale la pena señalar que el tipo int en Java le permite almacenar desde -2147483648 hasta 2147483647, por lo que solo podrá calcular los primeros 46 números de Fibonacci: si intentamos obtener el siguiente número 47, habrá un desbordamiento y obtendremos un número negativo. Si utilizamos el tipo de datos long en lugar de int, podremos calcular correctamente los primeros 91 números de Fibonacci. Para calcular los números de Fibonacci posteriores, debe utilizar la clase BigInteger, que implementa la lógica para almacenar operaciones aritméticas de números realmente GRANDES.