大数的阶乘

beyes

由于类型的限制，大数的阶乘会导致变量溢出，所以无法直接得到结果，比如求 100 的阶乘即使是 64 位的 long long 类型也不行。

如果使用 python 语言，那么得到 100 的阶乘最为容易：

[Plain Text] 纯文本查看 复制代码

#!/usr/bin/python

import math

print math.factorial(100)

运行输出：

$ python temp.py
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

对于 C 语言，这么大的数考虑用数组来存放。为了计算方便，可以考虑倒序存放阶乘结果，如 8! (40320)可以如下存放：

0

2

3

0

4

当笔算一个乘法时，我们会先从个位乘起，然后依次往上。每位相乘的结果分为有两部分，一部分是商( C 语言里的 / 除法运算结果，这个结果将作为进位，在下一次运算中加到其余数中)，一部分是余数，余数部分会和上一次运算的进位相加后保存下来。


下面程序就是模拟笔算的过程：

[C++] 纯文本查看 复制代码

#include <stdio.h>


#define FC 100        /*100的阶乘*/


static int a[FC * 3];    /*数组用来存储结果*/


int main()
{
    int i, j;
    int len = 1;    /*每次运算时对结果长度的跟踪*/
    int temp, carry;    /*temp为每位相乘时的结果;carry为每位相乘时的进位*/


    a[1] = 1;


    for (i = 2; i <= FC; i++) {    /*总阶乘长度循环*/
        carry = 0;
        
        for (j = 1; j <= len; j++) {    /*每次阶乘结果处理*/
            temp = a[j]*i + carry;    /*每位算得的结果加上上次运算的进位*/
            a[j] = temp % 10;    
            carry = temp / 10;    /*求进位*/
            if (j == len && carry !=0)    /*最高位算得的结果如果有进位则本次阶乘结果的长度则增加1位*/
                len++;
        }
    }
    for (i = len; i >=1; i--)
        printf ("%d", a[i]);


    printf ("\n");    
    return 0;
}

运算结果和 python 脚本里的相同。