Другие языки программирования и технологии

как посчитать 365! (С++) Нужен алгоритм вычисления факториала больших чисел.

Саша Зуев
Саша Зуев
2 203
А какой факториал нужен? целочисленный или с плавающей точкой?
Во многих учебниках приводиться рекурсивный алгоритм вычисления факториала. Но это лишь пример, чтобы новичкам объяснить что такое рекурсия, а вовсе не пример для практического использования. Глупо делать рекурсию, если можно обойтись простым циклом.
int N = 365;
int F = 1;
for (int i = 2; i <= N; ++i)
{
F *= i;
}
Вот и весь факториал. И какие то рекурсии применять нет необходимости.
Проблема то заключается в том, что факториал растет очень быстро, и как правило умещается в одно машинное слово для не очень больших N (первый - второй десяток) .

Даже если использовать числа с плавающей точкой, то все равно это не сильно помогает (сотню с небольшим) .
Тогда считай логарифм факториала
int N = 365;
double F = 1;
for (int i = 2; i <= N; ++i)
{
F += log10((double)i);
}
int P = (int)floor(F);
F -= P;
F = pow(10.0, F);
P -= 1;
printf("ю%d\n", F, P);

А если нужен целочисленный факториал, то придется задействовать число с многократной точностью (массив целых, как одно число) . Кстати, написать арифметику для не так уж и сложно для этого случая. Посмотри на цикл. F - число многократной точности, i - число однократной точности. Это несложно сделать.

DWORD N = 365;
for (DWORD i = 2; i <= N; ++i)
{
F += log((double)i);
}

DWORD SIZE = (DWORD)ceil(F / log(4294967296.0));
DWORD *F = new DWORD [ SIZE ];
memset(F, 0, SIZE * sizeof(DWORD ));
F[0] = 1;

DWORD Count = 1;
for (DWORD i = 2; i <= N; ++i)
{
DWORD Carry = 0;
for (DWORD j = 0; j < Count; ++j)
{
ULARGE_INTEGER u;
u.QuadPart = (UINT64)N[j] * i;
u.QuadPart += Carry;
N[j] = u.LowPart;
Carry = u.HighPart;
}
if (Carry)
{
N[Count++] = Carry;
}
}

// Факториал готов. Чтобы его вывести в десятичном предатавлении понадобится длинной деление (число многократной точности на одинарной точности - 10) Делается примерно также.

delete [] F;
АБ
Алмат Базарбаев
21 360
Лучший ответ
Ну, такой факториал считается быстро даже рекурсивно. Тебе тут скорее потребуется реализация типа для больших чисел...
Дениска Казаков популярно и доступно для понимания большинству совершенно незнакомых с математикой людей.