Как найти число фибоначчи java

Определение чисел Фибоначчи

Числа Фибоначчи это последовательность натуральных чисел, которая начинается с чисел ноль и один, а каждое следующее число равно сумме двух предыдущих:

Первые 10 чисел Фибоначчи:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Получение первых n чисел Фибоначчи

Чтобы найти первые n чисел Фибоначчи, можно создать массив размера n, первые два элемента будут равны нулю и единице, а остальные элементы можно получить, используя цикл и вышеприведённую формулу:

int[] f = new int[n];
f[0] = 0;
f[1] = 1;
for (int i = 2; i < n; ++i) {
    f[i] = f[i - 1] + f[i - 2];
}

В коде предполагается существование переменной n, которую можно ввести с клавиатуры, например так:

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

После заполнения массива f полученные первые n чисел Фибоначчи можно вывести на экран с помощью цикла:

for (int i = 0; i < n; ++i) {
    System.out.println(f[i]);
}

Онлайн пример кода

Стоит заметить, что тип int в Java позволяет хранить только числа до 2³¹-1, поэтому вышеприведённым способом получится вычислить только первые 46 чисел Фибоначчи (при попытке вычислить сорок седьмое число Фибоначчи произойдёт переполнение и получится отрицательное число). Используя тип данных long вместо int без переполнения получится вычислить первые 91 число Фибоначчи. Чтобы вычислять последующие числа Фибоначчи можно воспользоваться классом BigInteger, который реализует длинную арифметику в Java.

Получения n-ого по счёту числа Фибоначчи

Для получения только n-ого числа Фибоначчи не обязательно использовать массив, достаточно завести две переменных a и b, в которых будут храниться последние два числа Фибоначчи, и пересчитывать эти переменные n - 2 раза:

int a = 0;
int b = 1;
for (int i = 2; i <= n; ++i) {
    int next = a + b;
    a = b;
    b = next;
}
System.out.println(b);

Онлайн пример кода

Рекурсивное вычисление чисел Фибоначчи

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

// функция, возвращающая n-ое число Фибоначчи
public static int f(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return f(n - 1) + f(n - 2);
    }
}

Онлайн пример кода

Рекурсивный способ работает за экспоненциальное время от n, например для n равного 46 рекурсивный способ работает дольше пяти секунд, а способ с запоминанием последних двух чисел Фибоначчи работает менее одной десятой секунды).

Рекурсивный способ может работать долго, потому что в процессе вычисления функция будет много раз вызываться от одного и того же аргумента (например, при вычислении f(5) функция сделает рекурсивные вызовы к f(4) и f(3), оба рекурсивных вызова обратятся к f(2)), что приведёт к многократному повторению одних и тех же операций.

Быстрое вычисление чисел Фибоначчи с помощью быстрого умножения матриц (используя O(log n) операций умножения)

Рассмотрим матрицу:

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

Расписывая это соотношение, получаем:

Таким образом, чтобы найти n-ое число Фибоначчи достаточно возвести матрицу A в степень n - 1. Это можно сделать алгоритмом быстрого возведения в степень.

// матричное умножение двух матриц размера 2 на 2
public static BigInteger[][] matrixMultiplication(BigInteger[][] a, BigInteger[][] b) {
    // [a00 * b00 + a01 * b10, a00 * b01 + a01 * b11]
    // [a10 * b00 + a11 * b10, a10 * b01 + a11 * b11]
    return new BigInteger[][]{
            {a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])), a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
            {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0])), a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))},
    };
}

// возведение матрицы размера 2 на 2 в степень n
public static BigInteger[][] matrixPowerFast(BigInteger[][] a, int n) {
    if (n == 0) {
        // любая матрица в нулевой степени равна единичной матрице
        return new BigInteger[][]{
                {BigInteger.ONE, BigInteger.ZERO},
                {BigInteger.ZERO, BigInteger.ONE}
        };
    } else if (n % 2 == 0) {
        // a ^ (2k) = (a ^ 2) ^ k
        return matrixPowerFast(matrixMultiplication(a, a), n / 2);
    } else {
        // a ^ (2k + 1) = (a) * (a ^ 2k)
        return matrixMultiplication(matrixPowerFast(a, n - 1), a);
    }
}

