В начале 2019 года на работе был введен «вызов разработчиков». Предпосылка заключалась в том, что либо раз в две недели, либо раз в неделю (в зависимости от сложности) разработчикам в нашем офисе будет выдаваться «вызов», и мы затем попытаемся решить их, с групповым собранием в конце недели, чтобы обсудить все наши решения.

Первая поставленная задача была определенно сложной — нам представили следующую информацию;

Ребенок бежит вверх по лестнице с n ступенями и может прыгать на 1, 2 или 3 ступеньки за раз. Реализуйте метод подсчета количества возможных способов, которыми ребенок может взбежать по лестнице.

Задача состоит в том, чтобы использовать рекурсию, чтобы вычислить количество возможных способов, которыми ребенок может подняться на n количество ступенек, перепрыгивая 1, 2 или 3 за раз.

Рекурсия — это математический термин, который определяется как;

Повторное применение рекурсивной процедуры или определения.

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

На самом деле рекурсия была чем-то, с чем я как разработчик раньше не сталкивался, и это было то же самое для большого количества людей в офисе.

Для начала нам нужно оценить проблему — давайте предположим для целей этого упражнения, что наша лестница имеет 4 ступени. Следовательно, n = 4.

Мы знаем, что ребенок может запрыгнуть на 1, 2 или 3 ступеньки одновременно, поэтому, имея лестницу из 4 ступенек, ребенок может подняться по любому из этих маршрутов;

1–1–1–1,
1–2–1,
1–1–2,
2–1–1,
2–2,
1–3,
3–1.

Чтобы решить проблему, нам нужно собрать имеющуюся у нас информацию;

  • При отрицательном количестве ступенек у ребенка нет путей их подъема, так как этот сценарий невозможен.
  • Если ступенек нет или только одна ступенька, то у ребенка есть только один способ подняться на них — 1.
  • Мы знаем 3 возможных способа, которыми ребенок может закончить шаги. С 1, 2 или 3 шагами.

Это преобразуется в функцию, которая должна выглядеть примерно так:

countRoutes(stairs) {
    if (stairs < 0) {
        return 0;
    }
    if (stairs === 0) {
        return 1;
    }
    return this.countRoutes(stairs - 1) + this.countRoutes(stairs - 2) + this.countRoutes(stairs - 3);
}

Таким образом, решение нашей проблемы заключается в суммировании количества различных способов, которыми ребенок может добраться до наших трех сценариев финиша, следовательно — this.countRoutes(лестницы - 1) + this.countRoutes(лестницы - 2) + this.countRoutes( лестницы - 3).

Конкретные «базовые случаи» из 0 или 1 шагов служат нашим предложением выхода, поэтому мы знаем, когда остановить рекурсию.

Таким образом, если n = 4, количество возможных способов, которыми ребенок может подняться по лестнице, должно быть равно 7.

Давайте разберем эту функцию и посмотрим на нее в виде рекурсии.

Как мы уже говорили ранее, мы знаем, что ребенок может подниматься по ступеням любым из трех способов, поэтому, если у нас есть лестница из 4 ступеней, нам нужно учитывать каждый из способов, которыми ребенок может подняться. Итак, мы разбиваем его еще на 3 цикла функции fn(4–1) (fn(3)), fn(4–2) (fn(2)), fn(4–3) (fn(1)) .

Для третьего экземпляра есть только 1 шаг, мы знаем, что у ребенка есть только один способ подняться на него, поэтому мы знаем, что функция вернет 1.

Для двух других случаев мы можем разбить их дальше. По сути, дерево будет продолжать расти до тех пор, пока каждая итерация функции не вернет 1. Затем мы суммируем все методы, и, как вы можете видеть на приведенной выше диаграмме, за 4 шага мы получаем 7 возможных маршрутов.

Бонусные баллы — мемоизация

Однако есть еще одна проблема, которую следует учитывать — стек вызовов. Наша функция рекурсии может обрабатывать 4 ступени, потому что функция будет выполняться только 13 раз (см. диаграмму выше). 13 итераций функции достаточно просто для браузера. Но если мы попытаемся найти маршруты для 100 ступенек или более, мы столкнемся с некоторыми проблемами в браузере.

Вот тут и приходит на помощь мемоизация — еще одна новая концепция, представленная в этой задаче.

Если вы снова посмотрите на приведенную выше диаграмму (игнорируйте экземпляры -1 и 0, потому что мы возвращаемся к ним раньше без цикла), вы увидите 4 цикла, где n = 1, 2 цикла, где n = 2, 1 цикл, где n = 3, и 1 цикл, где n = 4. Если мы введем мемоизацию, мы можем исправить нашу функцию, чтобы при n = 1 она зацикливалась только один раз и так далее.

Мемоизация определяется как;

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

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

countRoutes(stairs, memory = {}) {
    if (stairs < 0) {
        return 0;
    }
    if (stairs === 0) {
        return 1;
    }
    if (memory[stairs]) {
        return memory[stairs];
    }
    return memory[stairs] = this.countRoutes(stairs - 1, memory) + this.countRoutes(stairs - 2, memory) + this.countRoutes(stairs - 3, memory);
}

И вот оно. Лестница Фибоначчи — решение на JavaScript. Удивительно мало строк кода для довольно сложной задачи.