Java 斐波那契数列

上次修改时间：2024 年 2 月 24 日

在本文中，我们将展示如何在 Java 中计算斐波那契数列。我们创建了几种计算斐波那契数列的算法。

斐波那契数列是一个值的序列，其中每个数字是前两个数字的和，从 0 和 1 开始。该序列的开头是：0、1、1、2、3、5、8、13、21、34、55、89、144 ...

在本文中，我们将展示几种在 Java 中生成斐波那契数列的方法。由于斐波那契数列是无限数字序列，我们使用 BigInteger 类型进行计算。

斐波那契经典循环示例

第一个算法使用 for 循环。

import java.math.BigInteger;

BigInteger fibonacci(int n) {

    if (n <= 1) {
        return BigInteger.valueOf(n);
    }

    BigInteger previous = BigInteger.ZERO, next = BigInteger.ONE, sum;

    for (int i = 2; i <= n; i++) {

        sum = previous;
        previous = next;
        next = sum.add(previous);
    }

    return next;
}

void main() {

    for (int i = 0; i <= 99; i++) {

        BigInteger val = fibonacci(i);
        System.out.println(val);
    }
}

该示例打印斐波那契数列的前一百个值。

斐波那契递归示例

在第二个示例中，我们使用递归算法计算斐波那契数列，其中 fibonacci 方法调用自身进行计算。

import java.math.BigInteger;

BigInteger fibonacci(int n) {

    if (n == 0 || n == 1) {

        return BigInteger.ONE;
    }

    return fibonacci(n - 2).add(fibonacci(n - 1));
}

void main() {

    for (int i = 0; i < 10; i++) {
        System.out.println(fibonacci(i));
    }
}

该示例计算斐波那契数列的前十个值。

BigInteger fibonacci(int n) {

    if (n == 0 || n == 1) {

        return BigInteger.ONE;
    }

    return fibonacci(n - 2).add(fibonacci(n - 1));
}

该算法以递归方式构建。这意味着 fibonacci 方法调用自身来计算这些值。

斐波那契流示例

第三个示例使用流进行计算。

import java.math.BigInteger;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

List<BigInteger> fibonacci(int limit) {

    var vals = Stream.iterate(new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
            t -> new BigInteger[] { t[1], t[0].add(t[1]) })
            .limit(limit)
            .map(n -> n[1])
            .collect(Collectors.toList());

    return vals;
}

void main() {

    System.out.println(fibonacci(100));
}

此示例计算达到某个限制的值。

var vals = Stream.iterate(new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
        t -> new BigInteger[] { t[1], t[0].add(t[1]) })
        .limit(limit)
        .map(n -> n[1])
        .collect(Collectors.toList());

Stream.iterate 方法生成一个无限的顺序有序 Stream，该 Stream 通过将函数 f 迭代应用于初始元素种子而生成，从而生成一个由种子、f(seed)、f(f(seed)) 等组成的 Stream。

该函数（以 t -> new BigInteger[] { t[1], t[0].add(t[1]) } lambda 形式）添加序列的最后两个值。limit 方法将序列截断为 limit 个值。 map 方法从数组中选择下一个斐波那契值。最后，我们使用 collect 将序列转换为列表。

来源

斐波那契数列

在本文中，我们展示了如何在 Java 中以三种不同的方式计算斐波那契数列：经典循环、递归算法和函数式方式。

作者

我叫 Jan Bodnar，是一位充满激情的程序员，拥有丰富的编程经验。 我自 2007 年以来一直在撰写编程文章。到目前为止，我已经撰写了超过 1,400 篇文章和 8 本电子书。 我拥有超过十年的编程教学经验。

列出所有Java教程。