递归斐波那契记忆

本文介绍了递归斐波那契记忆的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我正在为大学编程 II 课程编写一个程序，我需要一些帮助.问题要求人们使用递归计算斐波那契数列.必须将计算出的斐波那契数列存储在数组中，避免不必要的重复计算，减少计算时间.

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.

我设法让程序在没有数组和记忆的情况下运行，现在我正在尝试实现它，但我被卡住了.我不确定如何构建它.我在谷歌上搜索并浏览了一些书籍，但没有找到多少可以帮助我解决如何实施解决方案的问题.

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