Факториальные факты

Сегодня речь пойдет о факториале, напомню - факториалом называется произведение всех натуральный чисел от 1 до n включительно, сокращенно факториал n обозначается n!. Давайте поробуем "выжать" из этого произведения максимум информации!

факториал

* - факториал 0 = 1 (так договорились).

Таблица первых значений:

n 0 1 2 3 4 5 6 7 8 9 10
n! 1 1 2 6 24 120 720 5040 40320 362880 3628800

Полезный факт: Количество цифр в записи n! превышает n, когда n≥25. А еще приблизительное значение 10! = 3.5 миллиона.

Рекуррентная формула. Давайте для приличия запишем формулу в рекуррентном виде.

факториал в рекуррентном виде

Неравенство. Давайте поробуем оценить n! сверху и снизу:
n!2 = (1*2*..*n)(n*..*2*1) = P( k(n+1-k), k = 1..n )
Имеем n≤k(n+1-k)≤(n+1)2/4, поскольку квадратный многочлен k(n+1-k)=(n+1)2/4-(k-(n+1)/2)2 принимает наиманьшее значение при k=1 и наибольшее - при k=(n+1)/2.
Поэтому nn/2≤n!≤(n+1)n/2n

Формула Стирлинга. Как было бы чудесно, если бы могли быстро вычислить n!, не вычисляя (n-1), (n-2) ... 2 значение. Оказывается, что данная задача решена, причем точность алгоритма уже при n=10 дает значение, близкое к 3598696, при этом погрешность 0.83% ≈ 1/120, что безумного хорошо.

формула Стирлинга

погрешность формула Стирлинга

Вывод:

↑ Расскажите друзьям о статье


Comments system Cackle

© EduNow.su — материалы подлежат полному/частичному копированию при указании прямой ссылки на источник. (Сегодня 29.06.17)