FreeCodeCamp Intermediate JavaScript Algorithm Scripting Challenge
Внимание! Этот пост содержит решение задачи Наименьшее общее кратное из сценария промежуточного алгоритма Javascript.
Я делюсь своим решением, потому что хочу показать, как я использовал рекурсивные функции для решения этой задачи. Мое решение основано на этом алгоритме, который я нашел в Википедии.
Прежде чем углубиться в мою основную функцию, я хочу определить две вспомогательные функции (одна из которых рекурсивна сама по себе!)
Вышеупомянутый метод сначала получит текущий используемый делитель и этот делитель + 1. Затем, если следующий делитель простой, мы возвращаем его в основную функцию; в противном случае мы увеличиваем nextDivisor и проверяем снова.
Слева — очень простая функция простого числа, которую я использую в различных числовых алгоритмах. Возможно, есть лучший способ (более эффективный), но пока он отлично работает для базовых алгоритмов.
А теперь о главной функции!
Разве это не красиво? Давайте разберемся с этим построчно, а потом я перейду к рекурсивности.
Первые несколько строк получают максимальные и минимальные числа, а затем создают массив со всеми целыми числами между максимальным и минимальным. Мы также определяем некоторые переменные, которые будем использовать позже.
Затем я определяю метод alg, и знаете что? Это рекурсивно! (Подробнее об этом чуть позже).
Последние несколько строк, которые создают список primeFactors, перемножают их вместе и возвращают результат (который является наименьшим общим кратным всех целых чисел в исходном массиве чисел). .
А теперь функция алгоритма alg()!
Хорошо, сначала давайте определим наши аргументы. list – это наш массив чисел, полученный из переменных min и max. divisor — это простое число, которое мы используем для создания массива primeFactors, который также является третьим аргументом. делитель и список будут постоянно меняться, но primeFactors массив будет просто накапливать коэффициенты.
Теперь обратите внимание на наши три исходных аргумента:
- list = initRange — получено из переменных min и max.
- делитель = 2
- primeFactors = primeFactors, который начинается с пустого массива [ ].
Обратите особое внимание на то, что мы вызываем функцию alg() только один раз и сохраняем результат в переменной result — это забавная часть рекурсивных функций. Вызвав нашу рекурсивную функцию alg() всего один раз, она выполнит всю работу по нахождению наименьшего общего кратного. Никаких запутанных циклов или условных выражений; только одна фантастическая функция, чтобы сделать всю тяжелую работу!
Первая итерация
Первым шагом в нашем методе является проверка того, равен ли каждый элемент в нашем списке 1, если это так, мы знаем, что наш алгоритм завершен, и мы можем вернуть список primeFactors. Но в нашей первой итерации в списке не все единицы, поэтому мы переходим к следующей строке.
После инициализации логической переменной isDivisible переменная nextList пытается разделить каждое значение в списке на делитель. Если оно делится без остатка, мы возвращаем частное переменной и делителя в nextList, в противном случае мы возвращаем то же значение из спискав следующий список.
Затем мы проверяем, были ли изменены какие-либо значения, проверяя переменную isDivisible, которую мы присвоили истине во время функции list.map(). Если какая-либо переменная в списке делится на делитель, мы помещаем этот делитель в массив primeFactors и сбрасываем наш делитель на 2. Если вам интересно, почему мы делаем это не забудьте проверить алгоритм в Википедии.
И вот мы на последней строке нашего файла. . . который вызывает метод alg()? Но разве мы все еще не внутри первоговызова метода alg()?
Да, мы все еще находимся внутри стека вызовов первого вызова метода alg().
А теперь мы собираемся повторить весь этот процесс снова. НО на этот раз обратите внимание на переменные, которые мы передаем методу alg():
- list = nextRange — получено с помощью функции list.map()
- divisor = делитель — сбрасывается на 2
- primeFactors = primeFactors —теперь содержит коэффициент [2]
Потрясающий! Поэтому, несмотря на то, что я хотел бы сидеть здесь и работать с каждым вызовом стека, позвольте мне перейти к тому, где наш делитель обновляется дважды, прежде чем мы добавим еще один вызов в стек вызовов alg(). (Можете ли вы угадать, на каком методе number alg() мы находимся в нашем стеке вызовов?)
Последняя итерация
Обратите внимание на 3 начальных аргумента для этого вызова метода alg():
- list = [1, 1, 1, 1, 5] — Оооо, мы почти все 1!
- делитель = 2 —Изменяется ли эта вещь когда-либо? (Подсказка: да!)
- 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 тоже не работал. Не верите мне? Ищите сами:
Ну что теперь? (эта статья повторяется так же, как и моя программа, упс)
- Увеличивайте делитель с помощью нашего метода getNextPrimeDivisor().
- Вызовите метод alg() еще раз
- Съешьте конфету за то количество раз, которое 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.