Числа Фибоначчи

#java #алгоритм #математика

Что такое числа Фибоначчи?
Как найти первые n чисел Фибоначчи?

    

Ответы

Ответ 1

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

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







Первые 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 позволяет хранить только числа до 231-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));
}


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