Может ли кто-нибудь объяснить этот алгоритм вычисления больших факториалов?

я наткнулся на следующую программу для вычисления больших факториалов (числа до 100) .. может кто-нибудь объяснить мне основную идею, используемую в этом алгоритме ?? Мне нужно знать только математику, применяемую при вычислении факториала.

#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{

      unsigned int d;

      unsigned char *a;

      unsigned int j, n, q, z, t;

      int i,arr[101],f;

      double p;


    cin>>n;
    p = 0.0;
    for(j = 2; j <= n; j++)
        p += log10(j);
    d = (int)p + 1;
    a = new unsigned char[d];
    for (i = 1; i < d; i++)
        a[i] = 0; //initialize
    a[0] = 1;
    p = 0.0;
    for (j = 2; j <= n; j++)
    {
        q = 0;
        p += log10(j);
        z = (int)p + 1;
        for (i = 0; i <= z/*NUMDIGITS*/; i++)
        {
            t = (a[i] * j) + q;
            q = (t / 10);
            a[i] = (char)(t % 10);
        }

    }
    for( i = d -1; i >= 0; i--)
        cout << (int)a[i];
    cout<<"\n";
    delete []a;

return 0;
}

c++ algorithm factorial
person Vaibhav    schedule 24.01.2010    source источник
comment
Где вы нашли алгоритм? Вы должны всегда включать эту информацию, чтобы правильно указать авторство, но она также может быть полезна при ответе на вопрос.   -  person Bill the Lizard    schedule 24.01.2010
comment
Если это не предпоследний пример того, почему написание читаемого кода - это большой бонус, то я не знаю, что это такое. Этот код не заслуживает объяснения, его следует переписать.   -  person Lasse V. Karlsen    schedule 24.01.2010
comment
Как называется этот алгоритм?   -  person mahendiran.b    schedule 11.12.2014
comment
ИМХО, есть баг. Должно быть a = new unsigned char[d+1];   -  person user31264    schedule 24.05.2016

Ответы (1)


arrow_upward
86
arrow_downward

Обратите внимание, что

n! = 2 * 3 * ... * n

так что

log(n!) = log(2 * 3 * ... * n) = log(2) + log(3) + ... + log(n)

Это важно, потому что если k является положительным целым числом, то верхний предел log(k) - это количество цифр в десятичном представлении k. Таким образом, эти строки кода подсчитывают количество цифр в n!.

p = 0.0;
for(j = 2; j <= n; j++)
    p += log10(j);
d = (int)p + 1;

Затем эти строки кода выделяют место для хранения цифр n!:

a = new unsigned char[d];
for (i = 1; i < d; i++)
    a[i] = 0; //initialize

Затем мы просто выполняем алгоритм умножения в начальной школе

p = 0.0;
for (j = 2; j <= n; j++) {
    q = 0;
    p += log10(j);
    z = (int)p + 1;
    for (i = 0; i <= z/*NUMDIGITS*/; i++) {
        t = (a[i] * j) + q;
        q = (t / 10);
        a[i] = (char)(t % 10);
    }
}

Внешний цикл выполняется с j с 2 до n, потому что на каждом шаге мы умножаем текущий результат, представленный цифрами в a, на j. Внутренний цикл - это алгоритм умножения для начальной школы, в котором мы умножаем каждую цифру на j и переносим результат в q, если необходимо.

p = 0.0 перед вложенным циклом и p += log10(j) внутри цикла просто отслеживают количество цифр в ответе на данный момент.

Кстати, я думаю, что в этой части программы есть ошибка. Условие цикла должно быть i < z, а не i <= z, иначе мы будем писать после конца a, когда z == d, что обязательно произойдет, когда j == n. Таким образом замените

for (i = 0; i <= z/*NUMDIGITS*/; i++)

by

for (i = 0; i < z/*NUMDIGITS*/; i++)

Затем мы просто распечатываем цифры

for( i = d -1; i >= 0; i--)
    cout << (int)a[i];
cout<<"\n";

и освободить выделенную память

delete []a;
person jason    schedule 24.01.2010
comment
Действительно - +1 от меня. Я бы отдал больше, если бы мог. - person duffymo; 24.01.2010