O que um programador Java deve saber sobre os números de Fibonacci

Muitas vezes, durante entrevistas, especialmente em empresas estrangeiras, as pessoas podem ser questionadas sobre algoritmos e, em uma situação estressante, lembrar freneticamente de algo nem sempre é fácil. Portanto, você precisa se preparar. Para começar, pelo menos refresque a memória dos algoritmos básicos. Hoje analisaremos um fenômeno como os números de Fibonacci e as variantes mais comuns de problemas relacionados a eles. Os números de Fibonacci são uma sequência de números naturais que começa com os números zero e um, e cada número subsequente é igual à soma dos dois 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} ;
n ≥ 0, n ∈ Z

É importante notar que às vezes 0 é omitido e a série começa com 1 1 2 3... Via de regra, nas condições do problema é imediatamente especificado com quais dois primeiros números a série começa (0,1 ou 1,1), portanto, consideraremos soluções para ambos os casos.

Obtendo os primeiros n números de Fibonacci em Java

Suponha que tenhamos uma tarefa para obter os primeiros n números de Fibonacci.

• caso 0,1:

  Um certo número n chega até nós:

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

  Criamos um array de tamanho n. Os primeiros dois elementos serão iguais a zero e um, e os demais elementos são obtidos passando por este loop e usando os números anteriores do array.

  E exibimos:

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

  Definir int n = 10;

  E obtemos:

  
  0
  1
  1
  2
  3
  5
  8
  13
  21
  34

• para o caso 1.1, a solução não é 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];
  }

  Tudo o que precisávamos mudar foi o primeiro elemento do array arr[0]: de 0 para 1. Assim, os primeiros 10 elementos serão:

  
  1
  1
  2
  3
  5
  8
  13
  21
  34
  55

Primeiros n números de Fibonacci via stream

Mas queremos mostrar o nosso nível. Então vamos ver como ficaria essa solução 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));

  O método iterativo estático da classe Stream retorna um fluxo ordenado infinito criado pela aplicação da função ao array inicial arr. No nosso caso, a função é definir a regra de composição de cada novo array, com base no anterior. Como resultado, obteremos um fluxo de arrays:

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

  Mas haverá um número infinito deles e, portanto, usando .limit(n) reduzimos o número de elementos ao primeiro n (no nosso caso, para 10).

  No entanto, não precisamos de um fluxo de arrays, então usando .map(y -> y[0]) selecionamos o primeiro elemento de cada array e obtemos um fluxo com os números que precisamos e o imprimimos no console usando forEach .

  Parece mais legal, não é?

  com os primeiros elementos sendo 1,1 este código também será quase o mesmo:

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

  Novamente, as diferenças estão no elemento inicial: em vez de {0, 1} definimos {1, 1}

  Na verdade, os resultados serão os mesmos do exemplo anterior.

Soma dos números de Fibonacci

E se nos pedissem para obter a soma dos números de Fibonacci até o enésimo elemento inclusive? Isto não deverá causar-nos quaisquer dificuldades. Vamos pegar uma solução com um stream e substituir forEach por alguns outros métodos:

• 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) convertemos nosso stream em um IntStream numérico e usamos seu método .sum() para obter a soma de todos os elementos.

• para o caso com 1,1 elementos iniciais, em vez de {0, 1} definimos {1, 1}.

Obtendo o enésimo número da série Fibonacci

Às vezes, você é solicitado a imprimir não uma série de números, mas especificamente o enésimo número da série Fibonacci. Via de regra, isso só facilita a tarefa, pois você pode facilmente adaptar soluções anteriores para isso. Bem, que tal resolver o problema através da recursão?

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 executar o algoritmo com 0,1, é necessário especificar que quando tentamos obter o primeiro elemento, obtemos 0, e o segundo - 1. Na verdade, nós, como nas soluções anteriores, precisamos definir os dois primeiros elementos.

2. a implementação para 1.1 será um pouco 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);
     }
   }

   Neste caso, precisamos apenas definir o primeiro elemento como 1, pois o segundo elemento será o mesmo e a resposta do método será a mesma.

   Ao mesmo tempo, definimos a reação do método como 0, porque se não definirmos, então quando 2 vier como argumento, o mesmo método será chamado recursivamente, mas com argumento 0. A seguir, o mesmo método será lançado , mas com números negativos, e assim por diante até o infinito negativo. Como resultado, receberemos StackOverflowError .

No entanto, o método recursivo não é recomendado porque, diferentemente dos métodos anteriores, que são executados em tempo linear O(n), o método recursivo pode levar muito mais tempo para ser concluído. Por que? O método recursivo pode demorar muito, pois durante o processo de cálculo a função será chamada várias vezes a partir do mesmo argumento. Por exemplo, ao avaliar getFibonacciValue(7), a função fará chamadas recursivas para getFibonacciValue(5) e getFibonacciValue(6), ambas as chamadas recursivas chamarão getFibonacciValue(4)), o que resultará na chamada das mesmas operações várias vezes. Na entrevista, você pode mostrar esse método como uma solução, mas ao mesmo tempo falar sobre suas deficiências e oferecer outro método em troca. Vale ressaltar também que o tipo int em Java permite armazenar de -2147483648 a 2147483647, portanto você só conseguirá calcular os primeiros 46 números de Fibonacci: se tentarmos obter o próximo 47, haverá um overflow e obteremos um número negativo. Se usarmos o tipo de dados long em vez de int, seremos capazes de calcular corretamente os primeiros 91 números de Fibonacci. Para calcular os números de Fibonacci subsequentes, você precisa usar a classe BigInteger, que implementa a lógica para armazenar e realizar operações aritméticas de números realmente GRANDES.