Fibonacci Series in Java – 在Java中的斐波那契数列

最后修改: 2019年 12月 5日

中文/混合/英文(键盘快捷键:t)

1. Overview

1.概述

In this tutorial, we’ll look at the Fibonacci series.

在本教程中,我们将看一下斐波那契数列。

Specifically, we’ll implement three ways to calculate the nth term of the Fibonacci series, the last one being a constant-time solution.

具体来说,我们将实现三种方法来计算斐波那契数列的nth项,最后一种方法是恒定时间解。

2. Fibonacci Series

2.斐波那契系列

The Fibonacci series is a series of numbers in which each term is the sum of the two preceding terms. It’s first two terms are 0 and 1.

斐波那契数列是一个数列,其中每项都是前面两项之和。它的前两个项是01

For example, the first 11 terms of the series are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and 55.

例如,系列的前11项是0、1、1、2、3、5、8、13、21、34、55

In mathematical terms, the sequence Sn of the Fibonacci numbers is defined by the recurrence relation:

在数学上,斐波那契数的序列Sn是由递推关系定义的。

S(n) = S(n-1) + S(n-2), with S(0) = 0 and S(1) = 1

Now, let’s look at how to calculate the nth term of the Fibonacci series. The three methods we’ll be focusing on are recursive, iterative, and using Binet’s formula.

现在,让我们看看如何计算斐波那契数列的nth项。我们要关注的三种方法是递归法、迭代法和使用Binet的公式。

2.1. Recursive Method

2.1.递归法

For our first solution, let’s simply express the recurrence relation directly in Java:

对于我们的第一个解决方案,让我们简单地用Java直接表达递归关系。

public static int nthFibonacciTerm(int n) {
    if (n == 1 || n == 0) {
        return n;
    }
    return nthFibonacciTerm(n-1) + nthFibonacciTerm(n-2);
}

As we can see, we check whether n is equal to 0 or 1. If it true, then we return that value. In any other case, we recursively call the function to calculate the (n-1)th term and (n-2)th term and return their sum.

正如我们所看到的,我们检查n是否等于01.如果是真的,那么我们返回这个值。在其他情况下,我们递归调用函数来计算(n-1)项和(n-2)项并返回它们的总和。

Although the recursive method is simple to implement, we see that this method does a lot of repeated calculations. For instance, in order to calculate the 6th term, we make calls to calculate the 5th and the 4th term. Moreover, the call to calculate the 5th term makes a call to calculate the 4th term again. Because of this fact, the recursive method does a lot of redundant work.

虽然递归方法实现起来很简单,但我们看到这个方法做了很多重复计算。例如,为了计算6项,我们调用了计算54项。此外,计算5th项的调用会再次调用计算4th项。由于这一事实,递归方法做了很多多余的工作。

As it turns out, this makes its time complexity exponential; O(Φn) to be exact.

事实证明,这使得时间复杂度为指数级;O(Φn)是准确的。

2.2. Iterative Method

2.2.迭代法

In the iterative method, we can avoid the repeated calculations done in the recursive method. Instead, we calculate the terms of the series and store the previous two terms to calculate the next.

在迭代法中,我们可以避免在递归法中进行的重复计算。相反,我们计算数列的项,并存储前两个项来计算下一个

Let’s take a look at its implementation:

让我们来看看它的实施情况。

public static int nthFibonacciTerm(int n) {
    if(n == 0 || n == 1) {
        return n;
    }
    int n0 = 0, n1 = 1;
    int tempNthTerm;
    for (int i = 2; i <= n; i++) {
        tempNthTerm = n0 + n1;
        n0 = n1;
        n1 = tempNthTerm;
    }
    return n1;
}

Firstly, we check whether the term to be calculated is the 0th term or 1st term. If that is the case, we return the initial values. Otherwise, we compute the 2nd term using n0 and n1. Then, we modify the values of n0 and n1 variables to store the 1st term and 2nd term respectively. We keep on iterating until we have calculated the required term.

首先,我们检查要计算的项是否是0项或1项。如果是这样的话,我们返回初始值。否则,我们用n0n1计算2nd项。然后,我们修改n0n1变量的值,分别存储1st项和2nd项。我们不断地迭代,直到我们计算出所需的项。

The iterative method avoids repetitive work by storing the last two Fibonacci terms in variables. The time complexity and space complexity of the iterative method is O(n) and O(1) respectively.

迭代法通过在变量中存储最后两个斐波那契项来避免重复性工作。迭代方法的时间复杂度和空间复杂度分别为O(n) O(1)

2.3. Binet’s Formula

2.3.比奈特的公式

We have only defined the nth Fibonacci number in terms of the two before it. Now, we will look at Binet’s formula to calculate the nth Fibonacci number in constant time.

我们只定义了n个斐波那契数与它之前的两个数的关系。现在,我们来看看Binet的公式,以恒定时间计算nth斐波那契数。

The Fibonacci terms maintain a ratio called golden ratio denoted by Φ, the Greek character pronounced ‘phi’.

斐波那契条款保持着一个比率,称为黄金比率,用Φ,希腊字发音为’phi’.表示。

First, let’s look at how the golden ratio is calculated:

首先,让我们看看黄金比率是如何计算的。

Φ = ( 1 + √5 )/2 = 1.6180339887...

Now, let’s look at Binet’s formula:

现在,我们来看看Binet的公式

Sn = Φⁿ–(– Φ⁻ⁿ)/√5

Actually, this means that we should be able to get the nth Fibonacci number with just some arithmetic.

实际上,这意味着我们应该可以通过一些算术得到nth/em>斐波那契数。

Let’s express this in Java:

让我们用Java来表达。

public static int nthFibonacciTerm(int n) {
    double squareRootOf5 = Math.sqrt(5);
    double phi = (1 + squareRootOf5)/2;
    int nthTerm = (int) ((Math.pow(phi, n) - Math.pow(-phi, -n))/squareRootOf5);
    return nthTerm;
}

We first calculate the squareRootof5 and phi and store them in variables. Later, we apply Binet’s formula to get the required term.

我们首先计算squareRootof5phi,并将它们存储在变量中。之后,我们应用Binet的公式来得到所需的项。

Since we’re dealing with irrational numbers here, we’ll only get an approximation. Consequently, we’ll need to hold onto more decimal places for higher Fibonacci numbers to account for round-off error.

由于我们在这里处理的是无理数,我们只能得到一个近似值。因此,我们需要为更高的斐波那契数保留更多的小数位,以考虑到舍入误差。

We see that the above method calculates the nth Fibonacci term in constant time, or O(1).

我们看到,上述方法在恒定时间内计算出nth斐波那契项,即O(1)。

3. Conclusion

3.总结

In this brief article, we looked at the Fibonacci series. We looked at a recursive and an iterative solution. Then, we applied Binet’s formula to create a constant-time solution.

在这篇简短的文章中,我们看了斐波那契数列。我们看了一个递归和一个迭代的解决方案。然后,我们应用Binet的公式来创建一个恒定时间的解决方案。

As always, the full source code of the working examples is available over on GitHub.

一如既往,工作实例的完整源代码可在GitHub上获得over