«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.