Fibonacci n模m
Fibonacci n模m
提问于 2016-09-20 18:23:47
我试图计算模，这里可能很大:高达10^18，是第n位斐波纳契数，这是我的代码，它能很好地处理小数字，但是对于大的数字，它会抛出OutOfMemoryError或NegativeArraySizeException。
import java.util.*;
public class FibonacciHuge {
private static long getFibonacciHugeFast(long n, long m) {
long[] arr = new long[(int) n + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < n + 1; i++) {
arr[i] = (arr[i - 1] + arr[i - 2]) % m;
}
return arr[(int) n];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
System.out.println(getFibonacciHugeFast(n, m));
}
}回答 3
Stack Overflow用户
发布于 2016-09-20 18:34:09
这是你的两个异常/错误的解释。
- OutOfMemoryError例外:由于您正在尝试创建一个庞大的数组，远远超过了可能的大小。请参考这个问题Java数组有最大大小吗？
- NegativeArraySizeException:由于您正在将长转换为整数(代码
long[] arr = new long[(int) n + 1];)。读这个：原始数据类型。(基本上，在某一点上，你已经溢出了，所得到的整数是一个负数)
Stack Overflow用户
发布于 2016-09-20 21:56:38
如果n可以是10^18，那么即使不使用数组，它仍然会超时，因为您将运行一个循环直到n (即10^18)来计算第n个斐波那契数。
你可以使用矩阵指数法(线性递推法)。您可以在这博客中找到详细的解释和过程。运行时是O(log n)。
希望这会有帮助！
Stack Overflow用户
发布于 2016-09-20 22:15:22
您的代码有两个问题
- 您只需要知道fibonacci元素n-1和n-2就可以计算元素n，所以不需要数组，只需要两个变量。
- 因为(a + b) % m (a +b)%m(a+b+b% m)，你可以从n-1和n-2元素模m计算n-元素模m。事实上，你不能长时间存储10^18斐波纳契数，因为它的值很大--斐波纳契序列呈指数增长。这可能存在的唯一问题是，如果a%m+b%m溢出，所以应该将m限制为Long.MAX_VALUE / 2，因为您不知道只知道n的实际元素有多大，或者可以在函数中添加溢出检查。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39606533
复制相关文章
相似问题
腾讯云开发者
