递归斐波那契记忆
我正在为大学的编程 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方法的结尾是主要问题。我不知道如何让它将数字递归地添加到数组的正确部分。
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);
}
}
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.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
![扫码二维码加入Web技术交流群](/public/img/jiaqun_03.jpg)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(15)
您需要区分字典中已计算的数字和未计算的数字,而您目前还没有这样做:您总是重新计算数字。
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.
与上面的大多数解决方案类似,但使用地图代替。
Similar to most solutions above but using a Map instead.
使用 Memoization 打印前 n 个斐波那契数的程序。
Program to print first
n
fibonacci numbers using Memoization.我相信您忘记了在字典中实际查找内容。
更改
为
,它工作得很好(我自己测试过:)
I believe you forget to actually look up stuff in your dictionary.
Change
to
and it works just fine (tested it myself :)
这是我对递归斐波那契记忆的实现。使用 BigInteger 和 ArrayList 可以计算第 100 项甚至更大的项。我尝试了第 1000 项,结果在几毫秒内返回,代码如下:
输出示例
Here is my implementation of recursive fibonacci memoization. Using BigInteger and ArrayList allows to calculate 100th or even larger term. I tried 1000th terms, and result is returned in a matter of milliseconds, here is the code:
Output example
这是一个利用记忆化概念的完全成熟的类:
请注意,它们
用于消除在每个递归函数调用时进行以下检查的必要性
。
Here is a fully-fledged class that leverages the memoization concept:
Notice that
are used to eliminate the necessity of the following check
at each recursive function call.
这是使用静态值数组来实现递归 fibonacci() 方法记忆的另一种方法 -
请注意,此方法使用全局(类级别)静态数组 fibArray[]。要查看整个代码和解释,您还可以看到以下内容 -
This is another way to approach memoization for recursive fibonacci() method using a static array of values -
Note that this method uses a global(class level) static array fibArray[]. To have a look at the whole code with explanation you can also see the following - http://www.javabrahman.com/gen-java-programs/recursive-fibonacci-in-java-with-memoization/
在 Swift 5.3 中,
这是使用记忆化的非常快的方法。
首先我初始化我的缓存字典。
然后我创建我的斐波那契数生成器。由于它是一个递归函数,因此理论上每次调用该函数都会再次计算整个斐波那契数列,直到达到请求的数字。这就是我们使用缓存来加速递归函数的原因:
我可以将序列保存在数组中,如下所示:
或者在循环中使用该函数。
In Swift 5.3
This is a very quick one using memoisation.
First I initialise my cache dictionary.
Then I create my Fibonacci number generator. Since it is a recursive function, every call to the function would theoretically compute the whole Fibonacci sequence again up to the requested number. This is why we use the cache, to speed up the recursive function:
I can save my sequence in an array like this:
Or use the function in a loop.
使用系统;
使用 System.Collections.Generic;
斐波那契命名空间
{
公开课斐波那契数列
{
}
using System;
using System.Collections.Generic;
namespace Fibonacci
{
public class FibonacciSeries
{
}
可能太旧了,但这是我的快速解决方案
Might be too old but here is my solution for swift
这是我的实现。
Here is my implementation.