F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F 0 = 0, F 1 = 1, F n = F n - 1 + F n - 2 ;
n ≥ 0, n ∈ Z
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?-
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.
-
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 .
GO TO FULL VERSION