我正在尝试打印斐波那契数列直到'N'的数字。直到f(92)为止,所有工作均按预期进行,但是当我尝试获取f(93)的值时,值变成负数:“-6246583658587674878”。这怎么可能?下面的逻辑有什么错误?
public long fibo(int x){
long[] arr = new long[x+1];
arr[0]=0;
arr[1]=1;
for (int i=2; i<=x; i++){
arr[i]=arr[i-2]+arr[i-1];
}
return arr[x];
}
f(91) = 4660046610375530309
f(92) = 7540113804746346429
f(93) = -6246583658587674878
这是因为数据类型吗?我还要使用什么数据类型来打印最多N个数字的斐波那契数列? N可以是[0..10,000,000]范围内的任何整数。
最佳答案
您遇到了integer overflow:
4660046610375530309 <-- term 91
+7540113804746346429 <-- term 92
====================
12200160415121876738 <-- term 93: the sum of the previous two terms
9223372036854775808 <-- maximum value a long can store
为了避免这种情况,请使用
BigInteger
,它可以处理任意数量的数字。这是转换为使用
BigDecimal
的实现:public String fibo(int x){
BigInteger[] arr = new BigInteger[x+1];
arr[0]=BigInteger.ZERO;
arr[1]=BigInteger.ONE;
for (int i=2; i<=x; i++){
arr[i]=arr[i-2].add(arr[i-1]);
}
return arr[x].toString();u
}
请注意,返回类型必须为String(或BigInteger),因为即使
x
的值为93,也产生的结果对于任何Java原语都无法表示。