问题来了各位学神 - C语言论坛

得分:0

大数阶乘算法

转载别人的一篇日志，希望能帮到你
大数阶乘算法

前几天朋友问我一个问题：“10000的阶乘怎么算？”当时我就有点懵，“10000”这个数字太大了，无论用什么数据类型保存结果都会溢出。这可怎么办呢？一时间束手无策。然后被一顿鄙视。后来经朋友的提醒，才恍然大悟，终于知道怎么实现了，原来是使用数组来模拟数字，这样无论结果数字有多大，只要数组的长度够长就能表示出来，用这个办法可以进行大数据的运算。看起来还是挺有用的。我把它用程序实现出来，如果有用到的地方还可以借鉴一下。（最起码还可以拿来鄙视别人^_^）
首先定义一个足够长的数组。
拿10000的阶乘为例，最后的结果长度是35660位，所以我们定义一个40000个成员的数组就可以了。
int result[40000];
其核心思想就是把计算结果每一位上的数字保存到一个数组成员中，例如：
把124保存至数组中，保存结果应该是
result[0] 4
result[1] 2
result[2] 1
这样肯定是没有问题的,一个int型数据存放一个小于10的数是绝对不会溢出。但是处理起来就稍微有点麻烦。
把整个数组看成一个数字，这个数字和一个数相乘的时候，需要每一位都和这个乘数进行相乘运算还需要把前一为的进位加上。运算方法和小学数学是一样的，乘积的个位是当前位上应该表示的数字，10位以上的需要进位。因为乘数不可能大于10000，所以乘数和一个小于10的书相乘的时候不会大于100000，再加上前一位的进位用一个int型数据来保持这个结果就没有问题。写法如下：
int 结果 = result[x] * 乘数 + 进位;
每一位的计算结果有了，把这个结果的个位数拿出来放到这个数组元素上：
result[x] = 结果%10;
接下来的工作就是计算出进位：
进位 = 结果 / 10;
这样一位一位的把整个数组计算一遍，最后可能还有进位，用同样的方法，把进位的数值拆成单个数字，放到相应的数组元素中。
最后输出一下结果，从最高位吧数字打印一遍就OK了。完整程序如下，在VC6.0下调试通过。

程序代码：

#include <stdio.h>
int main()
{
    int carry,n,j;
    int a[40001];
    int digit;
    int temp,i; 
    while(scanf("%d",&n)!=EOF){
    a[0]=1;digit=1;
    for(i=2; i<=n; i++)
    {
        for(carry=0,j=1; j<=digit; ++j)
        {
            temp=a[j-1]*i+carry;
            a[j-1]=temp%10;
            carry=temp/10;
        }
        while(carry)
        {
            //digit++;
            a[++digit-1]=carry%10;
            carry/=10;
        }
    }

 
    for(int k=digit; k>=1; --k)
        printf("%d",a[k-1]);
    printf("\n");

 printf("length=%d\n",digit);

 }
    return 0;
}

#include <stdio.h> #include <stdint.h> #include <assert.h> #include <inttypes.h> uint64_t factorial_sigma( unsigned n ) { assert( n <= 20 ); uint64_t r=0, f=1; for( unsigned i=1; i!=n+1; ++i ) { //// 用来判断何时数值溢出，得出结论是n==21时会溢出，所以才有上面的 assert( n <= 20 ); //uint64_t t = f * i; //assert( t/f == i ); //f *= i; //t = r + f; //assert( t>=r && t>=f ); //r += f; f *= i; r += f; } return r; } int main( void ) { //// 测试 //assert( factorial_sigma(0) == 0 ); // 因为 1!==1 && 0!==1，所以从1!加到0!应该为0 //assert( factorial_sigma(1) == 1 ); // 1! //assert( factorial_sigma(2) == 3 ); // 1! + 2! //assert( factorial_sigma(3) == 9 ); // 1! + 2! + 3! //assert( factorial_sigma(4) == 33 ); // 1! + 2! + 3! + 4! //assert( factorial_sigma(20) == 2561327494111820313 ); printf( "%"PRIu64"\n", factorial_sigma(20) ); return 0; }