// функция, возвращающая n-ое число Фибоначчи
public static BigInteger fibonacci(int n) {
    if (n == 0) {
        return BigInteger.ZERO;
    }

    BigInteger[][] a = {
            {BigInteger.ONE, BigInteger.ONE},
            {BigInteger.ONE, BigInteger.ZERO}
    };
    BigInteger[][] powerOfA = matrixPowerFast(a, n - 1);
    // nthFibonacci = powerOfA[0][0] * F_1 + powerOfA[0][0] * F_0 = powerOfA[0][0] * 1 + powerOfA[0][0] * 0
    BigInteger nthFibonacci = powerOfA[0][0];
    return nthFibonacci;
}

public static void main(String[] args) {
    System.out.println(fibonacci(1024));
}

Онлайн пример кода

Содержание

1. Немного теории
2. Простая реализация на Java
3. Поддержка больших чисел
4. Рекурсивный вариант
5. Пример на Kotlin
6. Итоги

На собеседованиях по алгоритмам любят давать такую задачку, как нахождение чисел из последовательности Фибоначчи. Эта числовая последовательность названа в честь Леонардо Пизанского – известного математика Средневековья.

Сама последовательность довольно проста. Она состоит из целых положительных чисел, где каждый следующий элемент равен сумме двух предыдущих. Например, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2.

Последовательность начинается с 0 и 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …

Иногда в этой последовательности принято пропускать 0 и начинать её с двух единиц, однако официально она начинается именно с 0.

Эта последовательность описывает правило «золотого сечения», когда мы делим нечто целое на две неравные части, где целая часть так же пропорциональна бОльшей, как и бОльшая к меньшей.

Считается, что это правило также часто встречается в природе. Например, в спиралях раковины моллюска или в спирали Млечного Пути.

Давайте напишем метод, который будет возвращать число Фибоначчи по его индексу в этой последовательности. Числа в последовательности растут очень быстро, поэтому значения будем хранить в типе long.

public long getFibonacciByIndex(int index) {
    if (index == 0) {
        return 0; // первый элемент последовательности
    }
    if (index < 0 || index > 92) {
        // при индексе 93 происходит переполнение типа long
        throw new IndexOutOfBoundsException(index);
    }
    var n0 = 0L;
    var n1 = 1L;
    for (int i = 2; i <= index; i++) {
        var n2 = n0 + n1;
        n0 = n1;
        n1 = n2;
    }
    return n1;
}

Алгорим тут довольно простой: заводим первые два числа последовательности как n0 и n1. Затем в цикле, начиная с индекса 2, вычисляем новое значение как их сумму. Это новое значение становится n1, а то, что было n1 – становится n0. По достижении необходимого индекса выходим из цикла и возвращаем результат.

Обратите внимание на обработку пограничных случаев. Если индекс равен 0 – сразу возвращаем первый элемент последовательности, т.е. 0. Отрицательный индекс недопустим – кидаем стандартное исключение IndexOutOfBoundsException.

Также кидаем исключение, если индекс больше чем 92 – тут происходит переполнение типа long. При переполнении Java ошибку не кидает, но число при этом становится некорректным (например, отрицательным). Это связано со сдвигом и потерей части разрядов в двоичном представлении числа.

Теперь можем вызвать наш метод и посмотреть число Фибоначчи с индексом, например, 42.

public class Fibonacci {
    public static void main(String[] args) {
        var fibonacci = new Fibonacci();
        System.out.println(fibonacci.getFibonacciByIndex(42)); // выведет 267914296
    }
    // …
}

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

Ну а данная реализация работает довольно шустро и её единственный недостаток – это поддержка только первых 92 членов последовательности. Но что, если мы хотим вычислить элемент с индексом 100, 1000 или даже 1 000 000 ?

