Есть такая математическая операция как факториал

Есть такая математическая операция как факториал: для натурального числа n это произведение всех натуральных чисел от 1 до n. Обозначается n!. Если записать рекуррентное (или рекурсивное, если угодно) определение 1!=1, (n+1)!=(n+1)n!, то можно получить и факториал нуля: 0!=1, положив n=0. Но дальше таким путем никак не пройти. Да и нужды нет.

Смысл факториала в том, что он выражает число упорядоченных перестановок n предметов. Ну, в самом деле: если предмет один, перестановок и нет, точнее, есть ровно одна. Если больше, то первым можно поставить любой предмет, это n вариантов. Каждому варианту соответствует (n-1)! перестановок меньшего числа предметов.

Если предметов нет вообще, то это "одна" перестановка.

Так, из трех цифр 6, 7 и 8 можно составить шесть трехзначных чисел: 678, 687, 768, 786, 867, 876.

А вот из букв слова МОЛОКО можно составить не 6!=720 шестибуквенных слов, потому что перестановки букв О слова не меняют. Поэтому надо разделить на число перестановок трех букв О, их 3!=6, и получится 5!=120.

Далее комбинаторные формулы быстро размножаются. Число способов выбрать упорядоченный набор из k предметов из n возможных, без повтора, конечно, это n!/(n-k)!. Это легко понять, если упорядочить все предметы и взять k последних; при этом каждому набору соответствует n-k первых, которые (n-k)! способами можно упорядочить, но их порядок нас уже не волнует.

А неупорядоченных наборов из k предметов из n возможных еще в k! раз меньше. Эта формула (число сочетаний, биномиальный коэффициент) заслуживает отдельной заметки.

Когда-то были популярны кодовые замки. На нем было десять кнопок с цифрами, и нужно было нажать три или четыре кнопки одновременно, чтобы отпереть замок. Сколько различных кодов и как быстро можно код подобрать?

Мы имеем именно такую задачу. Выбор без повтора и без учета порядка: кнопки нажимаются одновременно. Число кнопок n=10, выбор k=3 или 4. Получается 10!/7!/3!.

Считать это правильно так: сократим множители от 1 до 7, получив 8?9?10/(1?2?3)=720/6=120. Для k=4 получим 210. Всего 330 комбинаций, всего-то. Если три секунды положить на проверку комбинации, то за тысячу секунд, то есть минут за двадцать, можно отпереть любой кодовый замок.

Факториал очень быстро растет, быстрее экспоненты (хотя быстрее экспоненты вообще мало что растет в реальном мире). Но медленнее, чем n в степени n. Немного медленнее. Для его приближенного вычисления есть формула Стирлинга.

Формула асимптотическая: отношение точного значения к приближенному стремится к единице при n к бесконечности. Однако менее известно, что формула неплохо работает и при малых n.

Так, при n=1 Стирлинг дает 0.92 вместо 1, то есть относительная погрешность менее 8%, а далее только убывает: при n=2 Стирлинг дает 1.9 вместо 2 (ошибка 4%), для n=3 имеем 5.8 вместо 6 (ошибка 2.7%), и так далее. И это я еще взял грубые оценки для чисел пи и е.

Формулу вывести точно — не так просто, но грубо — легко. Логарифм факториала есть сумма логарифмов, а ее можно приблизить интегралом:

ln(n!)=?ln(i) ? ? ln(x)dx = nln(n) - n + 1.

Сумма по i от 1 до n, интеграл от 1 до n.

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

Обнаружил вот, что логарифм по основанию 16 от 42! примерно равен 42. Неспроста! Неспроста!!

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

Общеизвестно, что неправильно считать факториал рекурсивно, хотя он именно рекурсивно определяется. Цикл значительно эффективнее. Сейчас это не так важно, если вам нужно именно посчитать факториал, но в вычислительноемких задачах это может быть критично. Не говоря уж о том, что рекурсия может запросто стек переполнить, с самыми печальными последствиями.

Так, такой однострочник

time perl -E 'sub f{my $n=shift;$n>1?return log($n)+f($n-1):return 0}; for(1 .. shift()){say f($_)}' 2000 > 1

работает на моем компьютере 0.685 секунды, а такой:

time perl -E 'for(1 .. shift()){$f=0;for my$i(1..$_){$f+=log($i)}say $f}' 2000 > 2

0.141 секунды: в 4.7 раза быстрее. Оба считают логарифмы факториалов чисел от 1 до 2000. Для 3000 получается 0.965 против 0.285, что около 3.4 раза.

То есть "в разы" выигрыш у цикла против рекурсии.

Да и вообще, факториал надо осторожно считать. Сокращать где надо... В общем, в лоб лучше не переть.

Факториал не вполне подпадает под условия теоремы об аналитическом продолжении (две аналитические функции, совпадающие на множестве с предельно точкой, совпадают повсюду в области определения), но функция, принимающая в точках 1, 2, ... заданные значения существует и может считаться аналитическим продолжением факториала. Это гамма-функция. Точнее, Г(n+1)=n!, но это мелочи. Про нее расскажу в другой раз.

Источник: vk.com

Комментарии: