递归Fibonacci memoization [英] Recursive Fibonacci memoization

问题描述

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

I need some help with a program I'm writing for my Programming II class at universtiy. The question asks that one calculates the Fibonacci sequence using recursion. One must store the calculated Fibonacci numbers in an array to stop unnecessary repeated calculations and to cut down to the calculation time.

我设法使程序在没有数组的情况下工作记忆，现在我正在努力实现这一点而且我被卡住了。我不确定如何构建它。我已经用Google搜索并浏览了一些书，但没有找到太多帮助我解决如何实施解决方案。

I managed to get the program working without the array and memorization, now I'm trying to implement that and I'm stuck. I'm not sure how to structure it. I've Googled and skimmed through some books but haven't found much to help me solve how to implement a 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);



}

}

以上是不正确的，我的fib方法的结束是主要问题。我不知道如何让它以递归的方式将数字添加到数组的正确部分。

The above is incorrect, the end of my fib method is the main problem. I've no idea how to get it to add the numbers recursively to the correctly parts of the array.

推荐答案

你需要区分已经计算的数字而不是字典中的计算数字，您目前没有：您始终重新计算数字。

You need to distinguish between already calculated number and not calculated numbers in the dictionary, which you currently don't: you always recalculate the numbers.

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

这篇关于递归Fibonacci memoization的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！