Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 5 равен произведению 1 * 2 * 3 * 4 * 5 = 120.
Формула нахождения факториала:
n! = 1 * 2 * … * n,
где n – это число, а n! – факториал этого числа.
Формулу можно представить в таком виде:
n! = 1 * … * (n-2) * (n-1) * n,
т. е. каждое предыдущее число меньше на единицу, чем последующее.
С помощью цикла можно найти факториал как по первой, так и второй формуле. Для вычисления факториала с помощью рекурсии используется вторая формула.
Вычисление факториала циклом
Вычисление факториала с помощью цикла for:
Нахождение факториала рекурсией
0 шаг. Вызов функции: fac(5)
1. fac(5) возвращает fac(4) * 5
2. fac(4) => fac(3) * 4
3. fac(3) => fac(2) * 3
4. fac(2) => fac(1) * 2
5. fac(1) => 1
6. 1 * 2 — возврат в вызов fac(2)
7. 2 * 3 — fac(3)
8. 6 * 4 — fac(4)
9. 24 * 5 – fac(5)
10. Возврат в основную ветку программы значения 120.
Функция factorial() модуля math
Модуль math языка программирования Python содержит функцию factorial(), принимающую в качестве аргумента неотрицательное целое число и возвращающую факториал этого числа:
95 Nir Levy [2011-02-28 01:22:00]
Как мне вычислить факториал целого в Python?
16 ответов
142 schnaader [2011-02-28 01:24:00]
Самый простой способ: math.factorial(x) (доступно в 2.6 и выше).
Если вы хотите/должны сами написать его, используйте что-то вроде
или что-то более читаемое:
Как всегда, Google — ваш друг;)
85 Joril [2011-02-28 01:25:00]
В Python 2.6 и выше попробуйте:
22 ciziar [2012-11-02 02:23:00]
Не обязательно, так как это такой старый поток. Но я сделал здесь еще один способ вычислить факториал целого числа, используя цикл while.
15 Tadeck [2012-01-29 03:12:00]
Существующее решение
Самое короткое и, вероятно, самое быстрое решение:
Построение собственных
Вы также можете создать собственное решение. Как правило, у вас есть два подхода. Тот, который мне подходит лучше всего:
(он работает также для больших чисел, когда результат становится long )
Второй способ достижения этого:
7 Nishanth [2013-10-19 14:51:00]
Если вы используете Python2.5 или старше, попробуйте
для нового Python, в математическом модуле есть факториал, как указано в других ответах здесь.
4 rahulm [2013-07-25 04:15:00]
Еще один метод вычисления факториала с использованием цикла for-loop —
2 Jordan [2011-02-28 01:27:00]
Вы имеете в виду:
2 binbjz [2018-03-29 12:50:00]
Из соображений производительности, пожалуйста, не используйте рекурсию. Это было бы катастрофично.
Проверьте результаты бега
Использование стека удобно (например, рекурсивный вызов), но оно обходится дорого: хранение подробной информации может занимать много памяти.
Если стек высок, это означает, что компьютер хранит много информации о вызовах функций.
Метод занимает только постоянную память (как итерация).
Или Использование для цикла
Проверьте результаты бега
Или используя встроенную функцию математики
Проверьте результаты бега
Вот моя попытка
Я знаю, что на этот вопрос ответили, но вот еще один метод с пониманием обратного списка диапазонов, делающий диапазон более легким для чтения и более компактным:
0 [2018-05-14 18:58:00]
Также работает одна строка, быстрые и большие числа:
Многие из этих методов очень хороши, но я бы сказал, что ваш лучший выбор — всегда использовать встроенную функцию. Однако есть очень легко создаваемые, если вы хотите увидеть, что происходит. Быстрый, который я придумал, почти так же, как и многие из них здесь.
Это довольно эффективный код, преимущество в том, что список создается, если вы не будете манипулировать некоторыми данными из списка, хотя я не уверен, почему вы действительно это делаете.
Изменить: только что увидел, что я разместил это на старой вещи. К сожалению.
Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.
воскресенье, 3 апреля 2011 г.
Вычисление факториала
Мне кажется, что это самый классический алгоритм из существующих. С примером реализации вы наверняка сталкивались и не раз, но для полноты картины, я просто обязан его описать. :))
Факториа́л числа n (обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел до n включительно:
. По определению полагают 0! = 1 . Факториал определён только для целых неотрицательных чисел.
Комбинаторная интерпретация
Рекуррентная формула
Итак это был тот минимум, который, как я считаю, должен знать любой уважающий себя. и всех тех кто его окружает, человек.
Теперь о реализации алгоритма. Как всегда средств много, от чего мы познакомимся с несколькими из них.
2 классических я возьму с сайта http://younglinux.info/algorithm/factorial
С использованием цикла
С использованием рекурсии
И на закуску, высокоинтеллектуальный пример с Вики :))
Ну и теперь самое вкусное и интересное, тестирование!
По их результатам я пришел к выводу, что скорость роста данных алгоритмов приблизительно равна. И по сему результат вычисления 70000! следующий:
- алгоритм с использованием цикла 4 function calls in 11.872 seconds
- алгоритм рекурсивный выбыл, подробнее читать тут
- зверский алгоритм с вики 70004 function calls in 13.211 seconds
- встроенный модуль math.factorial 4 function calls in 8.377 CPU seconds
Вывод таков, что не все нужно брать с википедии :)))
Просто получается многовато вызовов лямбда функций, ведь каждый вызов — это потери, хотим мы этого или нет.
Проблемы, возникшие с рекурсией: по умолчанию, максимальная глубина рекурсии равна 1000. Это ограничение предотвращает переполнение стека при бесконечных рекурсиях.
Я установил при помощи sys.setrecursionlimit(70000) новую глубину, но python падает через пару секунд, все таки нужно помнить, что рекурсия не самая хорошая штука для таких вычислений :((
Почему встроенная функция сильнее, лучше и быстрее? Могу предположить что написание на чистом С ему придает бодрости)))
Вычисление времени выполнения
Для примера разберем рекурсивный вариант. Мы должны с каждой рекурсивной процедурой связать временную функцию T(n), где n определяет объём аргументов процедуры. Затем получить рекуррентное соотношение для T(n). Естественной мерой объёма входных данных для функции fac, является значение n. Обозначим, через T(n) — время выполнения программы.
Время сравнения if имеет порядок роста О(1), а для последней строки О(1)+T(n-1), где О(1)-умножение на n, а T(n-1)-факториала с меньшим входным аргументом. Таким образом для некоторых констант c и d имеем,
Полагая, что n>2 и раскрывая выражение T(n-1)(т.е. подставляя n-1 вместо n и получившееся T(n-1) в предыдущую формулу T(n)), получим T(n)=2с+T(n-2), продолжая такие рассуждения до n-1 раз, получим T(n)=c(n-1)+d. Откуда имеем порядок роста О(n).
