Pessoal, eu estava procurando na net, maneiras diferentes de calcular a serie de fibonacci. Todas as maneiras que eu encontrava, eram diferentes claro, mas eu as entendia. A única que eu nao encontrei maneiras de entender foi essa tal de recursiva. Pra mim, o codigo nao faz sentido. Porque (Fn-1) + (Fn-2) nao da sempre certo digamos o numero 4, ficaria assim: (4-1) + (4-2) = 3+2 = 5 e na serie de fibonacci isso da 3. O codigo seria assim:
[code]public static long fib(long n) {
long h1=n-1;
long h2=n-2;
if (s <= 1) return n;
else
b = fib(h1) + fib(h2);
long h3=h1+h2;
return b;
}[/code]
O codigo ta bem “enrolado” com essas variaveis a mais porque eu entrei no modo de depuracao do NetBeans para ver se entendia quando que os valores “mudavam”, mas mesmo assim nao entendi nada. Pelo que percebi, h1 e h2 sempre chegam a 1 e 0 respectivamente mas nao entendo como.
Alguem saberia me explicar como o JVM lê isso? Como que eu entenderia esse código? T+
no passo b, fica f(4) = [f(2) + 1] + 1 + 0 = 4. Ja no passo c, f(4) = {[f(1) + f(0)] + 1] + 1 + 0 = 3. O passo C nao deveria ser f(4) = (([f(1)+1] + f(0))+1]+1+0)=4? Nao entendi pq f(2) fica igual a f(1) + f(0).
Realmente, eu so nao estou conseguindo entender a matematica. Slguem poderia por favor me explicar mais detalhadamente? Uma explicacao bem detalhada ajudaria muito. Quase nao durmo de noite tentando intender essa logica! oO
Acho que com esse código fica mais fácil de você entender, a fórmula é a seguinte:
Como a série começa com 1, 1, 2, 3, 5, 8, 13… as duas primeiras posições não requerem cálculo, então você retorna 1, a partir da terceira posição que começam realmente os cálculos:
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2)
Onde N = posição, é muito comum confundir a posição do valor na série com o número, por exemplo, Fibonacci(5) calcula o quinto elemento da série, e não para o “valor 5”.
PS: Em algumas literaturas a série de Fibonacci começa em 0 e em outras começa em 1, isso influencia no retorno, estou assumindo que a série começa com 1 nos exemplos.
public class FibonacciRecursivo {
int calculaFibonacci(int posicao) {
return (posicao<=2 ? 1 : calculaFibonacci(posicao-1) + calculaFibonacci(posicao-2));
}
}
public class TestaFibonacciRecursivo {
public static void main(String[] args) {
FibonacciRecursivo fibo = new FibonacciRecursivo();
int i = fibo.calculaFibonacci(6);
System.out.println(i); // Imprime o sexto elemento da série (número 8)
}
}
pessoal, continuo nao intendendo bem, o cimo a formula funciona. intendi que o N tratace da posicao mas, posicao = posicao-1 + posicao-2, isso e muito estranho. Porque por exemplo a posicao 6: posicao 6 = posicao 6-1 + posicao 6-2 = posicao 5 + posicao 4? E assim que calcula? Se nao for, quando que esses sinais de adicao e subtracao entram em acao?
Esse exemplo me deichou um tanto confuso pq tentei faze-lo para a posicao 6, mas deu tudo errado. Alguem poderia me explicar melhor a matematica por traz de tudo isso? E depois de explicar a matematica, alguem poderia me dar uma iluminada de como a maquina virtual le tudo isso? Um mini tuto :lol: ’
Desculpe minha burrice, mas ainda nao intendi
A regra é essa:
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)
[quote=DaniloM]me desculpem, mas continuo nao entendendo muito bem esta maneira.
F(6) = (F(6) - 1) + (F(6) - 2)[/quote]
Não é assim, na verdade, a fórmula vira isso:
F(6) = F(6-1) + F(6-2) ou F(6) = F(5) + F(4)
Agora, quanto é [color=red]F(5)[/color], pela mesma lógica? E [color=orange]F(4)[/color]?
Acompanhe a decomposição das funções, elas foram ressaltadas com cores iguais.
F(6) = [color=red]F(5)[/color] + [color=orange]F(4)[/color], seguindo a mesma lógica para F(5) e f(4) temos:
F(6) = [color=red]F(5-1) + F(5-2)[/color] + [color=orange]F(4-1) + F(4-2)[/color] então
F(6) = [color=orange]F(4)[/color] + [color=“blue”]F(3) + F(3)[/color] + [color=green]F(2)[/color] seguindo a lógica:
F(6) = [color=orange]F(4-1) + F(4-2)[/color] + [color=“blue”]F(3-1) + F(3-2) + F(3-1) + F(3-2)[/color] + [color=green]F(2-1) + F(2-2)[/color]
Caramba, agora estou comecando a intender!!! XD Nunca imaginaria que era assim que essa formula funcionava! Bom, a matematica está tranquila, entendi perfeitamente. A duvida agora esta na forma como a JVM le isso:
f(6) = f(6-1) + f(6-2) = [color=red]f(5)[/color] + [color=yellow]f(4)[/color]. Para a cor vermelha, f(5), ele vai iniciar aquele processo de f(5-1) + f(5-2)… depois o f(5) se transforma em duas outras formulas: f(4) + f(3), f(4) vai vira f(4-1) + f(4-2)… e assim por diante. pelo que me parece, varios processos estarao rodando em paralelo, ao mesmo tempo. É isso mesmo?
Digamos que eu tenha adotado o valor 6 como parametro do metodo f quando a JVM ler a instrucao: return f(n) = f(n-1) + f(n-2) que seria f(6) = f(6-1) + f(6-2) qual valor iria retornar como parametro para o metodo? Sendo que disso iria ficar: f(6) = f(5) + f(4) entao o valor que iria retornar como parametro para o metodo continuar a formula, seria o 5 ou 4? Ou ainda, ele iria iniciar os dois ao mesmo tempo tendo 2 processos em paralelo?
Obs: ViniGodoy, se esse forum tivece sistema de reputacao vc ja teria recebido ela de mim! Brigadao pela ajuda ate aqui. Ainda tenho algumas duvidas, mas elas estarao terminando aos poucos heheheheh
aguardo ancioso a resposta
Edit: Tentei fazer essa formula numa folha e fiz tambem com o numero 7 e deu certo. Entao eu ja intendi a matematica, so falta intender mesmo a logica de como a JVM le isso. Seria por processos paralelos mesmo, né?
tava dando uma pesquisada e fiquei sabendo que quando vc tem processos paralelos, vc tem os threads. E que nesse caso, nao é processo paralelo e sim em serie. Ele executa um e depois o outro né? Guardando na memoria os valores que ainda nao foram utilizados. Certo?
Desculpe perguntar depois de tanto tempo… minha dúvida é a seguinte: no trecho
F(6) = F(5) + F(4)
Em F(5) primeiro a vm vai calcular o F(5) até F(0) somar todos os valores retornar, fazer o mesmo procedimento para F(4) e depois somar os dois valores (F(5) e F(4)) e atribuir à F(6) que este por sua vez vai continuar este processo até ele ser 0 ou 1?
Se for assim este procedimento todo deve consumir bastante memória não?
Não consome tanta memória assim, embora gaste muito processamento devido a recursão e a repetição de vários cálculos.
Veja no exemplo ali em cima quantas vezes foram calculados f(2), f(3), e f(4)…
Nesse outro exemplo, mostro como otimizar isso através de um cache:
Estava estudando sobre isso agora e, pensando em uma maneira de não usar recursividade e sucessivas trocas de valores entre variáveis para criar uma sequencia, fiz o seguinte:
Quanto a processamento, é bem mais eficiente, já que não usa a pilha do SO. Essa é a vantagem de processos iterativos no lugar de recursivos. Outra vantagem é que seu processo evita calcular várias vezes o mesmo fib, do contrário do que ocorre com o método recursivo.
Mas a forma que você escreveu gasta muito mais memória. Se você só precisar calcular um índice específico, seria melhor descartar as sequencias anteriores a i-1 e i-2 e usar 2 variáveis no lugar de uma list inteira.
digamos o numero 4, ficaria assim: (4-1) + (4-2) = 3+2 = 5 e na serie de fibonacci isso da 3. O codigo seria assim:
Brigadao pela ajuda ate aqui. Ainda tenho algumas duvidas, mas elas estarao terminando aos poucos heheheheh