«Ряд Фибоначчи в Java» - Spring на русском

«1. Обзор

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

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

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

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

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

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

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

Во-первых, мы проверяем, является ли вычисляемый термин нулевым или первым. Если это так, мы возвращаем исходные значения. В противном случае мы вычисляем второй член, используя 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.

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