Ряд Фибоначчи в Java

1. Обзор

В этом уроке мы рассмотрим ряд Фибоначчи.

В частности, мы реализуем три способа вычисления n -го члена ряда Фибоначчи, последний из которых является решением с постоянным временем.

2. Ряд Фибоначчи

Ряд Фибоначчи представляет собой ряд чисел, в котором каждый член является суммой двух предыдущих членов . Первые два члена 0 и 1 .

Например, первые 11 членов ряда — это 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 и 55 .

С математической точки зрения последовательность чисел Фибоначчи S n определяется рекуррентным соотношением:

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

Теперь давайте посмотрим, как вычислить n -й член ряда Фибоначчи. Мы сосредоточимся на трех методах: рекурсивном, итеративном и использующем формулу Бине.

2.1. Рекурсивный метод

Для нашего первого решения давайте просто выразим рекуррентное отношение непосредственно в Java:

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

Как мы видим, мы проверяем, равно ли n 0 или 1. Если оно верно, то мы возвращаем это значение. В любом другом случае мы рекурсивно вызываем функцию для вычисления (n-1) -го термина и (n-2) -го термина и возвращаем их сумму.

Хотя рекурсивный метод прост в реализации, мы видим, что этот метод выполняет много повторяющихся вычислений. Например, для вычисления 6- го члена мы делаем вызовы для вычисления 5- го и 4- го членов. Более того, вызов для вычисления 5 - го члена снова вызывает вызов для вычисления 4-го члена. Из-за этого рекурсивный метод выполняет много избыточной работы.

Как оказалось, это делает временную сложность экспоненциальной; O(Φn ) , если быть точным.

2.2. Итерационный метод

В итеративном методе мы можем избежать повторных вычислений, выполняемых в рекурсивном методе. Вместо этого мы вычисляем члены ряда и сохраняем два предыдущих члена для вычисления следующего .

Давайте посмотрим на его реализацию:

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;
}

Во-первых, мы проверяем, является ли вычисляемый термин 0 -м или 1 -м термином. Если это так, мы возвращаем исходные значения. В противном случае мы вычисляем второй член , используя n0 и n1 . Затем мы изменяем значения переменных n0 и n1 для хранения 1 -го и 2 - го терминов соответственно. Мы продолжаем итерацию, пока не вычислим требуемый термин.

Итеративный метод позволяет избежать повторяющейся работы, сохраняя два последних члена Фибоначчи в переменных. Временная сложность и пространственная сложность итеративного метода составляют O (n) и O (1) соответственно.

2.3. Формула Бине

Мы только определили n -е число Фибоначчи в терминах двух предшествующих ему чисел. Теперь мы рассмотрим формулу Бине для вычисления n -го числа Фибоначчи за постоянное время.

Термины Фибоначчи поддерживают соотношение, называемое золотым сечением , которое обозначается буквой Φ , греческим символом, произносимым как «фи» .

Во-первых, давайте посмотрим, как рассчитывается золотое сечение :

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

Теперь давайте посмотрим на формулу Бине :

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

На самом деле это означает, что мы должны быть в состоянии получить n -е число Фибоначчи с помощью простых арифметических действий.

Давайте выразим это на 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;
}

Сначала мы вычисляем SquareRootof5 и phi и сохраняем их в переменных. Позже мы применяем формулу Бине, чтобы получить требуемый термин.

Поскольку здесь мы имеем дело с иррациональными числами, мы получим только приближение. Следовательно, нам нужно будет удерживать больше десятичных разрядов для более высоких чисел Фибоначчи, чтобы учесть ошибку округления.

Мы видим, что описанный выше метод вычисляет n -й член Фибоначчи за постоянное время, или O(1).

3. Заключение

В этой краткой статье мы рассмотрели ряд Фибоначчи. Мы рассмотрели рекурсивное и итеративное решение. Затем мы применили формулу Бине для создания решения с постоянным временем.

Как всегда, полный исходный код рабочих примеров доступен на GitHub .