我正在尝试计算 𝐹𝑛 模 𝑚,其中 𝑛 可能非常大:高达 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));
}
}
最佳答案
这是对您的两个异常/错误的解释。
- OutOfMemoryError 异常:由于您正在尝试创建一个巨大的数组,远远超过了可能的大小。引用这个问题Do Java arrays have a maximum size?
- NegativeArraySizeException:由于您将 long 转换为整数(代码
long[] arr = new long[(int) n + 1];
)。读这个:Primitive data types . (基本上你在某个时候溢出,结果整数是负数)
关于java - 斐波那契 n 模 m,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39606533/