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
在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
通过流的前 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 将其打印到控制台。
看起来更酷,不是吗?
第一个元素为 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 个数字。通常,这只会使任务变得更容易,因为您可以轻松地适应以前的解决方案。那么,通过递归来解决问题怎么样?-
对于 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。事实上,与之前的解决方案一样,我们需要设置前两个元素元素。
-
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。
GO TO FULL VERSION