25 марта 2024
Тэги: Java, Kotlin, алгоритмы, головоломки.
На собеседованиях по алгоритмам любят давать такую задачку, как нахождение чисел из последовательности Фибоначчи. Эта числовая последовательность названа в честь Леонардо Пизанского – известного математика Средневековья.
Сама последовательность довольно проста. Она состоит из целых положительных чисел, где каждый следующий элемент равен сумме двух предыдущих. Например, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2.
Последовательность начинается с 0 и 1:
Иногда в этой последовательности принято пропускать 0 и начинать её с двух единиц, однако официально она начинается именно с 0.
Эта последовательность описывает правило «золотого сечения», когда мы делим нечто целое на две неравные части, где целая часть так же пропорциональна бОльшей, как и бОльшая к меньшей.
Считается, что это правило также часто встречается в природе. Например, в спиралях раковины моллюска или в спирали Млечного Пути.
Давайте напишем метод, который будет возвращать число Фибоначчи по его индексу в этой последовательности. Числа в последовательности растут очень быстро, поэтому значения будем хранить в типе long.
Алгоритм тут довольно простой: заводим первые два числа последовательности как n0 и n1. Затем в цикле, начиная с индекса 2, вычисляем новое значение как их сумму. Это новое значение становится n1, а то, что было n1 – становится n0. По достижении необходимого индекса выходим из цикла и возвращаем результат.
Обратите внимание на обработку пограничных случаев. Если индекс равен 0 – сразу возвращаем первый элемент последовательности, т.е. 0. Отрицательный индекс недопустим – кидаем стандартное исключение IndexOutOfBoundsException.
Также кидаем исключение, если индекс больше чем 92 – тут происходит переполнение типа long. При переполнении Java ошибку не кидает, но число при этом становится некорректным (например, отрицательным). Это связано со сдвигом и потерей части разрядов в двоичном представлении числа.
Теперь можем вызвать наш метод и посмотреть число Фибоначчи с индексом, например, 42.
Данная реализация работает довольно шустро и её единственный недостаток – это поддержка только первых 92 членов последовательности. Но что, если мы хотим вычислить элемент с индексом 100, 1000 или даже 1 000 000 ?
На помощь нам придёт класс BigInteger. Он довольно громоздкий с точки зрения скорости вычисления и с точки зрения написания кода, но при этом поддерживает сколь угодно большие числа. Поэтому заменим long на BigInteger. Желаемый номер элемента также будем передавать в метод как BigInteger.
Тут мы уже не можем использовать числа типа 0 и 1. Вместо этого пишем константы BigInteger.ZERO и BigInteger.ONE. Сравнение чисел также усложняется – используем метод compareTo(). Для сложения вместо плюса пишем метод add(). Поскольку BigInteger поддерживает очень большие числа, то проверку на максимальный индекс убираем.
Теперь мы можем найти элемент с порядковым номером 1 000 000. Обратите внимание, что BigInteger можно инициализировать через текстовое представление числа.
Найденный результат представляет собой столь большое число, что оно не помещается на экран консоли! Даже на 20 экранов... Однако и это число на моём ноуте было вычислено всего-то за 15 секунд.
Согласитесь, вряд ли может потребоваться вычислять столь большие значения, поэтому можно считать, что даже с BigInteger алгоритм всё равно работает шустро.
Алгоритм поиска чисел Фибоначчи также можно реализовать с помощью рекурсии, т.е. когда метод будет вызывать сам себя.
В любом методе с рекурсией обязательно должны быть условия остановки, проверяющие пограничные значения. Здесь мы проверяем индекс, переданный в параметре. Если он 0 или 1 – тут же возвращаем число. Иначе возвращаем результат, как вызов этого же метода с параметрами n – 1 и n – 2 с последующим их суммированием.
Как видите, рекурсивный алгоритм довольно компактен. Но у него есть два недостатка.
Во-первых, для рекурсии активно используется стек вызова методов. Вы можете довольно легко исчерпать его и получить StackOverflowError, запросив какой-нибудь большой индекс.
Во-вторых, и это более критично, время вычисления каждого следующего числа в два раза больше предыдущего. Для малых индексов это не так заметно, но где-то в районе 45-го числа последовательности задержка уже даёт о себе знать. Дело в том, что мы вычисляем все предыдущие значения на каждом уровне рекурсии, несмотря на то, что уже вычисляли их ранее.
Эту проблему можно решить кешированием уже вычисленных значений. Доработаем предыдущий метод, добавив туда второй параметр memo, представляющий собой массив целых чисел, допускающих null-значения, т.е. ссылочный тип Long.
При вызове метода передаём пустой массив с количеством ячеек, равным количеству чисел в последовательности + 1. Вместо массива можно также использовать обычный List.
Теперь мы каждый раз перед вычислением проверяем, нет ли уже такого значения в кеше. Если значение уже вычислено, то под соответствующим индексом в memo будет число, а не null. Это даёт значительное ускорение работы метода.
Но даже учитывая эту оптимизацию, на практике я бы не рекомендовал использовать рекурсивную версию.
В дополнение приведу вариант без рекурсии на Kotlin, чтобы продемонстрировать лаконичность его синтаксиса.
Здесь всё ровно то же самое, только мы заменили цикл for на while. А также вернули обратно привычные нам операторы сравнения и инкремента. Теперь вызовем этот метод:
Время вычисления не увеличилось по сравнению с Java-версией, поскольку компилятор Kotlin вызывает те же самые compareTo() и add(), генерируя почти такой же байт-код.
Мы рассмотрели несколько реализаций нахождения числа Фибоначчи по его индексу.
P.S. Спасибо Диме Вдовину, который является автором telegram-канала Yet another backend digest, за комментарий о вычислительной сложности рекурсивного алгоритма.
Kotlin, Java, Spring, Spring Boot, Spring Data, SQL, PostgreSQL, Oracle, Linux, Hibernate, Collections, Stream API, многопоточность, файлы, Nginx, Apache, maven, gradle, JUnit, YouTube, новости, руководство, ООП, алгоритмы, головоломки, rest, GraphQL, Excel, XML, json, yaml.
25.10.2022 18:43 Сергей
Добавьте пример на Kotlin с использованием рекурскии.
26.10.2022 23:44 devmark
Сергей, я добавил вариант реализации алгоритма с рекурсией и указал на его нюансы.
22.02.2023 20:47 Артём
В Intellij IDEA всё получилось, но в другом компиляторе такая ошибка:
Can't compile file:
program.kt:12:24: error: cannot access 'TWO': it is private in 'BigInteger'
var i = BigInteger.TWO
^
Unable to find classes\programkt.class
16.02.2024 10:41 Дима
Рекурсивный вариант нахождения числа фибаначи в такой реализации является не очень хорошим в плане "сложности алгоритма". Тут сложность будет расти экспоненциально почти.
Почему так происходит? Допустим я считаю fib(6). Рекурсивно я пойду считать fib(5) и fib(4). Но проблема в том, что в каждой "ветке" (и их дочерних) я буду каждый раз считать одни и те же значения.
Как вариант, можно улучшить алгоритм "запоминая" уже высчитанные значения. И прежде чем начать их считать, проверять в "кеше".
Есть еще формула Бине, для подсчета чила фибоначи. Но это уже не про алгоритмы, а про математику: https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8#%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%91%D0%B8%D0%BD%D0%B5
24.03.2024 16:17 devmark
Дима, спасибо за коммент! Я немного переработал статью в части рекурсивного алгоритма и добавил вариант с кешированием.
04.10.2024 02:37 Владимир
мб добавить вариант рекурсии с оптимизацией попроще?
class FibonacciSearcher {
int get(int n) {
if (n <= 1)
return n;
return get(n, 0, 1);
}
private int get(int n, int left, int right) {
if (n < 2)
return right;
int sum = left + right;
return get(n - 1, right, sum);
}
}
06.10.2024 01:22 devmark
Владимир, спасибо, обязательно добавлю ваш вариант в статью!
И там лучше вместо int сразу использовать long, чтобы можно было до 92 индекса дойти.