Как вычислить факториал в питоне

Как вычислить факториал в питоне

Факториалом числа называют произведение всех натуральных чисел до него включительно. Например, факториал числа 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]

Существующее решение

Самое короткое и, вероятно, самое быстрое решение:

Читайте также:  Виды кнопок в html

Построение собственных

Вы также можете создать собственное решение. Как правило, у вас есть два подхода. Тот, который мне подходит лучше всего:

(он работает также для больших чисел, когда результат становится 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 падает через пару секунд, все таки нужно помнить, что рекурсия не самая хорошая штука для таких вычислений :((

Читайте также:  World of warcraft ошибка 3d ускорения

Почему встроенная функция сильнее, лучше и быстрее? Могу предположить что написание на чистом С ему придает бодрости)))



Вычисление времени выполнения


Для примера разберем рекурсивный вариант. Мы должны с каждой рекурсивной процедурой связать временную функцию 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).

Ссылка на основную публикацию
Adblock detector