Що повинен знати програміст на Java про числа Фібоначчі

Часто на співбесідах, особливо в іноземних компаніях, можуть розпитувати про алгоритми, а в стресовій ситуації судомно щось згадувати не завжди просто. Тож треба готуватися. Для початку хоча б освіжити в пам'яті основні алгоритми. Сьогодні ми розберемо таке явище як числа Фібоначчі і варіанти завдань, що найбільше зустрічаються, пов'язаних з ними. Числа Фібоначчі - це послідовність натуральних чисел, яка починається з чисел нуль і один, а кожне наступне число дорівнює сумі двох попередніх: F = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...} F 0 = 0,
F ₁ = ₁ , F _n = F _{n - 1} + F _{n - 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 виводимо на консоль.

Виглядає крутіше, чи не так?
при перших елементах 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-ий елемент включно? Це не повинно спричинити у нас труднощів. Візьмемо рішення зі стримуванням, замінимо длякожного на пару інших методів:

для 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);

За допомогою .mapToInt(Integer::intValue) ми переводимо наш stream у числовий IntStream і за допомогою його методу .sum() отримуємо суму всіх елементів.

для випадку з 1,1 початковим елементом замість {0, 1} задаємо {1, 1}.

Отримання n-ого число у ряді Фібоначчі

Іноді просять вивести не ряд чисел, а саме n-е число у ряді Фібоначчі. Як правило, це тільки полегшує завдання, адже можна легко адаптувати попередні рішення для цього. Ну а як щодо вирішення задачі через рекурсію?

для 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. По суті, як і в попередніх рішеннях, нам потрібно задати перші два елементи.
реалізація для 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

Що повинен знати програміст на Java про числа Фібоначчі - 3

Рекурсивний метод може працювати довго, оскільки у процесі розрахунку функція багато разів викликатиметься від однієї й тієї аргументу. Наприклад, при обчисленні getFibonacciValue(7) функція зробить рекурсивні виклики до getFibonacciValue(5) і getFibonacciValue(6), обидва рекурсивні виклики будуть звертатися до getFibonacciValue(4)), що і призведе до багаторазових. На співбесіді можна показати цей спосіб як варіант рішення, але при цьому розповісти про ці його недоліки і натомість запропонувати інший спосіб. Також варто відзначити, що тип int в Java дозволяє зберігати від -2147483648 до 2147483647, тому вдасться обчислити тільки перші 46 чисел Фібоначчі: при спробі отримати наступне 47-е виникне переповнення, і ми отримаємо негативне число. Якщо ми будемо використовувати тип даних long замість int, то вдасться правильно обчислити перші 91 число Фібоначчі. Щоб обчислювати наступні числа Фібоначчі, необхідно скористатися класом BigInteger, який реалізує логіку зберігання та арифметичних операцій дійсно більших чисел.