Факториал

From

Evgenij Masherov (2:5020/175.2)

To

Alexander Ivanchenko

Date

2002-11-28T09:48:06Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Thu Nov 28 2002 08:34, Alexander Ivanchenko wrote to Ilia Kantor:

 
 IK>> Дык, степень-то все равно придется вычислять ! Как бы то ни было, даже
 IK>> через FEE факториал считается быстро, но минимум за логарифм n.

 AI> Хорошо, если нет способа вычисления одним выражением, как можно наиболее
 AI> эффективно вычислить факториал, в расчёте на экономию процессорного
 AI> времени?

Самый быстрый способ его посчитать - перемножить в лоб :)
Формула Стирлинга полезна для ОЧЕНЬ больших значений (и тогда работают
обыкновенно не с ней, а с ее логарифмом) или же для аналитических выкладок,
иногда позволяющих избавиться от факториала вообще (пример - переход от
биномиального к нормальному распределению).
Часто искомая величина - не факториал, а отношение факториалов, тогда бывает
полезно предварительно избавиться от общих сомножителей, и также
переупорядичить их, дабы не было переполнения.
Скажем, число сочетаний из N по M = N!/(M! (N-M)!) может привести при расчете
"наивном" - сначала посчитать факториалы, а потом поделить - к переполнению
уже при N порядка 50. Если же сперва заметить, что М! дает сомножители,
входящие в N!, и на них можно сократить, а затем соотнести оставшиеся
сомножители в числителе и знаменателе, так, чтобы не допустить чрезмерного
возрастания чисел, получим:
(N/(N-M))*((N-1)/(N-M-1))*((N-2)/(N-M-2)*...*(N-M+1)/1)
и переполнения не будет.
Если речь идет о многократном вычислении факториала для десятка-другого
значений аргумента - воспользуйтесь таблицей, предварительно заполненной.
Но чего точно не следует делать - считать по примеру из главы про рекурсию:)

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)