我碰到下面的程序计算大的阶乘（数字大如100）..谁能给我解释一下这个算法中使用的基本理念？ 我需要知道的只是在计算阶乘实现的数学。

 的#include＆LT; CMATH＆GT;
＃包括＆LT;的iostream＆GT;
＃包括＆LT; cstdlib＆GT;

使用名字空间std;

诠释的main（）
{

      无符号整型D组;

      无符号字符*一个;

      unsigned int类型J，N，Q，Z，T;

      INT I，编曲[101]，F;

      双磷;


    霉素＆GT;将N;
    P = 0.0;
    为（J = 2; J＆LT; = N; J ++）
        P + = LOG10（J）;
    D =（int）的P + 1;
    A =新的无符号的char [D];
    对于（i = 1; I＆LT; D​​组;我++）
        A [1] = 0; //初始化
    一个[0] = 1;
    P = 0.0;
    为（J = 2; J＆LT; = N; J ++）
    {
        Q = 0;
        P + = LOG10（J）;
        Z =（int）的P + 1;
        对于（i = 0; I＆LT; = Z / * NUMDIGITS * /;我++）
        {
            T =（A [1] * j）条+ Q;
            Q =（T / 10）;
            A [1] =（char）的（T％10）;
        }

    }
    对（我= D -1; I＆GT; = 0;我 - ）
        COUT＆LT;＆LT; （int）的A [1];
    COUT＆LT;＆LT;\ N的;
    删除[]一个;

返回0;
}
 

解决方案

注意

  N！ = 2 * 3 * ... * n个
 

让

 的log（n！）=日志（2 * 3 * ...... * N）=日志（2）+日志（3）+ ... +的log（n）
 

这是很重要的，因为如果 K 是一个正整数，然后日志的上限（K）是多少在基-10重$ P $ K 的psentation数字。因此，code这些行计算的位数的 N！。

  P = 0.0;
为（J = 2; J＆LT; = N; J ++）
    P + = LOG10（J）;
D =（int）的P + 1;
 

然后，code这些行分配的空间来容纳 n个位数：

  A =新的无符号的char [D];
对于（i = 1; I＆LT; D​​组;我++）
    A [1] = 0; //初始化
 

然后，我们只是做了年级学校乘算法

  P = 0.0;
为（J = 2; J＆LT; = N; J ++）{
    Q = 0;
    P + = LOG10（J）;
    Z =（int）的P + 1;
    对于（i = 0; I＆LT; = Z / * NUMDIGITS * /;我++）{
        T =（A [1] * j）条+ Q;
        Q =（T / 10）;
        A [1] =（char）的（T％10）;
    }
}
 

外环从Ĵ从 2 运行 N ，因为在每一个步骤，我们将乘当前结果再由位数在按Ĵ。内环是等级学校乘算法，其中我们乘每个数字由Ĵ和实施结果为①如果有必要的。

在 P = 0.0 前的嵌套循环和 P + = LOG10（J）循环内刚跟踪数字的数目中的答案为止。

顺便说一句，我认为在这部分程序的错误。循环条件应该是 I＆LT; ž不是 I＆LT; = Z ，否则我们会写过去的结束 A 当以Z = D 这会发生一定时Ĵ==ñ。因此，更换

 为（i = 0; I＆LT; = Z / * NUMDIGITS * /;我++）
 

按

 为（i = 0; I＆LT; Z / * NUMDIGITS * /;我++）
 

然后，我们只是打印出来的数字

 的（我= D -1; I＆GT; = 0;我 - ）
    COUT＆LT;＆LT; （int）的A [1];
COUT＆LT;＆LT;\ N的;
 

和自由分配的内存

 删除[]一个;
 

i came across the following program for calculating large factorials(numbers as big as 100).. can anyone explain me the basic idea used in this algorithm?? I need to know just the mathematics implemented in calculating the factorial.

#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;
}

Note that

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

so that

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

This is important because if k is a positive integer then the ceiling of log(k) is the number of digits in the base-10 representation of k. Thus, these lines of code are counting the number of digits in n!.

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

Then, these lines of code allocate space to hold the digits of n!:

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

Then we just do the grade-school multiplication algorithm

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);
    }
}

The outer loop is running from j from 2 to n because at each step we will multiply the current result represented by the digits in a by j. The inner loop is the grade-school multiplication algorithm wherein we multiply each digit by j and carry the result into q if necessary.

The p = 0.0 before the nested loop and the p += log10(j) inside the loop just keep track of the number of digits in the answer so far.

Incidentally, I think there is a bug in this part of the program. The loop condition should be i < z not i <= z otherwise we will be writing past the end of a when z == d which will happen for sure when j == n. Thus replace

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

by

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

Then we just print out the digits

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

and free the allocated memory

delete []a;