Как сделать факториал в javascript
Обновлено: 05.07.2024
Вместо использования циклов Array объект JavaScript является достаточно мощным средством для создания последовательностей . А как насчет более сложных серий, а не просто списка последовательных цифр или букв? К счастью, у нас еще есть функции другого массива , например filter , map , every , и reduce в нашем распоряжении. Они могут быть использованы для генерации списка простых чисел , вычисления факториала и получения ряда Фибоначчи .
Простые числа
Вышеприведенная реализация теста простоты , вероятно, не самая оптимальная, достаточно проиллюстрировать концепцию.
Следующей задачей этой функции является печать всех простых чисел от 0 до N :
Мы уже узнали, что некоторые основанные на циклах итерации могут быть превращены в однострочники Array. Можем ли мы применить ту же технику к вышеуказанной проблеме?
Давайте решать isPrime() сначала. Подходящим решением здесь является использование Array.prototype.every . В разделе 15.4.4.16 спецификация ECMAScript 5.1 гласит:
каждый вызывает callbackfn один раз для каждого элемента, присутствующего в массиве, в порядке возрастания, пока не найдет элемент, где callbackfn вернет false. Если такой элемент найден, каждый сразу возвращает false. В противном случае, если callbackfn вернул true для всех элементов, каждый вернет true.
Другими словами, мы можем использовать every для проверки каждого потенциального делителя и посмотреть, является ли один из них делителем для кандидата. Если да, очевидно, что кандидат не простое число, и нам просто нужно немедленно выручить. Если после исчерпывающего поиска есть подходящий делитель, это означает, что мы находим наше простое число.
Удивительно, но код короче приведенного выше объяснения. Кроме того, ~~ вместо какой- Math.floor то дополнительной загадки используется трюк .
Другая функция primeList() довольно проста для рефакторинга. Вспомните еще раз подход с использованием комбинации конструктора Array apply , и map мы в итоге получим следующее окончательное решение. Обратите внимание, что тест на простоту теперь встроен с помощью Array.prototype.filter .
(Красавка) сочетание map , filter и every достаточно очевидно , чтобы избежать петли!
Если вы заботитесь о готовящемся выпуске ECMAScript 6 , использование функции со стрелкой и понимания массива позволяет записать вышеуказанную конструкцию в виде:
function primeList(N) < return [for (i of Array.apply(0, Array(N)).map((x, y) =>y)) if ((i > 1) && Array.apply(0, Array(1 + ~~Math.sqrt(i))). every((x, y) => (y Факториал
Вычислительный факториал — еще одна интригующая математическая деятельность. Фактически, из-за своей природы, это становится обычным упражнением для введения в рекурсивное программирование. А сейчас давайте сосредоточимся на нерекурсивной реализации, что-то вроде:
Здесь, если мы хотим избежать императивного стиля использования цикла, стратегия будет другой. Поскольку вычисление факториала n зависит от всех предыдущих значений, мы не можем просто использовать map или даже every как в предыдущем примере. Для этого нам нужна помощь Array.prototype.reduce . В разделе 15.4.4.21 спецификации есть, что сказать об этой функции высшего порядка:
callbackfn вызывается с четырьмя аргументами: previousValue (или значение из предыдущего вызова callbackfn), currentValue (значение текущего элемента), currentIndex и просматриваемый объект.
Вероятно, это легче понять reduce из следующей простой иллюстрации:
Из-за x + y вышеприведенного кода по существу выдает сумму каждого числа в массиве. Здесь x соответствует предыдущему значению, а y — текущему значению (которое будет изменяться от 1 до 5). В этом контексте представьте, что х действует как аккумулятор. Обратите внимание также, что reduce может принимать необязательный второй аргумент, который станет начальным значением. В приведенном выше примере 100 это сместит вычисленную сумму.
Мы также можем сделать что-то вроде следующего. Не только элемент массива (текущее значение, y ) используется, обратный вызов также использует индекс элемента, переданный в качестве третьего аргумента z .
Если вы сделаете это так далеко, вы, вероятно, уже придумали решение проблемы факториала. Вот примерная реализация. Обратите внимание на возвращаемое значение обратного вызова, оно не является простым, потому что индекс элемента z начинается с 0, а не с 1.
Как обычно, вот версия ECMAScript 6 с функцией стрелки:
Наконец, для сравнения смотрите также этот твит от Ангуса Кролла ( @angustweets ). Для другого варианта ознакомьтесь с версией Джеда Шмидта ( @jedschmidt ), где сама функция также используется в качестве обратного вызова для reduce .
Серия Фибоначчи
Этот короткий трактат неполон без ряда Фибоначчи , часто связанного с ростом популяции кроликов. Идея чисел Фибоначчи относительно проста, но с ней могут быть связаны десятки головоломных задач программирования.
Если попросить показать первые n чисел Фибоначчи, ее реализация может выглядеть так:
Если мы хотим переключить реализацию для использования Array объекта JavaScript , ситуация с двумя предыдущими значениями становится реальной проблемой. Опираясь на reduce будет сложно , так как его обратного вызова получает только одно предыдущее значение. Кроме того, мы можем взглянуть на последние два значения из последнего аргумента обратного вызова, через который перемещается массив, потому что этот массив неизменен (в конце концов, это функциональное программирование).
К счастью, мир программирования полон волшебных трюков и секретных переходов. Среди других возможностей, одна хитрость, которую мы можем продолжать использовать, reduce это использовать (пустой) массив в качестве начального значения. Фактически, этот массив будет содержать окончательный ряд Фибоначчи. Так как мы продолжаем хранить больше чисел в этом массиве, просмотр двух предыдущих чисел становится очень простым. На самом деле, полный код для этого совсем не скучен.
Обновление: оригинальная версия содержит, map но Джед Шмидт ( @jedschmidt ) любезно указал, что в этом нет необходимости, потому что мы просто хотим использовать индекс элемента, а нам не важно само значение элемента.
Переписав выше функции для использования ECMAScript 6 «s массив понимания и функции стрелка остается в качестве упражнения для читателя.
Наконец, если вы все еще подвергаете сомнению мощь объекта Array JavaScript, подумайте еще раз. Среди смертных вторые мысли — самые мудрые.
Можно долго спорить о том, стоит ли использовать рекурсию или не стоит. Иногда ее применение просто необходимо, а иногда совсем не оправдано. Все программисты знают, что с одной стороны рекурсия имеет свои преимущества, но и недостатков у нее тоже куча. Сейчас не об этом. Рассмотрим как можно применять рекурсию в JavaScript. И, безусловно, в качестве тестового примера будем юзать вычисление факториала. Если кто еще до сих пор не в курсе, то вот вам формула для вычисления факториала числа: \[n!=1\times2\times3\times. \times n\] К примеру: \[6!=1\times2\times3\times4\times5\times6=720\] Факториал числа 6 для этого примера можно вычислить без применения рекурсии. Например вот так: А теперь приведем пример рекурсивного решения задачи вычисления факториала: Но, поскольку с рекурсией надо быть осторожным, чтобы не было сбоев и зацикливаний можно предложить усовершенствованный вариант кода: Для тех кто еще только начинает изучать JavaScript поясним, что результат работы скрипта для данного примера можно посмотреть в консоли JavaScript. Слева на картинке пример меню в Chrome для вызова консоли. Или можно нажать соответствующее сочетание клавиш. И в завершение, хотелось бы напомнить, что при реализации рекурсивных программ следует предусматривать надежный выход из рекурсии, чтобы не допустить зацикливания. Часто одного условия не достаточно, особенно в тех случаях, когда результат, получаемый от работы скрипта заранее не известен или условие выхода из рекурсии может оказаться недостижимым.
Программирование на C++ с Нуля до Гуру
Данный курс научит Вас программировать на языке C++, который, несмотря на свой почтенный возраст, необычайно сильно востребован. Курс состоит из 6 разделов, посмотрев которые и выполнив все упражнения, Вы с нуля освоите этот язык и сможете создавать самые разные проекты любой сложности на C++.
Для закрепления материала из уроков к ним идёт множество упражнений.
Дополнительно к курсу идёт вспомогательная система, которая не даст Вам забросить начатое на полпути.
Также вместе с курсов Вы получаете Бонус "Программирование на C++ в Unreal Engine", в котором Вы научитесь создавать игры на C++ с использованием этого движка.
Подпишитесь на мой канал на YouTube, где я регулярно публикую новые видео.
Подписаться
Подписавшись по E-mail, Вы будете получать уведомления о новых статьях.
Подписаться
Добавляйтесь ко мне в друзья ВКонтакте! Отзывы о сайте и обо мне оставляйте в моей группе.
Сегодня мы поговорим о факториалах. Это одна из самых базовых функций, которые программисту нужно знать, а заодно — уметь с этим работать. Итак, приступим. Факториал числа n — это значение произведения (умножения) всех натуральных чисел от 1 до n, которое обозначается как n! Как это выглядит: И ещё одно небольшое правило, для 0: Если мы хотим, к примеру, получить разницу факториалов 6! и 4!: Давайте взглянем, как это будет выглядеть в Java и разберемся с несколькими способами того, как можно вычислить факториал.
Обычное решение
Ничего сложного: используем пришедшее число как размер нашего цикла, в котором умножаем на все предыдущие числа, пока не дойдём до f. И в main: Проверяем и получаем искомый результат: 696.
Рекурсивное решение
условие выхода из метода, при достижении которого метод должен перестать вызывать самого себя и начать отдавать значения наверх. Ведь иначе мы получим бесконечный цикл из вызова методом самого себя и как следствие — StackOverflowError.
некоторая обработка (логика), необходимая в данной ситуации + вызов самого себя, но уже с другим входящим значением.
Решение со Stream
Для не знающих stream функционал или для желающих освежить его в памяти, будет полезно прочитать вот это. Тут мы используем специальный класс IntStream , дающий дополнительные возможности при работе со stream из int значений. Для создания такого stream мы используем его статический метод rangeClosed, который создаёт значения с 2 до f включительно с шагом 1. Далее мы объединяем все значения с помощью метода reduce, а именно — показываем в нем, как мы хотим их объединить. Наконец, мы получаем результирующее значение с помощью терминального метода getAsInt.
Применение BigInteger
В Java часто для обработки чисел, особенно БОЛЬШИХ, используется класс BigInteger. Ведь если мы используем int, то максимальный факториал, который мы можем взять без потери данных, — 31, для long — 39. А что если нам нужен будет факториал 100? Давайте же рассмотрим предыдущие варианты решения, но с использованием BigInteger.
Обычное решение
Алгоритм подсчёта по сути тот же, но здесь мы используем возможности BigInteger: BigInteger.ONE — для задания стартового значения 1. multiply — умножение между предыдущим значением факториала и текущим числом.
Рекурсивное решение
Решение cо Stream
По сути всё то же самое, но с BigInteger. В stream у нас появился метод mapToObj, которым мы преобразуем значения int в BigInteger, чтобы в дальнейшем перемножить их между собой с помощью multiply (ну и добавился get для взятия объекта из обёртки Optional). Если же мы запустим любой из этих трёх методов с аргументом 100, то у нас не случится переполнения и мы получим:
Вычисление больших факториалов на JavaScript
Продолжаю делать первые шаги в JavaScript. Пытаюсь написать процедуру, вычисляющую факториал:
function factorial ( n )
for ( i = n - 1 ; i > 0 ; i -- ) <
n *= i ;
Кажется, она потихонечку работает (типа, ура?), но только для маленьких чисел.
Например:
выдаёт , однако
уже выдаёт .
С другой стороны, Альфа успешно вычисляет факториал числа 1000.
Можно ли заставить JavaScript сделать то же самое?
P. S.
Приму любые замечания по коду, включая эстетические. И вообще, любые замечания, так или иначе касающиеся программирования. Когда делаешь первые шаги, важна каждая мелочь.
Для таких задач нужна арифметика произвольной точности (либо встроенная в язык, либо реализованная в виде внешней библиотеки). Насколько я знаю, в Javascript недавно вставили соответствующий примитивный тип BigInt, но насколько это работоспособно уже сейчас, сказать не берусь.
Последний раз редактировалось arseniiv 02.07.2018, 23:54, всего редактировалось 1 раз.
.
* Лень копаться в стандартах насчёт возможных альтернатив (например, более широких форматов, когда доступны), но подавляющее большинство реализаций должно быть в согласии.
Плюс почему не работает этот код: введите в консоли Number.MAX_VALUE и получите наверняка 1.7976931348623157e+308 .
Вы правы, именно это значение и получилось.
А есть способ обойти это ограничение? Почему, например, в Альфе не так?
Потому что Альфа изначально представляет целые числа иначе и использует арифметику произвольной точности. В Питоне, например, целые тоже могут быть любой длины.
Aritaborian
Я правильно понимаю, что в JavaScript, оказывается, нельзя - и точка? Он не для таких вещей создан?
Есть какие-то внешние библиотеки. И см. выше, что написал Pphantom про новый тип данных. Но подробностей вы от меня не добьётесь, не настолько хорошо разбираюсь.
Задействуйте мозг для смены алгоритма вычислений и замените умножение сложением логарифмов (для удобства можно даже десятичных). Точность пострадает, зато диапазон допустимых чисел вырастет на порядки. Преобразование в нормальную запись делать уже для результата при выводе человеку, тоже руками (вот тут десятичные сильно пригодятся).
Конечно это не решает проблему больших чисел в общем, но такие обходные пути часто можно найти, при желании, правда в каждом конкретном случае свои.
Задействуйте мозг для смены алгоритма вычислений и замените умножение сложением логарифмов (для удобства можно даже десятичных).
Последний раз редактировалось Dmitriy40 03.07.2018, 01:48, всего редактировалось 1 раз.
Если использовать логарифмы, то для лучшей точности стоит идти в сторону увеличения чисел, а не уменьшения как сейчас в коде.
Точность в любом случае не превысит где-то девяти-десяти знаков, в отличии от BigInt, который вообще говоря точный, зато медленнее логарифмов (для достаточно длинных чисел).
PS. Ну а без мозга изучать программирование, и тем более заниматься им, полностью бессмысленно.
Читайте также: