Memorización recursiva de Fibonacci

Question

Necesito ayuda con un programa que estoy escribiendo para mi clase de Programación II en la universidad. La pregunta pide que uno calcule la secuencia de Fibonacci usando la recursión. Uno debe almacenar los números de Fibonacci calculados en una matriz para detener los cálculos repetidos innecesarios y reducir el tiempo de cálculo.

Logré hacer que el programa funcionara sin la matriz y la memorización, ahora estoy tratando de implementar eso y estoy atascado. No estoy seguro de cómo estructurarlo. Busqué en Google y hojeé algunos libros, pero no he encontrado mucho que me ayude a resolver cómo implementar una solución.

import javax.swing.JOptionPane; 
public class question2 
{ 
static int count = 0; 
static int [] dictionary; 

public static void main(String[] args) 
{ 

int answer; 
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:")); 

javax.swing.JOptionPane.showMessageDialog(null, 
     "About to calculate fibonacci(" + num + ")"); 

//giving the array "n" elements 
dictionary= new int [num]; 

if (dictionary.length>=0) 
dictionary[0]= 0; 

if (dictionary.length>=1) 
dictionary[0]= 0; 
dictionary[1]= 1; 


//method call 
answer = fibonacci(num); 

//output 
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)"); 
} 



    static int fibonacci(int n) 
    { 
count++; 

// Only defined for n >= 0 
if (n < 0) { 
    System.out.println("ERROR: fibonacci sequence not defined for negative numbers."); 
    System.exit(1); 
} 

// Base cases: f(0) is 0, f(1) is 1 
// Other cases: f(n) = f(n-1) + f(n-2)/ 
if (n == 0) 
{ 
    return dictionary[0]; 
} 

else if (n == 1) 
{ 
    return dictionary[1]; 
} 

else 
return dictionary[n] = fibonacci(n-1) + fibonacci(n-2); 



} 

} 

Lo anterior es incorrecto, el final de mi método fib es el problema principal. No tengo idea de cómo conseguir que agregue los números recursivamente a las partes correctas de la matriz.

Answer 1

es necesario distinguir entre el número ya calculado y no números calculados en el diccionario , que actualmente no: siempre recalcula los números.

if (n == 0) 
{ 
    // special case because fib(0) is 0 
    return dictionary[0]; 
} 
else 
{ 
    int f = dictionary[n]; 
    if (f == 0) { 
    // number wasn't calculated yet. 
    f = fibonacci(n-1) + fibonacci(n-2); 
    dictionary[n] = f; 
    } 
    return f; 
} 

Answer 2

Creo que te olvidas de buscar cosas en tu diccionario.

Cambio

else 
    return dictionary[n] = fibonacci(n-1) + fibonacci(n-2); 

a

else { 
    if (dictionary[n] > 0) 
     return dictionary[n]; 

    return dictionary[n] = fibonacci(n - 1) + fibonacci(n - 2); 
} 

y funciona muy bien (probado yo mismo :)

Answer 3

int F(int Num){ 
int i =0; 
int* A = NULL; 
if(Num > 0) 
{ 
A = (int*) malloc(Num * sizeof(int)); 
} 
else 
return Num; 

for(;i<Num;i++) 
A[i] = -1; 

return F_M(Num, &A); 


} 

int F_M(int Num, int** Ap){ 
int Num1 = 0; 
int Num2 = 0; 

if((*Ap)[Num - 1] < 0) 
{ 
    Num1 = F_M(Num - 1, Ap); 
    (*Ap)[Num -1] = Num1; 
    printf("Num1:%d\n",Num1); 
} 
else 
    Num1 = (*Ap)[Num - 1]; 

if((*Ap)[Num - 2] < 0) 
{ 
    Num2 = F_M(Num - 2, Ap); 
    (*Ap)[Num -2] = Num2; 
    printf("Num2:%d\n",Num2); 
} 
else 
    Num2 = (*Ap)[Num - 2]; 

if(0 == Num || 1 == Num) 
{ 
(*Ap)[Num] = Num; 
return Num; 
} 
else{ 
// return ((*Ap)[Num - 2] > 0?(*Ap)[Num - 2] = F_M(Num -2, Ap): (*Ap)[Num - 2] ) +  ((*Ap)[Num - 1] > 0?(*Ap)[Num - 1] = F_M(Num -1, Ap): (*Ap)[Num - 1] ); 
    return (Num1 + Num2); 
} 

} 

