Сегодня я расскажу о рядах Фибоначчи и о том, как мы можем использовать несколько методов для решения проблемы. Я буду подробно рассказывать о каждом решении, разбивая каждый шаг. Если вы в настоящее время ищете алгоритмы JS для практики, взгляните на два моих последних сообщения в блоге, чтобы узнать о нескольких более простых алгоритмах.
JS: обращение строк, палиндромы и анаграммы
JS: Целочисленное обращение и FizzBuzz!
Последовательность Фибоначчи
Прежде чем мы займемся этим, давайте рассмотрим, что такое последовательность Фибоначчи. Вот ряд цифр.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…
Числа, которые вы видите выше, являются первыми 13 числами в последовательности. Цифры можно продолжать и продолжать, но для простоты мы оставим 13 цифр.
Если вы еще не поняли, следующее число в последовательности можно найти, добавив два числа перед ним. Следующее число в последовательности будет найдено путем сложения 89 + 144. Имея это в виду, следующее число будет 233.
Если вы посмотрите на 7-е число в последовательности, 8, два числа перед ним — 5 и 3. 5 +3 = 8. Это так просто!
Алгоритм
Распечатайте n-й элемент ряда Фибоначчи. Если мы передадим 6 в качестве аргумента нашей функции fib, мы ожидаем, что наша функция вернет 5. Если это не имеет смысла, еще раз взгляните на приведенную выше последовательность. Шестой элемент в последовательности равен 5.
Решение 1. Итеративное решение
Итеративное решение является более простым из двух (на мой взгляд) и может быть решено с помощью afor всего за пару шагов. Если мы хотим вернуть n-й элемент ряда Фибоначчи, нам нужно сначала создать массив, в котором будет храниться наша последовательность до n-го элемента. Мы также заполним его первыми двумя элементами последовательности, чтобы немного начать последовательность. Приступаем к кодированию.
function fib(n) {
const seq = [0, 1]
}
Следующий шаг будет включать в себя создание цикла for. Поскольку у нас уже есть первые две записи последовательности в нашем массиве seq, мы можем начать наш цикл for со 2-й позиции вот так.
function fib(n) {
const seq = [0, 1]
for(let i = 2; i <= n; i++) {
}
}
Опять же, мы начинаем наш цикл for со 2-й позиции массива, потому что у нас уже есть первые две записи в массиве seq.
Теперь все, что нам нужно сделать, это выяснить, как мы можем сложить две предыдущие записи, чтобы получить следующее число в последовательности. Мы знаем, что две предыдущие добавленные записи будут равны следующей записи, поэтому давайте создадим две переменные, a и b, которые будут равны каждой из двух предыдущих записей.
function fib(n) {
const seq = [0, 1]
for (let i = 2; i <= n; i++) {
const a = result[i - 1]
const b = result[i - 2]
}
}
Для первого прохода цикла for мы использовали result[i-1] для захвата 1 в массиве seq и result[i-2] для захвата 0. Для каждого последующего прохода цикла a и b будут равны двум предыдущим записям массива. seq .
Теперь все, что осталось сделать в цикле, — это сложить эти две переменные вместе и поместить их в массив seq.
function fib(n) {
const seq = [0, 1]
for (let i = 2; i <= n; i++) {
const a = result[i - 1]
const b = result[i - 2]
result.push(a + b)
}
}
Наш цикл завершен и прекратит работу, как только будет достигнута n-я запись в последовательности Фибоначчи. Теперь, когда у нас есть nth в качестве последнего числа в массиве seq, все, что нам нужно сделать, это вернуть число.
function fib(n) {
const seq = [0, 1]
for (let i = 2; i <= n; i++) {
const a = result[i - 1]
const b = result[i - 2]
result.push(a + b)
}
return seq[n]
}
Поскольку все, что мы здесь сделали, это вернули последнее число в нашем массиве seq, мы могли бы также записать решение как return seq[seq.length — 1]
И это все для нашего итеративного решения! Это решение очень легко понять и довольно легко запомнить. Перейдем к следующему решению.
Решение № 2: рекурсивное решение
В некоторых случаях вы можете столкнуться с интервьюером, который попросит вас решить эту проблему с помощью рекурсивного решения. Хотя решение может быть трудно найти самостоятельно, как только вы сделаете это один раз, вы освоитесь.
Давайте перейдем непосредственно к решению и поговорим о том, как и почему оно работает. Этот формат немного отличается от того, как я обычно подхожу к решению алгоритмов, но вы поймете, почему я выбрал именно этот подход, а не рассматривал решение шаг за шагом.
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2);
}
Первый условный оператор существует для одной цели. Если аргумент функции fib равен 0 или 1, эти числа будут возвращены сразу. Если вы еще раз взглянете на последовательность Фибоначчи, то увидите, что первые два числа — это 0 и 1, а остальные не нуждаются в объяснении. Если аргумент n равен 2 или больше, мы входим в рекурсию. Чтобы лучше понять, что происходит, давайте взглянем на диаграмму ниже.
Если мы вызовем fib(5), нашим оператором возврата будет return fib(5 — 1) + fib(5 — 2), что переводится как fib(4) + fib(3). Глядя на график выше, fib(4) будет разветвляться, чтобы стать fib(3) + fib(2), и это будет продолжаться до тех пор, пока не будет достигнуто дно и не будет сложено окончательное значение. Если это еще не имеет смысла, уделите несколько минут изучению диаграммы.
Как только мы достигнем нижней части диаграммы, у нас будут экземпляры, в которых вызывались fib(1) и fib(0), и, если вы помните, мы автоматически возвращаем 1 для fib(1) и 0 для fib(0). Если мы сложим все синие квадраты, мы получим 5. Снова взглянув на последовательность Фибоначчи, 5-е число действительно равно 5.
Опять же, сначала это может не иметь большого смысла, но я призываю вас изучить график, и если рекурсия пока не имеет смысла, прочитайте эту полезную статью с сайта Javascript.info .
Вывод
Если вам удалось дойти до конца, не расстраивайтесь, если рекурсивное решение не имеет смысла. Это одно из тех решений, которые в конечном итоге зависят от того, видели ли вы его раньше или нет. Я не мог бы сам придумать решение, но я надеюсь, что этот пост поможет вам понять, как мы можем справиться с рядом Фибоначчи.
Спасибо за чтение!
