递归Fibonacci memoization

我需要一些帮助，我正在为Universiy的Programming II课程编写一个程序。 问题是要求使用递归计算斐波纳契数列。 必须将计算出的斐波那契数存储在一个数组中，以阻止不必要的重复计算并减少计算时间。

我设法让程序在没有arrays和记忆的情况下工作，现在我正在尝试实现它而且我被卡住了。 我不确定如何构建它。 我用谷歌搜索并浏览了一些书，但没有找到太多帮助我解决如何实施解决方案。

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

 public static int fib(int n, Map 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 3

程序使用Memoization打印第一个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 4

我相信你忘了实际查找字典中的内容。

更改

 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 5

这是我对递归斐波那契记忆的实现。 使用BigInteger和ArrayList可以计算出第100个甚至更长的项。 我尝试了第1000个术语，结果在几毫秒内返回，这里是代码：

  private static List dict = new ArrayList(); 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 6

 int F(int Num){ int i =0; int* A = NULL; if(Num > 0) { A = (int*) malloc(Num * sizeof(int)); } else return Num; for(;i 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 7

这是使用静态值数组进行递归fibonacci（）方法的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 8

这是一个利用memoization概念的完全成熟的类 ：

 import java.util.HashMap; import java.util.Map; public class Fibonacci { public static Fibonacci getInstance() { return new Fibonacci(); } public int fib(int n) { HashMap memoizedMap = new HashMap<>(); memoizedMap.put(0, 0); memoizedMap.put(1, 1); return fib(n, memoizedMap); } private int fib(int n, Map 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; 

在每个递归函数调用。

Answer 9

 #include  long int A[100]={1,1}; long int fib(int n){ if (A[n]) { return A[n]; } else { return A[n]=fib(n-1)+fib(n-2); } } int main(){ printf("%ld",fib(30)); } 

Answer 10

这是我的实施。

 private static int F(int N, int[] A) { if ((N == 0) || (N == 1)) return N; if (A[N] != 0) return A[N]; if ((A[N - 1] != 0) && (A[N - 2] != 0)) { A[N] = A[N - 1] + A[N - 2]; return A[N]; } if (A[N-2] != 0) { A[N] = A[N - 2] + F(N - 1, A); return A[N]; } if (A[N-1] != 0) { A[N] = A[N - 1] + F(N - 2, A); return A[N]; } A[N] = F(N-1, A) + F(N-2, A); return A[N]; }