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

Question

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

После дальнейших поисков я не смог найти никакого документированного решения для этого, поэтому я нашел свое собственное. Если вы добавите следующий метод и поле к реализации дочерней формы, это исправит проблему:

protected override void OnVisibleChanged(EventArgs e)
{
    base.OnVisibleChanged(e);

    if (!Visible)
    {
        _lastState = WindowState;
    }
    else
    {
        if (_lastState == FormWindowState.Maximized)
            WindowState = FormWindowState.Maximized;
    }
}

FormWindowState _lastState = FormWindowState.Normal;

Однако, если у кого-то есть лучшее исправление, мне было бы очень интересно узнать об этом.

22

factorial algorithm c++

задан Deanie 24 May 2016 в 01:45

1 ответ

Другие вопросы по тегам:

factorial algorithm c++

Похожие вопросы:

score 85 · Accepted Answer

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

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

, так что

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

Это важно, потому что если k является положительным целым числом, то верхний предел log(k) является количеством цифр в представление базы-10 из 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++)

на

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

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

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

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

delete []a;