Mémorisation récursive de Fibonacci

J'ai besoin d'aide avec un programme que j'ai écris pour ma Programmation II classe à universtiy. La question demande que l'on calcule la suite de Fibonacci en utilisant la récursivité. On doit stocker les nombres de Fibonacci calculé dans un tableau à arrêter inutilement répétée des calculs et de réduire le temps de calcul.

J'ai réussi à obtenir le programme de travail sans le tableau et la mémorisation, maintenant je suis en train de mettre en œuvre et je suis coincé. Je ne suis pas sûr de savoir comment le structurer. J'ai Googlé et écrémé à travers quelques livres mais je n'ai pas trouvé grand chose pour m'aider à résoudre la façon de mettre en œuvre une solution.

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



}

}

Le ci-dessus est incorrecte, la fin de mon fib méthode est le principal problème. Je n'ai aucune idée de la façon de l'obtenir pour ajouter les numéros de manière récursive à l'correctement les parties du tableau.

source d'informationauteur Eogcloud

Vous avez besoin de distinguer entre déjà calculé le nombre, et non calculé les nombres dans le dictionnaire, vous n': vous toujours recalculer le nombre.

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

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; 

}

Similaire à la plupart des solutions ci-dessus, mais en utilisant une Carte à la place.

Programme pour imprimer la première n nombres de fibonacci à l'aide de 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 + ", ");
    }
}

Je crois que vous oubliez de réalité chercher des choses dans votre dictionnaire.

Changement

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

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

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

et il fonctionne très bien (testé moi-même 🙂

Voici mon implémentation récursive de fibonacci memoization. À l'aide de BigInteger et ArrayList permet de calculer la 100e ou même plus grand terme. J'ai essayé 1000e termes, et le résultat est renvoyé en quelques millisecondes, voici le code:

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

Exemple de sortie

printFebonachiRecursion(100);

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

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

1

C'est une autre façon d'aborder memoization récursive de fibonacci() la méthode à l'aide d'un tableau statique de valeurs -
```
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;
}
}
```
Noter que cette méthode utilise globale(niveau de classe) tableau statique fibArray[]. Avoir un coup d'oeil à l'ensemble du code de l'explication vous pouvez également voir les éléments suivants - http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

Vous devez vous connecter pour publier un commentaire.