遞歸斐波那契記憶

Question

我需要一些幫助，我正在編寫我的Programming II課程。問題是要求用遞歸計算Fibonacci序列。必須將計算的斐波那契數字存儲在數組中以停止不必要的重複計算並減少計算時間。

我設法讓程序在沒有數組和記憶的情況下工作，現在我試圖實現這一點，並且我被卡住了。我不知道如何構建它。我已經Google和Google瀏覽了一些書籍，但沒有找到太多的東西來幫助我解決如何實施解決方案。

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



} 

} 

以上是不正確的，我的fib方法的結束是主要問題。我不知道如何讓它遞歸地將數字添加到數組的正確部分。

Answer 1

您需要在字典中已經計算出的數量之間沒有計算號區分，您目前沒有：您總是重新計算數字。

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

我相信你忘了在你的字典中實際查找東西。

變化

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

，它工作得很好（測試它自己:)

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

程序打印使用記憶化第一n斐波那契數。

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

這是使用的值的靜態陣列的另一種方式接近的memoization遞歸斐波納契（）方法 -

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

注意，此方法使用全局（類級）靜態數組fibArray [] 。要看看整個代碼的解釋，你還可以看到以下內容 - http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/

Answer 6

這裏是我的遞歸斐波那契記憶實現。使用BigInteger和ArrayList可以計算出第100個甚至更大的術語。我想第1000條款，結果在幾毫秒內恢復，這裏是代碼：

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

輸出例如

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; 

} 

上面大多數的解決方案，但是使用地圖，而不是類似。

Answer 8

這裏是一個不折不扣的類，它利用記憶化概念：

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

注意

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

用於消除下一檢查的必要性

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

在每次遞歸函數調用時都會調用

。