На помощь нам придёт класс BigInteger. Он довольно громоздкий с точки зрения скорости вычисления и с точки зрения написания кода, но при этом поддерживает сколь угодно большие числа. Поэтому заменим long на BigInteger. Желаемый номер элемента также будем передавать в метод как BigInteger.

public BigInteger getFibonacciByIndexInfinite(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) == 0) {
        return BigInteger.ZERO;
    }
    if (index.compareTo(BigInteger.ZERO) < 0) {
        throw new IndexOutOfBoundsException(index.toString());
    }
    var n0 = BigInteger.ZERO;
    var n1 = BigInteger.ONE;
    for (var i = BigInteger.TWO; i.compareTo(index) <= 0; i = i.add(BigInteger.ONE)) {
        var n2 = n0.add(n1);
        n0 = n1;
        n1 = n2;
    }
    return n1;
}

Обратите внимание, что тут мы уже не можем использовать числа типа 0 и 1. Вместо этого пишем константы BigInteger.ZERO и BigInteger.ONE. Сравнение чисел также усложняется – используем метод compareTo(). Для сложения вместо плюса пишем метод add(). Поскольку BigInteger поддерживает очень большие числа, то проверку на максимальный индекс убираем.

Теперь мы можем найти элемент с порядковым номером 1 000 000. Обратите внимание, что BigInteger можно инициализировать через текстовое представление числа.

System.out.println(fibonacci.getFibonacciByIndexInfinite(new BigInteger(«1000000»)));
// найденное число состоит из 208988 цифр!

Найденный результат представляет собой столь большое число, что оно не помещается на экран консоли! Даже на 20 экранов… Однако и это число на моём ноуте было вычислено всего-то за 15 секунд.

Согласитесь, вряд ли может потребоваться вычислять столь большие значения, поэтому можно считать, что даже с BigInteger алгоритм всё равно работает шустро.

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

public long getFibonacciByIndexRecursive(int n) {
    if (n == 0) {
        return 0L;
    }
    if (n == 1) {
        return 1L;
    } else {
        return getFibonacciByIndexRecursive(n — 1) + getFibonacciByIndexRecursive(n — 2);
    }
}

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

Как видите, рекурсивный алгоритм довольно компактен. Но у него есть один недостаток. Для рекурсии активно используется стек вызова методов. Вы можете довольно легко исчерпать его и получить StackOverflowError, запросив какой-нибудь большой индекс. Поэтому на практике я бы не рекомендовал рекурсивную версию.

В дополнение приведу этот же метод на Kotlin, чтобы продемонстрировать лаконичность его синтаксиса.

fun getFibonacciByIndexInfinite(index: BigInteger): BigInteger {
    if (index == BigInteger.ZERO) {
        return BigInteger.ZERO
    }
    if (index < BigInteger.ZERO) {
        throw IndexOutOfBoundsException(index.toString())
    }
    var n0 = BigInteger.ZERO
    var n1 = BigInteger.ONE
    var i = BigInteger.TWO
    while (i <= index) {
        val n2 = n0 + n1
        n0 = n1
        n1 = n2
        i++
    }
    return n1
}

Здесь всё ровно то же самое, только мы заменили цикл for на while. А также вернули обратно привычные нам операторы сравнения и инкремента. Теперь вызовем этот метод:

fun main() {
    println(Fibonacci().getFibonacciByIndexInfinite(BigInteger(«1000000»)))
}

Время вычисления не увеличилось по сравнению с Java-версией, поскольку компилятор Kotlin вызывает те же самые compareTo() и add(), генерируя почти такой же байт-код.

Мы рассмотрели несколько реализаций нахождения числа Фибоначчи по его индексу.

• Наиболее простая реализация на Java использует примитивный тип long. Он работает быстро, но уже на 93-м элементе последовательности происходит переполнение.

• Чтобы вычислять числа с бОльшим индексом, мы использовали класс BigInteger, который хоть и значительно медленнее примитива, но всё равно довольно шустро вычисляет огромные числа.

• Также узнали про рекурсивный вариант реализации, который выглядит просто, но приводит к переполнению стека вызовов для больших индексов последовательности.

