Часто на собеседованиях, особенно в иностранных компаниях, могут расспрашивать об алгоритмах, а в стрессовой ситуации судорожно что-то вспоминать бывает не всегда просто. Поэтому нужно готовиться. Для начала, хотя бы освежить в памяти основные алгоритмы. Сегодня мы разберем такое явление как числа Фибоначчи и наиболее встречаемые варианты задач, связанных с ними. Числа Фибоначчи — это последовательность натуральных чисел, которая начинается с чисел ноль и один, а каждое последующее число равно сумме двух предыдущих:
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
Java-университет

Первые 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)), что и приведёт к многоразовому вызову одних и тех же операций. На собеседовании можно показать этот способ как вариант решения, но при этом рассказать об этих его недостатках и взамен предложить другой способ. Также стоит отметить, что тип int в Java позволяет хранить от -2147483648 до 2147483647, поэтому получится вычислить только первые 46 чисел Фибоначчи: при попытке получить следующее 47-ое возникнет переполнение, и мы получим отрицательное число. Если же мы будем использовать тип данных long вместо int, то получится правильно вычислить первые 91 число Фибоначчи. Чтобы вычислять последующие числа Фибоначчи, необходимо воспользоваться классом BigInteger, который реализует логику хранения и арифметических операций действительно БОЛЬШИХ чисел.
Python-университет