Memoizzazione ricorsiva di Fibonacci

Question

Ho bisogno di aiuto con un programma che sto scrivendo per la mia classe Programming II in universtiy. La domanda chiede che si calcoli la sequenza di Fibonacci usando la ricorsione. Uno deve memorizzare i numeri di Fibonacci calcolati in una matrice per interrompere calcoli ripetuti non necessari e ridurre al tempo di calcolo.

Sono riuscito a far funzionare il programma senza l'array e la memorizzazione, ora sto cercando di implementarlo e sono bloccato. Non sono sicuro di come strutturarlo. Ho cercato su Google e sfogliato alcuni libri, ma non ho trovato molto per aiutarmi a risolvere come implementare una soluzione.

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



} 

} 

Quanto sopra è corretta, la fine del mio metodo fib è il problema principale. Non ho idea di come ottenere di aggiungere i numeri in modo ricorsivo alle parti correttamente della matrice.

Answer 1

È necessario distinguere tra il numero già calcolato e non numeri calcolati nel dizionario , che attualmente non lo fai: tu sempre ricalcoli i numeri.

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

Credo che tu abbia dimenticato di cercare effettivamente le cose nel tuo dizionario.

Change

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

e funziona bene (provato io :)

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

programma per stampare primi n numeri di Fibonacci utilizzando Memoizzazione.

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

Questo è un altro modo di affrontare memoization per Fibonacci ricorsiva() metodo che utilizza una matrice statica di valori -

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

noti che questo metodo utilizza un (livello di classe) globale matrice statica fibArray [] . Per dare un'occhiata all'intero codice con spiegazione puoi anche vedere quanto segue -

Answer 6

Ecco la mia implementazione della ricognizione della memoizzazione di Fibonacci. L'utilizzo di BigInteger e ArrayList consente di calcolare il termine 100 o anche più grande. Ho provato termini 1000i, e il risultato viene restituito in pochi millisecondi, ecco il codice:

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

esempio uscita

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; 

} 

Simile alla maggior parte delle soluzioni di cui sopra, ma utilizzando una mappa, invece.

Answer 8

Qui è un classe pieno titolo che sfrutta la memoization concetto:

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

noti che

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

sono utilizzati per eliminare la necessità della seguente controllo

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

ad ogni chiamata di funzione ricorsiva.