java - 获取斐波那契数的总和的代码
问题描述
我正在尝试制作一个简单的递归代码来计算斐波那契级数的总和,但我不知道如何使计数器正常工作,这是我的代码:
public static long fibonacciRecursiveHits(int n,long sum)
{
if (n>1)
{
sum++;
sum = fibonacciRecursiveHits(n-1,sum) + fibonacciRecursiveHits(n-2,sum);
}
return sum;
}
例子:
Input: 4
Correct Output: 4 //The number of sums
My Output: 12
解决方案
您的问题是您正在计算 n 的总和数,并且您将其添加到 n+1 和 n+2 的总和中,这使您多次计算它们。
简单的解决方案:返回总和数
只需计算 n 的总和数,而不将它们传递下去。试试这个例如:
public static long fibonacciRecursiveHits(int n)
{
if (n>1)
{
return fibonacciRecursiveHits(n-1) + fibonacciRecursiveHits(n-2) + 1;
} else {
return 0;
}
}
我们在这里做什么:如果 n > 1,我们计算 n-1 的所有总和加上 n-2 的总和加上这个总和(1 总和)。
替代方案:传递参数
如果您想将 sum 作为参数传递并递归更新它,您可以,但并非没有技巧,因为Java 是 pass-by-value,这意味着如果您在函数中修改 sum,它不会被修改呼叫者,召集者。有几种方法可以解决此问题。
- 创建一个包含该对象的对象
int sum
并将其向下传递 - 创建一个静态变量 sum,以便您可以在类中的任何地方修改它
- 创建一个包含一个元素的数组并将其向下传递
- 此答案中描述的其他方式
这是有关如何使用选项 3 执行此操作的示例:
public static void fibonacciRecursiveHits(int n, long[] sum)
{
if (n>1)
{
sum[0]++;
fibonacciRecursiveHits(n-1, sum);
fibonacciRecursiveHits(n-2, sum);
}
}
发生的情况是,每次调用总和都会增加总和。
现在你这样称呼它:
long[] sum = {0};
fibonacciRecursiveHits(4, sum);
System.out.println(sum[0]); //sum[0] contains your result
迭代解决方案
上述递归解决方案的问题是它们具有指数运行时间 O(2^n),这意味着在中到大型输入上会非常慢。另一种方法是迭代地构建结果并将它们保存在数组中(动态编程)。这将运行时间减少到 O(n)。
public static long fibonacciRecursiveHits(int n)
{
long[] sums = new long[n+1];
// sums[0] and sums[1] are both initialized to 0
for(int i = 2; i <= n; i++){
sums[i] = sums[i-2] + sums[i-1] + 1;
}
return sums[n];
}
推荐阅读
- php - 我在我的页面的 php 登录中添加一个简单的记住我功能时遇到问题?
- ruby - Ruby类的未知方法`add`
- python - Python - 从日志文件中打印错误文本
- python - Google Colab:将大文件保存到团队驱动器
- promisekit - PromiseKit 出错的正确方法
- batch-file - 如何打开“运行”对话框,其中已有文件在框中
- mysql - ODBC select query with text field return no record
- javascript - 从 url 到 HTML 的 JSON
- c# - 使用同名 DLL 构建 .NET Core 项目时出现“找不到项目信息”错误
- python - 使用 AngularJS 在表中动态生成列