• Наконец, мы рассмотрели реализацию на Kotlin. Благодаря лаконичному синтаксису метод выглядит менее громоздко и при этом не теряет в производительности.

В ряду Фибоначчи на Java следующее число является суммой двух предыдущих чисел. Первые два числа ряда Фибоначчи – 0 и 1.

Числа Фибоначчи в значительной степени используются в вычислительном исследовании времени выполнения алгоритма для определения наибольшего общего делителя двух целых чисел. В арифметике массив Wythoff представляет собой бесконечную матрицу чисел, являющуюся результатом последовательности Фибоначчи.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Java-код с использованием For

//Using  For Loop
public class FibonacciExample {
 
	public static void main(String[] args) 
	{
		// Set it to the number of elements you want in the Fibonacci Series
		 int maxNumber = 10; 
		 int previousNumber = 0;
		 int nextNumber = 1;
		 
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
 
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */
 
	      
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
 
	}
 
}

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

• previousNumber инициализируется до 0, а nextNumber инициализируется до 1
• Для цикла перебирает maxNumber
  • Показать предыдущий номер
  • Вычисляет сумму предыдущего и следующего номеров
  • Обновляет новые значения previousNumber и nextNumber

С использованием while

Вы также можете сгенерировать ряд Фибоначчи, используя цикл While в Java.

//Using  While Loop
public class FibonacciWhileExample {
 
	public static void main(String[] args) 
	{
	
		 int maxNumber = 10, previousNumber = 0, nextNumber = 1;
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
 
	        int i=1;
	        while(i <= maxNumber)
	        {
	            System.out.print(previousNumber+" ");
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	            i++;
	        }
 
	}
 
}

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

Единственное отличие в логике программы – использование цикла WHILE для вывода чисел Фибоначчи.

Ряд Фибоначчи, основанный на пользовательском вводе

//fibonacci series based on the user input
import java.util.Scanner;
public class FibonacciExample {
 
	public static void main(String[] args) 
	{
	
		 int maxNumber = 0; 
		 int previousNumber = 0;
		 int nextNumber = 1;
		 
		    System.out.println("How many numbers you want in Fibonacci:");
	        Scanner scanner = new Scanner(System.in);
	        maxNumber = scanner.nextInt();
	        System.out.print("Fibonacci Series of "+maxNumber+" numbers:");
 
	        for (int i = 1; i <= maxNumber; ++i)
	        {
	            System.out.print(previousNumber+" ");
	            /* On each iteration, we are assigning second number
	             * to the first number and assigning the sum of last two
	             * numbers to the second number
	             */
 
	      
	            int sum = previousNumber + nextNumber;
	            previousNumber = nextNumber;
	            nextNumber = sum;
	        }
 
	}
 
}

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

Через рекурсию

//Using Recursion
public class FibonacciCalc{
	public static int fibonacciRecursion(int n){
	if(n == 0){
		return 0;
	}
	if(n == 1 || n == 2){
			return 1;
		}
	return fibonacciRecursion(n-2) + fibonacciRecursion(n-1);
	}
    public static void main(String args[]) {
	int maxNumber = 10;
	System.out.print("Fibonacci Series of "+maxNumber+" numbers: ");
	for(int i = 0; i < maxNumber; i++){
			System.out.print(fibonacciRecursion(i) +" ");
		}
	}
}

Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

Рекурсивная функция – это функция, которая может вызывать себя сама.

fibonacciRecursion():

	fibonacciRecursion (4)  
	It will recursively call fibonacciRecursion function for values 2 and 3
		fibonacciRecursion (2) \ call for value 0 and 1
			fibonacciRecursion (0) = 0
			fibonacciRecursion (1) = 1
		fibonacciRecursion (3) \ It will call for 1 and 2
			fibonacciRecursion (1) = 1
			fibonacciRecursion (2) \ It will call for 0 and 1
				fibonacciRecursion (0) = 0
				fibonacciRecursion (1) = 1

Теперь результат добавлен 0 + 1 + 1 + 0 + 1 = 3.