Что должен знать программист на Java о числах Фибоначчи

Статья из группы Java Developer
участников
Часто на собеседованиях, особенно в иностранных компаниях, могут расспрашивать об алгоритмах, а в стрессовой ситуации судорожно что-то вспоминать бывает не всегда просто. Поэтому нужно готовиться. Для начала, хотя бы освежить в памяти основные алгоритмы. Сегодня мы разберем такое явление как числа Фибоначчи и наиболее встречаемые варианты задач, связанных с ними. Числа Фибоначчи — это последовательность натуральных чисел, которая начинается с чисел ноль и один, а каждое последующее число равно сумме двух предыдущих:
F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...}
F0 = 0, F1 = 1, Fn = Fn - 1 + Fn - 2;
n ≥ 0, n ∈ Z

Стоит отметить, что иногда 0 опускается, и ряд начинается с 1 1 2 3… Как правило в условиях задачи сразу уточняется, с каких первых двух чисел начинается ряд (0,1 или 1,1), поэтому дальше мы будем рассматривать решения для обоих случаев.

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

Предположим, у нас есть задача по получению первых n чисел Фибоначчи.
  • случай 0,1:

    К нам приходит некое число n:

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

    Мы создаём массив размера n. Первые два элемента будут равны нулю и единице, а остальные элементы получаем, проходясь по данному циклу и используя предыдущие числа из массива.

    И выводим на экран:

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

    Задаем int n = 10;

    И получаем:

    
    0
    1
    1
    2
    3
    5
    8
    13
    21
    34
    
  • для случая 1,1 решение фактически не отличается:

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

    Всё, что нам нужно было изменить — это первый элемент массива arr[0]: с 0 на 1. Соответственно, первые 10 элементов будут:

    
    1
    1
    2
    3
    5
    8
    13
    21
    34
    55
    

Первые n чисел Фибоначчи через stream

Но мы же хотим показать свой уровень. Поэтому давайте посмотрим, как будем выглядеть данное решение с использованием stream.
  • для 0,1:

    Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
       .limit(n)
       .map(y -> y[0])
       .forEach(x -> System.out.println(x));

    Статический метод iterate класса Stream возвращает бесконечный упорядоченный поток, созданный применением функции к начальному массиву arr. В нашем случае в качестве функции служит задание правила составления каждого нового массива, основываясь на предыдущем. Как итог мы получим поток из массивов:

    {0,1}
    {1,1}
    {1, 2}
    {2, 3}
    {3, 5}
    {5, 8}
    {8, 13}
    {13, 21}
    {21, 34}
    {34, 55}..

    Но их будет бесконечное количество, и поэтому с помощью .limit(n) мы урезаем количество элементов до первых n (в нашем случае до 10).

    Однако нам не нужен поток массивов, поэтому с помощью .map(y -> y[0]) мы отбираем по первому элементу каждого массива и получаем поток с необходимыми нам числами и с помощью forEach выводим на консоль.

    Выглядит покруче, не так ли?

    Что должен знать программист на Java о числах Фибоначчи - 2при первых элементах 1,1 этот код также будет почти таким же:

    Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
         .limit(n)
         .map(y -> y[0])
         .forEach(x -> System.out.println(x));

    Опять же, различия — в начальном элементе: вместо {0, 1} задаём {1, 1}

    Собственно, результаты будут такими же, как и в предыдущем примере.

Сумма чисел Фибоначчи

А что если нас попросили получить сумму чисел Фибоначчи по n-ый элемент включительно? Это не должно вызвать у нас трудностей. Возьмем решение со стримом, заменим forEach на пару других методов:
  • для 0,1:

    int n = 10;
    int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
         .limit(n)
         .map(t -> t[0])
         .mapToInt(Integer::intValue)
         .sum();
    System.out.println(result);

    C помощью .mapToInt(Integer::intValue) мы переводим наш stream в числовой IntStream и с помощью его метода .sum() получаем сумму всех элементов.

  • для случая с 1,1 начальным элементом вместо {0, 1} задаём {1, 1}.

Получение n-ого число в ряде Фибоначчи

Иногда просят вывести не ряд чисел, а именно n-ое число в ряде Фибоначчи. Как правило это только облегчает задачу, ведь можно легко адаптировать предыдущие решения для этого. Ну а как насчёт решения задачи через рекурсию?
  1. для 0,1:

    public int getFibonacciValue(int n) {
      if (n <= 1) {
         return 0;
      } else if (n == 2) {
         return 1;
      } else  {
         return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
      }
    }

    Для выполнения алгоритма с 0,1 необходимо задать, что при попытке получить первый элемент мы получаем 0, а второй — 1. По сути нам, как и в прошлых решениях, нужно задать первые два элемента.

  2. реализация для 1,1 будет немного отличаться:

    public int getFibonacciValue(int n) {
      if (n == 0) {
         return 0;
      } else if (n == 1) {
         return 1;
      } else  {
         return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
      }
    }

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

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