int main(int argc, char** argv){ 
int Num = 0; 
if(argc>1){ 
sscanf(argv[1], "%d", &Num); 
} 

printf("F(%d) = %d", Num, F(Num)); 

return 0; 

} 

Answer 4

programa para imprimir primeros números de Fibonacci utilizando n memoization.

int[] dictionary; 
// Get Fibonacci with Memoization 
public int getFibWithMem(int n) { 
    if (dictionary == null) { 
     dictionary = new int[n]; 
    } 

    if (dictionary[n - 1] == 0) { 
     if (n <= 2) { 
      dictionary[n - 1] = n - 1; 
     } else { 
      dictionary[n - 1] = getFibWithMem(n - 1) + getFibWithMem(n - 2); 
     } 
    } 

    return dictionary[n - 1]; 
} 

public void printFibonacci() 
{ 
    for (int curr : dictionary) { 
     System.out.print("F[" + i++ + "]:" + curr + ", "); 
    } 
} 

Answer 5

Esta es otra manera de acercarse a memoization de Fibonacci recursiva() método que usa una matriz estática de los valores -

public static long fibArray[]=new long[50];\\Keep it as large as you need 

public static long fibonacci(long n){ 
long fibValue=0; 
if(n==0){ 
    return 0; 
}else if(n==1){ 
    return 1; 
}else if(fibArray[(int)n]!=0){ 
    return fibArray[(int)n];  
} 
else{ 
    fibValue=fibonacci(n-1)+fibonacci(n-2); 
    fibArray[(int) n]=fibValue; 
    return fibValue; 
} 
} 

Tenga en cuenta que este método utiliza un (nivel de clase) mundial matriz estática fibArray [] . Para echar un vistazo a todo el código con una explicación, también puede ver lo siguiente: http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

Answer 6

Aquí está mi implementación de la memoria recursiva de Fibonacci. El uso de BigInteger y ArrayList permite calcular el término 100 o incluso mayor. Probé términos número 1000, y el resultado se devuelve en cuestión de milisegundos, aquí está el código:

private static List<BigInteger> dict = new ArrayList<BigInteger>(); 
    public static void printFebonachiRecursion (int num){ 
    if (num==1){ 
     printFebonachiRecursion(num-1); 
     System.out.printf("Term %d: %d%n",num,1); 
     dict.add(BigInteger.ONE); 
    } 
    else if (num==0){ 
     System.out.printf("Term %d: %d%n",num,0); 
     dict.add(BigInteger.ZERO); 
    } 
    else { 
    printFebonachiRecursion(num-1); 
    dict.add(dict.get(num-2).add(dict.get(num-1))); 
    System.out.printf("Term %d: %d%n",num,dict.get(num)); 
    } 
} 

Ejemplo de salida

printFebonachiRecursion(100); 

Term 0: 0 
Term 1: 1 
Term 2: 1 
Term 3: 2 
... 
Term 98: 135301852344706746049 
Term 99: 218922995834555169026 
Term 100: 354224848179261915075 

Answer 7

public static int fib(int n, Map<Integer,Integer> map){ 

    if(n ==0){ 
     return 0; 
    } 

    if(n ==1){ 
     return 1; 
    } 

    if(map.containsKey(n)){ 
     return map.get(n); 
    } 

    Integer fibForN = fib(n-1,map) + fib(n-2,map); 
    map.put(n, fibForN); 

    return fibForN; 

} 

Al igual que en la mayoría de las soluciones anteriores, pero utilizando un mapa en su lugar.

Answer 8

Aquí es una clase de pleno derechoque aprovecha la memoization concepto:

import java.util.HashMap; 
import java.util.Map; 

public class Fibonacci { 

    public static Fibonacci getInstance() { 
     return new Fibonacci(); 
    } 

    public int fib(int n) { 
     HashMap<Integer, Integer> memoizedMap = new HashMap<>(); 

     memoizedMap.put(0, 0); 
     memoizedMap.put(1, 1); 

     return fib(n, memoizedMap); 
    } 

    private int fib(int n, Map<Integer, Integer> map) { 
     if (map.containsKey(n)) 
      return map.get(n); 

     int fibFromN = fib(n - 1, map) + fib(n - 2, map); 

     // MEMOIZE the computed value 
     map.put(n, fibFromN); 

     return fibFromN; 
    } 
} 

en cuenta que

memoizedMap.put(0, 0); 
memoizedMap.put(1, 1); 

se utiliza para eliminar la necesidad de la siguiente comprobación

if (n == 0) return 0; 
if (n == 1) return 1; 

en cada llamada de función recursiva.