c++ - 谁能解释这种算法来计算大阶乘？

我遇到了以下用于计算大阶乘(最大为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;
}

最佳答案

注意

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

以便

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

这很重要，因为如果k是一个正整数，则log(k)的上限是k的以10为基数表示的位数。因此，这些代码行正在计算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时发生。因此更换

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;

关于c++ - 谁能解释这种算法来计算大阶乘？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2127540/