ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   28 Nov 2002  10:48:06
 To : Alexander Ivanchenko
 Subject : Факториал
 -------------------------------------------------------------------------------- 
 

 Thu Nov 28 2002 08:34, Alexander Ivanchenko wrote to Ilia Kantor:
 
  
  IK>> Дык, степень-то все равно придется вычислять ! Как бы то ни было, даже
  IK>> через FEE факториал считается быстро, но минимум за логарифм n.
 
  AI> Хорошо, если нет способа вычисления одним выражением, как можно наиболее
  AI> эффективно вычислить факториал, в расчёте на экономию процессорного
  AI> времени?
 
 Самый быстрый способ его посчитать - перемножить в лоб :)
 Формула Стирлинга полезна для ОЧЕHЬ больших значений (и тогда работают
 обыкновенно не с ней, а с ее логарифмом) или же для аналитических выкладок,
 иногда позволяющих избавиться от факториала вообще (пример - переход от
 биномиального к нормальному распределению).
 Часто искомая величина - не факториал, а отношение факториалов, тогда бывает
 полезно предварительно избавиться от общих сомножителей, и также
 переупорядичить их, дабы не было переполнения.
 Скажем, число сочетаний из 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)
 и переполнения не будет.
 Если речь идет о многократном вычислении факториала для десятка-другого
 значений аргумента - воспользуйтесь таблицей, предварительно заполненной.
 Hо чего точно не следует делать - считать по примеру из главы про рекурсию:)
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Факториал   Alexander Ivanchenko   27 Nov 2002 19:47:36   Факториал   Ilia Kantor   27 Nov 2002 21:15:56   Факториал   Evgenij Masherov   27 Nov 2002 21:17:02   Факториал   Vladimir Vassilevsky   27 Nov 2002 21:48:51   Факториал   Ilia Kantor   28 Nov 2002 02:45:51   Факториал   Alexander Ivanchenko   28 Nov 2002 09:34:05   Факториал   Evgenij Masherov   28 Nov 2002 10:48:06   Факториал   Ilia Kantor   30 Nov 2002 01:36:11   Факториал   Alexander Ivanchenko   30 Nov 2002 09:37:13   Факториал   Ilia Kantor   01 Dec 2002 12:32:05   Факториал   Nickita A Startcev   01 Dec 2002 22:20:18