使用流和大整数计算斐波那契数

Question

我有以下代码来计算位置10处的斐波那契数：

IntStream.range(1,10)
.mapToObj(ignore ->     List.Of(BigInteger.One, BigInteger.One)
.reduce(List.Of(BigInteger.One, BigInteger.One), (values,ignore) -> ???)
.get(1)

如何替换代码中的问号？

我必须仅使用函数式编程来实现它。

Answer 1

你需要的 lambda 是：

(values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1)))

将列表[a, b]转换为[b, a+b]。

但是，代码中存在一些编译错误：

• 这List.of()不是List.Of()
• 这BigInteger.ONE不是BigInteger.One

还有一个逻辑错误：第一个斐波那契数是 0，而不是 1，所以要以IntStream.range(1, n)开头返回第 n 个斐波那契数，累加器必须List.of(BigInteger.ZERO, BigInteger.ONE)，而不是List.of(BigInteger.ONE, BigInteger.ONE)。

完整的工作代码是：

BigInteger fibonacci = IntStream.range(1, 10)
.mapToObj(ignore -> List.of(BigInteger.ZERO))
.reduce(
List.of(BigInteger.ZERO, BigInteger.ONE),
(values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1)))
).get(0);

返回34，这是第 10 个斐波那契数。

---

与其使用IntStream#range()，更简单的方法是使用Stream#generate()生成起始列表并应用limit(n)，使用上面的相同 lambda：

BigInteger fibonacci = Stream.generate(() -> List.of(BigInteger.ZERO, BigInteger.ONE))
.limit(10)
.reduce((values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1))))
.get().get(0);

还返回34.

Answer 2

如果你打算将此代码用于相对较小的输入数字，如10，使用BigInteger似乎是不合理的。

否则，为序列的每个成员创建新列表在性能方面是有害的。最好只创建一个列表一次，然后重复使用它。

不幸的是，List.of()返回了一个不可变的列表，为了使它可变，你用一个ArrayList包装它，笨拙的代码变得更加笨拙......

相反，我建议使用如下所示的数组，这将使代码性能更高且更容易推理。

public static BigInteger getFib(int num) {
return Stream.iterate(new BigInteger[]{BigInteger.ZERO, BigInteger.ONE}, // the only array created in the stream
arr -> {arr[1] = arr[0].add(arr[1]);      // calculating the next member of the sequence
arr[0] = arr[1].subtract(arr[0]); // calculating the previous member of the sequence
return arr;})                     // returning the same array
.limit(num - 1)
.reduce((left, right) -> right)
.map(arr -> arr[1])
.orElse(BigInteger.ZERO);
}

main()

public static void main(String[] args) {
List<BigInteger> result = // generating a list Fibonacci numbers for demo purposes
IntStream.rangeClosed(1, 10)
.mapToObj(num -> getFib(num))
.collect(Collectors.toList());
System.out.println(result);
}

输出

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Answer 3

要计算斐波那契数列的Nth项，您可以这样做。不涉及任何列表，因为它们是动态计算的，并且只打印或返回Nth列表。这通过初始化a[ 0, 1 ]数组并生成后续的[ a[1], a[0] + a[1] ]数组来工作，以便a[0]用作系列中的术语。仓位从1开始，如果不足，可以更改。

• 定义位置(必须为>= 1)或(即>= 第一个位置)
• 使用数组迭代序列。
• 跳过流中的前position - 1术语。
• 然后打印下一个(或分配它)

int position = 10;
Stream.iterate(new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
(a) -> new BigInteger[] { a[1], a[0].add(a[1]) })
.skip(position-1).limit(1)
.map(a->a[0]).forEach(System.out::println);
}

指纹

34

要分配它，请将forEach更改为findFirst().get().并分配给BigInteger。

在这里，我已将其包含在一种方法中。

public static BigInteger getFibTerm(int position) {
if (position < 1) {
throw new IllegalArgumentException("position must be >= 1");
}
return Stream.iterate(
new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
(a) -> new BigInteger[] { a[1], a[0].add(a[1]) })
.skip(position - 1).limit(1).map(a -> a[0])
.findFirst().get();
}