文章
开始
开始学习
JavaRush /Java 博客 /Random-ZH /Java 程序员应该了解哪些关于斐波那契数的知识
Эллеонора Керри
第 41 级

Java 程序员应该了解哪些关于斐波那契数的知识

已在 Random-ZH 群组中发布
通常在面试过程中，尤其是在外企，人们可能会被问及算法，而在压力很大的情况下，疯狂地记住一些东西并不总是那么容易。因此，你需要做好准备。首先，至少刷新一下你对基本算法的记忆。今天我们将分析斐波那契数列这样的现象以及与之相关的问题的最常见变体。 斐波那契数是一个以数字 0 和 1 开头的自然数序列，后续的每个数字都等于前两个数字之和：
F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F 0 = 0, F 1 = 1, F n = F n - 1 + F n - 2 ;
n ≥ 0，n ∈ Z

值得注意的是，有时会省略 0，并且级数以 1 1 2 3 开始...通常，在问题的条件下，会立即指定级数以哪一个前两个数字开始（0.1 或 1.1），因此，我们将进一步考虑这两种情况的解决方案。

在Java中获取前n个斐波那契数

假设我们有一个任务来获取前 n 个斐波那契数。

  • 案例0.1：

    某个数字 n 来到我们身边：

    int[] arr = new int[n];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}

    我们创建一个大小为 n 的数组。前两个元素将等于 0 和 1，其余元素是通过执行此循环并使用数组中的先前数字获得的。

    我们显示：

    for (int i = 0; i < arr.length; ++i) {
  System.out.println(arr[i]);
}

    设置int n = 10；

    我们得到：

    
0
1
1
2
3
5
8
13
21
34

  • 对于情况 1.1，解决方案实际上没有什么不同：

    int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}

    我们需要更改的只是数组 arr[0] 的第一个元素：从 0 到 1。相应地，前 10 个元素将是：

    
1
1
2
3
5
8
13
21
34
55
Java-университет

通过流的前 n 个斐波那契数

但我们想展示我们的水平。那么让我们看看使用Stream 的解决方案会是什么样子。

  • 对于 0.1：

    Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
   .limit(n)
   .map(y -> y[0])
   .forEach(x -> System.out.println(x));

    Stream类的静态 iterate 方法返回一个无限有序流，该流是通过将该函数应用于初始数组 arr 而创建的。在我们的例子中，该功能是根据前一个数组设置组成每个新数组的规则。结果，我们将得到一个数组流：

    {0,1}
{1,1}
{1, 2}
{2, 3}
{3, 5}
{5, 8}
{8, 13}
{13, 21}
{21, 34}
{34, 55}
…..

    但它们的数量是无限的，因此使用 .limit(n) 我们将元素的数量减少到前 n （在我们的例子中减少到 10）。

    但是，我们不需要数组流，因此使用 .map(y -> y[0]) 我们选择每个数组的第一个元素并获取包含我们需要的数字的流，并使用 forEach 将其打印到控制台。

    看起来更酷，不是吗？

    Java 程序员应该了解的斐波那契数知识 - 2第一个元素为 1,1，此代码也几乎相同： 

    Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));

    同样，差异在于初始元素：我们设置了 {1, 1}，而不是 {0, 1}

    实际上，结果将与前面的示例相同。

斐波那契数列之和

如果我们被要求获得直到第 n 个元素（含第 n 个元素）的斐波那契数列之和，该怎么办？这不应该给我们带来任何困难。让我们采用流的解决方案，并将 forEach 替换为其他几个方法：

  • 对于 0.1：

    int n = 10;
int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(t -> t[0])
     .mapToInt(Integer::intValue)
     .sum();
System.out.println(result);

    使用 .mapToInt(Integer::intValue) 我们将流转换为数字 IntStream 并使用其 .sum() 方法来获取所有元素的总和。

  • 对于初始元素为 1,1 的情况，我们设置 {1, 1}，而不是 {0, 1}。

获取斐波那契数列中的第 n 个数字

有时，系统会要求您打印的不是一系列数字，而是打印斐波那契数列中的第 n 个数字。通常，这只会使任务变得更容易，因为您可以轻松地适应以前的解决方案。那么，通过递归来解决问题怎么样？

  1. 对于 0.1：

    public int getFibonacciValue(int n) {
  if (n <= 1) {
     return 0;
  } else if (n == 2) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}

    要使用 0,1 运行算法，需要指定当我们尝试获取第一个元素时，我们获取 0，第二个元素获取 - 1。事实上，与之前的解决方案一样，我们需要设置前两个元素元素。

  2. 1.1 的实现会略有不同：

    public int getFibonacciValue(int n) {
  if (n == 0) {
     return 0;
  } else if (n == 1) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}

    在这种情况下，我们只需将第一个元素设置为 1，因为第二个元素将相同，并且该方法的响应将相同。

    同时，我们将方法的反应设置为0，因为如果我们不设置它，那么当2作为参数时，会递归调用相同的方法，但参数为0。接下来，将启动相同的方法，但为负数，依此类推，直到负无穷大。结果，我们将收到一个 StackOverflowError。

但是，不建议使用递归方法，因为与之前的以线性 O(n) 时间运行的方法不同，递归方法可能需要更长的时间才能完成。为什么？ Java 程序员应该了解的斐波那契数知识 - 3递归方法可能需要很长时间，因为在计算过程中，同一参数会多次调用该函数。例如，在计算 getFibonacciValue(7) 时，该函数将递归调用 getFibonacciValue(5) 和 getFibonacciValue(6)，这两个递归调用都会调用 getFibonacciValue(4)），这将导致多次调用相同的操作。在面试时，你可以展示这个方法作为解决方案，但同时谈论它的缺点并提供另一种方法作为回报。还值得注意的是，Java 中的 int 类型允许存储从 -2147483648 到 2147483647 的范围，因此您只能计算前 46 个斐波那契数：如果我们尝试获取下一个 47 个数，则会出现溢出，并且我们会得到一个负数。如果我们使用 long 数据类型而不是 int，我们将能够正确计算前 91 个斐波那契数。要计算后续的斐波那契数，您需要使用 BigInteger 类，该类实现了真正 BIG 数的存储和算术运算的逻辑。
评论
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION