当前位置: 首页 > 面试题库 >

斐波那契数列中f(93)处的数字为负值,怎么办?

欧阳鸿德
2023-03-14
问题内容

我正在尝试打印斐波那契数列直到’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]范围内的任何整数。


问题答案:

您遇到了整数溢出:

 4660046610375530309 <-- term 91
+7540113804746346429 <-- term 92
====================
12200160415121876738 <-- term 93: the sum of the previous two terms
 9223372036854775808 <-- maximum value a long can store

为避免这种情况,请使用BigInteger,它可以处理任意数量的数字。
这是转换为use的实现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),因为即使适度的93也会x产生太大的结果,以至于任何Java原语都无法表示。



 类似资料:
  • 主要内容:递归生成斐波那契数列,总结公元 1202 年,意大利数学家莱昂纳多·斐波那契提出了具备以下特征的数列: 前两个数的值分别为 0 、1 或者 1、1; 从第 3 个数字开始,它的值是前两个数字的和; 为了纪念他,人们将满足以上两个特征的数列称为斐波那契数列。 如下就是一个斐波那契数列: 1 1 2 3 5 8 13 21 34...... 下面的动画展示了斐波那契数列的生成过程: 图 1 斐波那契数列 很多编程题目要求我们输

  • 题目链接 NowCoder 题目描述 求斐波那契数列的第 n 项,n <= 39。 <!--1}\end{array}\right." class="mathjax-pic"/> --> 解题思路 如果使用递归求解,会重复计算一些子问题。例如,计算 f(4) 需要计算 f(3) 和 f(2),计算 f(3) 需要计算 f(2) 和 f(1),可以看到 f(2) 被重复计算了。 递归是将一个问题划分

  • Python3 实例 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13,特别指出:第0项是0,第1项是第一个1。从第三项开始,每一项都等于前两项之和。 Python 实现斐波那契数列代码如下: 实例(Python 3.0+)# -*- coding: UTF-8 -*- # Filename : test.py # author by : www.runoob.com

  • 本文向大家介绍JavaScript中的斐波那契数列,包括了JavaScript中的斐波那契数列的使用技巧和注意事项,需要的朋友参考一下 斐波那契数是这样的数,使得该序列中前两个后的每个数字都是前两个的和。该系列从1、1开始。示例- 我们可以编写一个程序来生成nth,如下所示: 您可以使用以下方式进行测试: 这将给出输出- 让我们看看这些函数调用实际上是如何发生的- 当我们调用f(5)时,我们将调用

  • 一、题目 写一个函数,输入n,求斐波那契数列的第n项值。 斐波那契数列的定义如下: 二、解题思路 按照上述递推式,可以使用循环或递归的方式获取第n项式。 三、解题代码 public class Test { /** * 写一个函数,输入n,求斐波那契(Fibonacci) 数列的第n项 * @param n Fibonacci数的项数 * @ret

  • 问题内容: 我最初对程序进行了错误编码。我没有为程序返回范围内的斐波那契数(即startNumber 1,endNumber 20应该仅= 1和20之间的那些数字),而是为程序编写了显示范围内的所有斐波那契数(即startNumber 1,endNumber 20)显示=前20个斐波那契数字)。我以为我有一个确定的代码。我也看不出为什么会这样。 有人在我的第二部分中指出了这一点(由于重复而被关闭-