Возможно ли оптимизировать вычисление факториала? -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [216.73.216.21]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Возможно ли оптимизировать вычисление факториала?

2005fs

Сообщ. #1 , 25.06.10, 17:02

Profi

Профиль · PM

Поощрения: 3 Dgm

Рейтинг (т): 38

Необходимо вычислить выражение
res = !n - !(n-1) + !(n-2) - ...

Вот код который я написал:

private static int Calculate(int n)

{

if (n < 0)

throw new ArgumentException("Input parameter can't be less then zero", "n");

int currentFact = n % 2 == 0 ? 1 : -1;

int currSumm = currentFact;

for (int i = 1; i <= n; i++)

{

currentFact *= i * (-1);

currSumm += currentFact;

}

return currSumm;

}

Возможно ли его еще оптимизировать?

esperanto	Сообщ. #2 , 25.06.10, 18:03
математик Профиль · PM Поощрения: 5 Dgm Рейтинг (т): 50	Да факториал от отрицательных тоже существует, всетаки это Гама ф-ия. Так что обработку исключения можно убрать. А каков ваш алгоритм? напишите словами.

Аэтерос	Сообщ. #3 , 26.06.10, 02:38
штудент Профиль · PM Рейтинг (т): 36	Цитата 2005fs @ 25.06.10, 17:02 Возможно ли его еще оптимизировать? Разве что таблицей

Pavlovsky	Сообщ. #4 , 26.06.10, 07:36
Senior Member Профиль · PM Рейтинг (т): 61	Можно это выражение считать приблизительно. Если n! вынести за скобки, то в скобках останется знакопеременный ряд очень быстро убывающий. То есть достаточно вычислять два - три члена этого ряда.

Pavia

Сообщ. #5 , 26.06.10, 08:30

Master

Профиль · PM

Поощрения: 2 Dgm

Рейтинг (т): 257

Возьмем ряд тейллора найдем наиболее похожую из известные функций ch(x) и sh(x)
$user posted image$
$user posted image$
Ясно что нам нужно ch(x)- sh(x)=e^(-x)

$user posted image$
возьмем x=1 чтобы в числителях получить 1^n=1
Возьмем первые n элементов приведём к одному знаменателю n!
получим
(!n - !(n-1) + !(n-2) ..)/!n
И того e^(-1)*n!

$user posted image$
Возможно надо точнее опраксимировать факториал, но для cкорости возьмем эту формулу
sqrt(2*pi*n)*(n/e)^n/e=sqrt(2*Pi*n)*power(n,n)/power(e,n+1)

Сообщение отредактировано: Pavia - 26.06.10, 08:41

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0205 ] [ 15 queries used ] [ Generated: 20.06.25, 08:55 GMT ]