递归斐波那契记忆

math java recursion fibonacci

2022-09-03 16:35:16

我需要一些帮助，我正在为我在大学的编程II课程编写一个程序。这个问题要求人们使用递归计算斐波那契数列。必须将计算出的斐波那契数列存储在数组中，以停止不必要的重复计算并缩短计算时间。

我设法让程序在没有数组和记忆的情况下工作，现在我正试图实现这一点，但我卡住了。我不知道如何构建它。我已经谷歌并浏览了一些书籍，但没有找到太多帮助我解决如何实施解决方案的问题。

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方法的结束是主要问题。我不知道如何让它以递归方式将数字添加到数组的正确部分。

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

答案 2

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; 

}

与上面的大多数解决方案类似，但使用地图代替。