Ola, nao entendi o que vc quis dizer com " Eu preciso Otimizar o algoritmo do fibonacci para que somente seja chamado os métodos que não conheçemos o seu resultado. ".
Aparentemente o codigo que vc postou esta correto, por exemplo :
public class Fib {
public static void main(String[] args) {
int initialNumber = 10;
int resp ;
resp = calc(initialNumber);
System.out.println(resp);
}
public static int calc(int number) {
if ( number <= 2 ) {
return 1 ;
} else {
return calc(number-1) + calc(number-2);
}
}
}
Quando eu rodar isso vai imprimit o decimo numero da sequencia ( porque eu defini initialNumber = 10).
O resultado no caso eh 55.
[b]A chamada do método é executada varias vezes, exemplo: fibonacci(1) é chamado 5 vezes e o resultado é sempre o mesmo.
Otimize o algoritmo do fibonacci para que somente chame os métodos que não conhecemos seu resultado.
Dica: talvez é melhor alterar a assinatura do método e passar mais algum parametro.[/b]
Esta informação acima, foi passada para fazermos esta otimização, mas não sei como explicar melhor o que deve ser feito.
Eu acho que desta forma: "guarde os números já gerados pelo algoritmo em um array e passe a referência do array em cada chamada do algoritmo… " já deve otimizar, mas também não tenho ideia de como fazer.
O que o Renrutal afirmou é que é mais fácil fazer algo como isto aqui:
import java.util.*;
import java.math.*;
/**
* "Memoizing" (que eu vou traduzir por "memorização") é uma técnica de acelerar programas
* recursivos guardando resultados já calculados.
* Embora existam maneiras mais simples e eficientes de calcular os números de Fibonacci, vou
* mostrar uma técnica genérica que não exige mexer muito no seu algoritmo.
* Como vocês devem saber:
* fibonacci (0) = 0
* fibonacci (1) = 1
* fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
*/
class FibonacciComMemorizacao {
Map<Integer,BigInteger> preCalculado = new TreeMap<Integer,BigInteger>();
public FibonacciComMemorizacao() {
preCalculado.put (0, BigInteger.ZERO); // fibonacci (0) = 0
preCalculado.put (1, BigInteger.ONE); // fibonacci (1) = 1
}
public BigInteger fibonacci (int n) {
if (n == 0) {
return BigInteger.ZERO;
} else if (n == 1) {
return BigInteger.ONE;
} else if (n > 1) { // fibonacci (n) = fibonacci (n - 1) + fibonacci (n - 2)
BigInteger f = preCalculado.get (n); // vamos ver se já foi calculado antes...
if (f != null) {
// volto o valor pré-calculado!
return f;
} else {
// Não tem jeito, tem de calcular pela fórmula recursiva
f = fibonacci (n - 1).add (fibonacci (n - 2));
// E agora vamos guardar o resultado
preCalculado.put (n, f);
return f;
}
} else {
throw new IllegalArgumentException ("Definido apenas para os números positivos.");
}
}
public static void main(String[] args) {
FibonacciComMemorizacao fcm = new FibonacciComMemorizacao();
int[] valores = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 15, 20, 25, 30, 35, 40, 1000, 3000, 5000
};
/*
Valores esperados: (veja a seqüência http://www.research.att.com/~njas/sequences/A000045)
Fibonacci (1) = 1
Fibonacci (2) = 1
Fibonacci (3) = 2
Fibonacci (4) = 3
Fibonacci (5) = 5
Fibonacci (6) = 8
Fibonacci (7) = 13
Fibonacci (8) = 21
Fibonacci (9) = 34
Fibonacci (10) = 55
Fibonacci (15) = 610
Fibonacci (20) = 6765
Fibonacci (25) = 75025
Fibonacci (30) = 832040
Fibonacci (35) = 9227465
Fibonacci (40) = 102334155
*/
for (int i = 0; i < valores.length; ++i) {
System.out.println ("Fibonacci (" + valores[i] + ") = " + fcm.fibonacci (valores[i]));
}
}
}
De fato, exceto pela parafernália necessária para usar hashmaps, eu acho mais fácil de entender que a tal versão recursiva com mais parâmetros que apresentei acima.
Tava feito uams duas horas atrás mas só fui testar agora:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class FibonacciMemoizado
{
private static List<BigInteger> list = new ArrayList<BigInteger>(0);
public static void main(String[] args)
{
int numero = 1000;
System.out.println(fibMem(numero));
}
public static BigInteger fibMem(int n)
{
if (n < list.size())
return list.get(n);
else
{
BigInteger resultado;
if (n <= 1)
resultado = new BigInteger(Integer.toString(n));
else
resultado = (fibMem(n - 2).add(fibMem(n - 1)));
list.add(resultado);
return resultado;
}
}
}
PS: Pra se ter idéia, o fibonacci normal de 50 trava a máquina virtual (deixei rodando uns 45 minutos), enquanto esse que usa memoização o resultado é instantâneo.
O erro da máquina virtual que ele gerou está em anexo