2011-10-24 59 views
11

我需要一些帮助,我正在编写我的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方法的结束是主要问题。我不知道如何让它递归地将数字添加到数组的正确部分。

+0

您知道,从头开始设置循环中的值比使用递归快得多。如果这是家庭作业,你只能使用递归。事实上,通过这种方式来计算可以表示的最大数量非常快,它可能不需要记住值。即仅在屏幕上绘制结果将花费更长的时间。 –

+0

我怎么会这么喜欢....这个问题具体到使用递归。一些教我们如何运作的方式我猜。 – Eogcloud

+1

这会让它成为'[作业]'添加这个标签可以让你获得关于如何以其他方式更简单的评论。 ;) –

回答

15

您需要在字典中已经计算出的数量之间没有计算号区分,您目前没有:您总是重新计算数字。

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

谢谢你,我正在看它一个小时,无法确定我做错了什么,或者我怎么修复它。我在Main方法中定义了fib(1)和fib(0),是否真的需要特殊情况? – Eogcloud

+2

@Eogcloud:由于fib(0)和fib(1)在一般情况下不能与代码混合(因为fib(-2)和fib(-1)未定义,所以需要特殊情况!)。你可以用'if(n <2){return n; }'以避免数组查找。 –

3

我相信你忘了在你的字典中实际查找东西。

变化

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

,它工作得很好(测试它自己:)

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

} 
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 + ", "); 
    } 
} 
1

这是使用的值的静态阵列的另一种方式接近的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/

2

这里是我的递归斐波那契记忆实现。使用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 
6
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; 

} 

上面大多数的解决方案,但是使用地图,而不是类似。

+0

使用地图绝对有效;不过,我会尽量避免在代码中增加不必要的复杂性。包含整数作为元素的数组可以被认为是从索引到相关整数的映射。 –

0

这里是一个不折不扣的类,它利用记忆化概念:

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; 
在每次递归函数调用时都会调用