Нахождение чисел фибоначчи java

Числа Фибоначчи

Числа Фибоначчи — элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …, в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел:

В следующем примере реализованы два варианта вычисления чисел Фибоначчи: с помощью рекурсии (метод recursive) и цикла for (метод calculateWithFor):

public class Fibonacci < public static void main(String[] args) < int n = 25; LocalTime localTime1 = LocalTime.now(); System.out.print("Рекурсия " + recursive(n)); LocalTime localTime2 = LocalTime.now(); Duration duration1 = Duration.between(localTime1, localTime2); System.out.println(", время выполнения - " + duration1); LocalTime localTime3 = LocalTime.now(); System.out.print("Цикл for " + calculateWithFor(n)); LocalTime localTime4 = LocalTime.now(); Duration duration2 = Duration.between(localTime3, localTime4); System.out.println(", время выполнения - " + duration2); >/** * Сложность О(n) * * @param n * @return */ private static long calculateWithFor(int n) < long first = 0; long second = 1; long result = n; for (int i = 1; i < n; i++) < result = first + second; first = second; second = result; >return result; > /** * Сложность О(2^n) * * @param n * @return */ private static long recursive(int n) < if (n return recursive(n - 2) + recursive(n - 1); > >

Если запустить данную программу и посмотреть на время выполнения обоих алгоритмов, то можно увидеть, что рекурсивный вариант работает дольше.

Попробуйте изменить значение переменной n на 250, и программа зависнет. Проблема состоит в том, что скорость вычисления рекурсивного алгоритма крайне низкая.

Источник

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

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

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

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

 int[] arr = new int[n]; arr[0] = 0; arr[1] = 1; for (int i = 2; i

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

 int[] arr = new int[n]; arr[0] = 1; arr[1] = 1; for (int i = 2; i

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

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

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

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

Но их будет бесконечное количество, и поэтому с помощью .limit(n) мы урезаем количество элементов до первых n (в нашем случае до 10). Однако нам не нужен поток массивов, поэтому с помощью .map(y -> y[0]) мы отбираем по первому элементу каждого массива и получаем поток с необходимыми нам числами и с помощью forEach выводим на консоль. Выглядит покруче, не так ли? при первых элементах 1,1 этот код также будет почти таким же:

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

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

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

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

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

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

Источник

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

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

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

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

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

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

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

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

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

Тогда наша последовательность будет иметь такой вид:

Но нам нужно вывести результат с использованием программы. Держите код с объяснениями в комментариях:

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

Найти число Фибоначчи через рекурсию

Рекурсивная функция — это такая функция, которая вызывает саму себя. Она также неплохо отрабатывает в алгоритмических задачах вроде чисел Фибоначчи, но ей требуется больше времени.

Почему так происходит? Всё дело в том, что рекурсивная функция приводит к многоразовому вызову одних и тех же операций. Именно из-за этого её не рекомендуется использовать, но если уж на собеседовании прозвучит такая задача, вы будете готовы.

Рассмотрим пример, в котором нам нужно получить n-ое число в ряде Фибоначчи:

public int fibonacciValue(num) < if (num 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[], arr -> new int[]) //Задаём лимит значений: .limit(num) //Отбираем по первому элементу каждого массива: .map(y -> y[0]) //Выводим в консоль: .forEach(x -> System.out.println(x));

В данном примере метод iterate() будет возвращать упорядоченный поток, ограниченный лимитом в num значений и созданный с применением функции к начальному массиву arr . В консоль будет выведено следующее:

А так мы получим сумму чисел последовательности по элемент num включительно:

int fibonacciValuesSum = Stream.iterate(new int[], arr -> new int[]) .limit(num) .map(y -> y[0]) .mapToInt(Integer::intValue) .sum(); System.out.println(fibonacciValuesSum);

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

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

Источник

Фибоначчи на Java примеры

В ряду Фибоначчи на Java следующее число является суммой двух предыдущих чисел. Первые два числа ряда Фибоначчи – 0 и 1.

Числа Фибоначчи в значительной степени используются в вычислительном исследовании времени выполнения алгоритма для определения наибольшего общего делителя двух целых чисел. В арифметике массив Wythoff представляет собой бесконечную матрицу чисел, являющуюся результатом последовательности Фибоначчи.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, .

Java-код с использованием For

//Using For Loop public class FibonacciExample < public static void main(String[] args) < // Set it to the number of elements you want in the Fibonacci Series int maxNumber = 10; int previousNumber = 0; int nextNumber = 1; System.out.print("Fibonacci Series of "+maxNumber+" numbers:"); for (int i = 1; i > >

Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

• previousNumber инициализируется до 0, а nextNumber инициализируется до 1
• Для цикла перебирает maxNumber
  • Показать предыдущий номер
  • Вычисляет сумму предыдущего и следующего номеров
  • Обновляет новые значения previousNumber и nextNumber

  С использованием while

  Вы также можете сгенерировать ряд Фибоначчи, используя цикл While в Java.

  //Using While Loop public class FibonacciWhileExample < public static void main(String[] args) < int maxNumber = 10, previousNumber = 0, nextNumber = 1; System.out.print("Fibonacci Series of "+maxNumber+" numbers:"); int i=1; while(i > >

  Fibonacci Series of 10 numbers:0 1 1 2 3 5 8 13 21 34

  Единственное отличие в логике программы – использование цикла WHILE для вывода чисел Фибоначчи.

  Ряд Фибоначчи, основанный на пользовательском вводе

  //fibonacci series based on the user input import java.util.Scanner; public class FibonacciExample < public static void main(String[] args) < int maxNumber = 0; int previousNumber = 0; int nextNumber = 1; System.out.println("How many numbers you want in Fibonacci:"); Scanner scanner = new Scanner(System.in); maxNumber = scanner.nextInt(); System.out.print("Fibonacci Series of "+maxNumber+" numbers:"); for (int i = 1; i > >

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

  Через рекурсию

  //Using Recursion public class FibonacciCalc < public static int fibonacciRecursion(int n)< if(n == 0)< return 0; >if(n == 1 || n == 2) < return 1; >return fibonacciRecursion(n-2) + fibonacciRecursion(n-1); > public static void main(String args[]) < int maxNumber = 10; System.out.print("Fibonacci Series of "+maxNumber+" numbers: "); for(int i = 0; i < maxNumber; i++)< System.out.print(fibonacciRecursion(i) +" "); >> >

  Fibonacci Series of 10 numbers: 0 1 1 2 3 5 8 13 21 34

  Рекурсивная функция – это функция, которая может вызывать себя сама.

  fibonacciRecursion (4) It will recursively call fibonacciRecursion function for values 2 and 3 fibonacciRecursion (2) \\ call for value 0 and 1 fibonacciRecursion (0) = 0 fibonacciRecursion (1) = 1 fibonacciRecursion (3) \\ It will call for 1 and 2 fibonacciRecursion (1) = 1 fibonacciRecursion (2) \\ It will call for 0 and 1 fibonacciRecursion (0) = 0 fibonacciRecursion (1) = 1

  Теперь результат добавлен 0 + 1 + 1 + 0 + 1 = 3.

  Источник