Вычисление чисел Фибоначчи

Числа Фибоначчи — это числа такой последовательности, в которой первые два элемента — 0 и 1, а каждый последующий элемент равен сумме двух предшествующих. Выглядит это так:

			0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …
		

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

Формула записывается следующим образом:

Вычисление ряда Фибоначчи — стандартная задача, которую задают на собеседованиях, чтобы проверить кандидата на понимание алгоритмов. Не так популярна, как сортировка, но всё же.

Давайте вычислим ряд и его отдельные элементы, использовав для этого язык Java.

1. Цикл
2. Рекурсия
3. Stream
4. Тест

Вычислить ряд Фибоначчи циклом

Предположим, что нам нужно вывести на экран первые десять чисел последовательности Фибоначчи. Мы помним, что:

• первый элемент ряда — 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);
		

Математический тест

Любите математику? Попробуйте решить наш математический тест: