FreeCodeCamp Intermediate JavaScript Algorithm Scripting Challenge

Внимание! Этот пост содержит решение задачи Наименьшее общее кратное из сценария промежуточного алгоритма Javascript.

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

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

Вышеупомянутый метод сначала получит текущий используемый делитель и этот делитель + 1. Затем, если следующий делитель простой, мы возвращаем его в основную функцию; в противном случае мы увеличиваем nextDivisor и проверяем снова.

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

А теперь о главной функции!

Разве это не красиво? Давайте разберемся с этим построчно, а потом я перейду к рекурсивности.

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

Затем я определяю метод alg, и знаете что? Это рекурсивно! (Подробнее об этом чуть позже).

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

А теперь функция алгоритма alg()!

Хорошо, сначала давайте определим наши аргументы. list – это наш массив чисел, полученный из переменных min и max. divisor — это простое число, которое мы используем для создания массива primeFactors, который также является третьим аргументом. делитель и список будут постоянно меняться, но primeFactors массив будет просто накапливать коэффициенты.

Теперь обратите внимание на наши три исходных аргумента:

  1. list = initRange — получено из переменных min и max.
  2. делитель = 2
  3. primeFactors = primeFactors, который начинается с пустого массива [ ].

Обратите особое внимание на то, что мы вызываем функцию alg() только один раз и сохраняем результат в переменной result — это забавная часть рекурсивных функций. Вызвав нашу рекурсивную функцию alg() всего один раз, она выполнит всю работу по нахождению наименьшего общего кратного. Никаких запутанных циклов или условных выражений; только одна фантастическая функция, чтобы сделать всю тяжелую работу!

Первая итерация

Первым шагом в нашем методе является проверка того, равен ли каждый элемент в нашем списке 1, если это так, мы знаем, что наш алгоритм завершен, и мы можем вернуть список primeFactors. Но в нашей первой итерации в списке не все единицы, поэтому мы переходим к следующей строке.

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

Затем мы проверяем, были ли изменены какие-либо значения, проверяя переменную isDivisible, которую мы присвоили истине во время функции list.map(). Если какая-либо переменная в списке делится на делитель, мы помещаем этот делитель в массив primeFactors и сбрасываем наш делитель на 2. Если вам интересно, почему мы делаем это не забудьте проверить алгоритм в Википедии.

И вот мы на последней строке нашего файла. . . который вызывает метод alg()? Но разве мы все еще не внутри первоговызова метода alg()?

Да, мы все еще находимся внутри стека вызовов первого вызова метода alg().

А теперь мы собираемся повторить весь этот процесс снова. НО на этот раз обратите внимание на переменные, которые мы передаем методу alg():

  1. list = nextRange — получено с помощью функции list.map()
  2. divisor = делитель — сбрасывается на 2
  3. primeFactors = primeFactors —теперь содержит коэффициент [2]

Потрясающий! Поэтому, несмотря на то, что я хотел бы сидеть здесь и работать с каждым вызовом стека, позвольте мне перейти к тому, где наш делитель обновляется дважды, прежде чем мы добавим еще один вызов в стек вызовов alg(). (Можете ли вы угадать, на каком методе number alg() мы находимся в нашем стеке вызовов?)

Последняя итерация

Обратите внимание на 3 начальных аргумента для этого вызова метода alg():

  1. list = [1, 1, 1, 1, 5] — Оооо, мы почти все 1!
  2. делитель = 2 —Изменяется ли эта вещь когда-либо? (Подсказка: да!)
  3. primeFactors = [2, 2, 3] — я люблю простые числа. Так просто.

"Эй, мам! Смотреть! 5 вызовов одного и того же метода в одном стеке вызовов!»

Какие? 5! Разве в нашем массиве primeFactors не всего 3 простых числа?

Да, у нас есть только 3 простых числа в массиве, но помните, что при первом вызове alg() мы использовали пустой массив, а затем добавили к массиву значение [2]. Затем мы получили следующий [2] при втором вызове alg(). Затем мы снова вызвали alg(), но на этот раз число 2 не сработало. Итак, мы увеличили значение на 1, снова вызвали метод alg(), и теперь у нас есть 4 вызова, 3 простых числа, и мы собираемся найти 4-е и последнее простое число. Сможете ли вы предположить, основываясь на приведенных выше аргументах, сколько вызовов потребуется, чтобы определить последнее простое число для массива primeFactors?

Делитель 2 не заработал (я же говорил, что уже опа), а что теперь?

Мы можем вызвать метод alg(). . .снова. На этот раз с делителем = 3.

Здорово! Значит, это должен быть последний вызов alg(), верно? (Извините, нет!)

Делитель 3 тоже не работал. Не верите мне? Ищите сами:

Ну что теперь? (эта статья повторяется так же, как и моя программа, упс)

  1. Увеличивайте делитель с помощью нашего метода getNextPrimeDivisor().
  2. Вызовите метод alg() еще раз
  3. Съешьте конфету за то количество раз, которое alg() находится в стеке вызовов.

Ура! Число [5] наконец сработало, и после добавления его к primeFactors делитель по умолчанию вернулся к 2, а в nextList установлены все единицы, думаю, пора с этим покончить.

Можем ли мы получить барабанную дробь для нашего последнего стека вызовов?

8. VIII. очо. שמונה. 八. 8

— вызовы метода alg().

Но что теперь? (Мне очень нравится повторение, которое я получил здесь).

При этом последнем вызове метода alg() первый блок if, наконец, будет оценен как true, и мы вернем только один массив:

primeFactors — [2, 2, 3, 5]

И как насчет оставшихся методов alg()?

Время очистки

После 8-го вызова alg() возвращается один массив, а не другой вызов метода alg(). По сути, мы вводим длинный список операторов возврата:

Самый внутренний вызов alg( ) возвращает массив primeFactors предыдущему вызову alg( ) и так далее и так далее, пока Массив primeFactors присваивается переменной result.

Но что теперь? (Я ломаю себя, мне так жаль, что я не могу с собой поделать).

Метод редукции используется для результирующего массива, умножая накопитель на каждое целое число, которое является наименьшим общим кратным для всех целых чисел от 1 до 5! 🎉

Я очень надеюсь, что вам понравилось мое объяснение того, как использовать рекурсивную функцию для решения задачи алгоритма наименьшего общего кратного от FreeCodeCamp🔥

Если у вас есть какие-либо вопросы, не стесняйтесь комментировать ниже и не забудьте нажать на маленький ❤️ внизу страницы! Большое спасибо, и я надеюсь увидеть вас на форумах FCC/gitter.

TL/DR: алгоритм наименьшего общего кратного, реализованный с использованием рекурсивных функций JavaScript.