Тем не менее, рекурсивный способ не рекомендуется использовать, потому что в отличие от предыдущих способов, которые работают за линейное время от O(n), рекурсивный способ может работать значительно дольше. Почему? Что должен знать программист на Java о числах Фибоначчи - 3Рекурсивный способ может работать долго, так как в процессе расчёта функция будет много раз вызываться от одного и того же аргумента. Например, при вычислении getFibonacciValue(7) функция сделает рекурсивные вызовы к getFibonacciValue(5) и getFibonacciValue(6), оба рекурсивных вызова будут обращаться к getFibonacciValue(4)), что и приведёт к многоразовому вызову одних и тех же операций. Что должен знать программист на Java о числах Фибоначчи - 4На собеседовании можно показать этот способ как вариант решения, но при этом рассказать об этих его недостатках и взамен предложить другой способ. Также стоит отметить, что тип int в Java позволяет хранить от -2147483648 до 2147483647, поэтому получится вычислить только первые 46 чисел Фибоначчи: при попытке получить следующее 47-ое возникнет переполнение, и мы получим отрицательное число. Если же мы будем использовать тип данных long вместо int, то получится правильно вычислить первые 91 число Фибоначчи. Чтобы вычислять последующие числа Фибоначчи, необходимо воспользоваться классом BigInteger, который реализует логику хранения и арифметических операций действительно БОЛЬШИХ чисел.
Комментарии (12)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Alexey Belyashkin
Уровень 8, Москва, Russian Federation
позавчера, 17:14
Когда делаю так ругается что Cannot resolve symbol 'n' int[] arr = new int[n]; arr[0] = 0; arr[1] = 1; for (int i = 2; i < arr.length; ++i) { arr[i] = arr[i - 1] + arr[i - 2]; }
wan-derer.ru
Уровень 40, Москва, Россия
27 февраля, 17:56
Думаю, к теме рекурсии надо добавить рекурсию с буферизацей. Смысл в том чтобы вместо многократного вызова функции с одним и тем же параметром вычислить его однократно и сохранить, а когда он нужен - взять из буфера. Минус - требуется дополнительная память. Плюс - кардинальное ускорение.
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fib {
    public static void main(String[] args) {

        long start = System.nanoTime();
        System.out.println(fib(40) + "\t" + (System.nanoTime() - start) + " нс");
        start = System.nanoTime();
        System.out.println(fibRec(40) + "\t" + (System.nanoTime() - start) + " нс");
        start = System.nanoTime();
        System.out.println(fibRecBuf(40) + "\t" + (System.nanoTime() - start) + " нс");
    }

    private static BigInteger fib(int n) {
        BigInteger fib1 = new BigInteger("0");
        BigInteger fib2 = new BigInteger("1");

        for (int i = 3; i <= n; i++) {
            BigInteger temp = fib1.add(fib2);
            fib1 = fib2;
            fib2 = temp;
        }

        return fib2;
    }

    private static BigInteger fibRec(int n) {
        if (n <= 1) return BigInteger.ZERO;
        if (n == 2) return BigInteger.ONE;
        return fibRec(n - 1).add(fibRec(n - 2));
    }


    static Map<Integer, BigInteger> fibs = new HashMap<>();

    private static BigInteger fibRecBuf(int n) {
        if (n <= 1) return BigInteger.ZERO;
        if (n == 2) return BigInteger.ONE;

        if (fibs.get(n - 1) == null) fibs.put(n - 1, fibRecBuf(n - 1));
        if (fibs.get(n - 2) == null) fibs.put(n - 2, fibRecBuf(n - 2));
        return fibs.get(n - 1).add(fibs.get(n - 2));
    }
}
Artem Kirillov безработный мужчина в самом расцвете сил
10 июля 2021, 16:05
Видел пример с рекурсией, не могу понять почему n уменьшается с n до единицы.
private static long fibNaive(int n, long[] mem) {
    if (mem[n] != -1) {
        return mem[n];
    }

    if (n <= 1) {
        return n;
    }

    long result = fibNaive(n - 1, mem) + fibNaive(n - 2, mem);
    mem[n] = result;

    return result;
}
Wally Dator
Уровень 26, Чехов, Россия
24 июня 2020, 21:17
про 46 и 91 число - спасибо
Илья
Уровень 2, Минск
24 июня 2020, 18:27
👍
AButrym
Уровень 1, Харьков
24 июня 2020, 10:55
Если вас попросят получать сумму первых n чисел Фибоначи, то проявите немножко аналитических способностей и вместо прямого суммирования попробуйте вначале получить формулу рекурсии для суммы чисел Фибоначи, и только после этого итерируйте по этой формуле.
Стас Пасинков Software Developer в Zipy Master
24 июня 2020, 15:09
рекурсия - зло
AButrym
Уровень 1, Харьков
25 июня 2020, 13:20
Формулу рекурсии можно не сверху вниз, а снизу вверх раскручивать - всё будет ОК.
Стас Пасинков Software Developer в Zipy Master
25 июня 2020, 13:38
яисрукер - все-равно зло))) если рекурсию можно заменить циклом (а это можно сделать практически в каждом случае) - лучше сделать через цикл :) уметь сделать через рекурсию - да, надо. но действительно использовать ее - лучше нет)
Антон Инженер в Транстелематика
24 июня 2020, 09:38
Познавательно!
Сергей
Уровень 23, Москва
24 июня 2020, 07:43
Спасибо за информацию
Дима
Уровень 41, Хабаровск, Россия
24 июня 2020, 07:41
🙄