Числа Фибоначчи — это числа такой последовательности, в которой первые два элемента — 0 и 1, а каждый последующий элемент равен сумме двух предшествующих. Выглядит это так:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …Формула записывается следующим образом:
Вычисление ряда Фибоначчи — стандартная задача, которую задают на собеседованиях, чтобы проверить кандидата на понимание алгоритмов. Не так популярна, как сортировка, но всё же.
Давайте вычислим ряд и его отдельные элементы, использовав для этого язык Java.
Вычислить ряд Фибоначчи циклом
Предположим, что нам нужно вывести на экран первые десять чисел последовательности Фибоначчи. Мы помним, что:
- первый элемент ряда — 0, второй — 1;
- каждый последующий — сумма двух предыдущих.
Тогда наша последовательность будет иметь такой вид:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34Но нам нужно вывести результат с использованием программы. Держите код с объяснениями в комментариях:
public class Main{
public static void main(String[] args) {
//Объявляем переменные при известных первых двух:
int num0 = 0;
int num1 = 1;
int num2;
//Первые две переменные выводим вне цикла:
System.out.print(num0 + " " + num1 + " ");
for(int i = 3; i <= 10; i++){
num2 = num0 + num1;
//Каждый следующий элемент выводим в цикле:
System.out.print(num2 + " ");
//Предыдущим двум переменным присваиваем новые значения:
num0 = num1;
num1 = num2;
}
}
}Выполнение завершится на десятом элементе. Количество элементов при этом можно менять, изменив значение в условиях цикла.
Найти число Фибоначчи через рекурсию
Рекурсивная функция — это такая функция, которая вызывает саму себя. Она также неплохо отрабатывает в алгоритмических задачах вроде чисел Фибоначчи, но ей требуется больше времени.
Почему так происходит? Всё дело в том, что рекурсивная функция приводит к многоразовому вызову одних и тех же операций. Именно из-за этого её не рекомендуется использовать, но если уж на собеседовании прозвучит такая задача, вы будете готовы.
Рассмотрим пример, в котором нам нужно получить n-ое число в ряде Фибоначчи:
public int fibonacciValue(num) {
if (num <= 1) {
return 0;
} else if (num == 2) {
return 1;
} else {
return fibonacciValue(num - 1) + fibonacciValue(num - 2);
}
}Если в качестве num задать большое значение, программа зависнет.
Тип int в Java может хранить значения до 2147483647, так что вычислить получится лишь первые 46 чисел Фибоначчи. Тип long хранит до 9223372036854775807, а это 91 число Фибоначчи. Класс BigInteger призван работать с действительно большими значениями, вот только само выполнение программы это никак не ускорит.
Использовать для вычисления Stream
Stream в Java — это компонент для самостоятельной внутренней итерации своих же элементов. Подробнее о нём вы можете почитать в нашей статье о Java Stream API.
И, разумеется, Stream подходит для вычисления элементов последовательности Фибоначчи:
Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
//Задаём лимит значений:
.limit(num)
//Отбираем по первому элементу каждого массива:
.map(y -> y[0])
//Выводим в консоль:
.forEach(x -> System.out.println(x));В данном примере метод iterate() будет возвращать упорядоченный поток, ограниченный лимитом в num значений и созданный с применением функции к начальному массиву arr. В консоль будет выведено следующее:
{0,1}
{1,1}
{1, 2}
{2, 3}
{3, 5}
{5, 8}
{8, 13}
{13, 21}
…А так мы получим сумму чисел последовательности по элемент num включительно:
int fibonacciValuesSum = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
.limit(num)
.map(y -> y[0])
.mapToInt(Integer::intValue)
.sum();
System.out.println(fibonacciValuesSum);Математический тест
Любите математику? Попробуйте решить наш математический тест:
