曲径通幽论坛

标题: 大数的阶乘 [打印本页]

---

作者: beyes    时间: 2011-9-1 11:59
标题: 大数的阶乘
由于类型的限制，大数的阶乘会导致变量溢出，所以无法直接得到结果，比如求 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);





    printf ("\n");    

    return 0;

}

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

---

欢迎光临 曲径通幽论坛 (http://www.groad.net/bbs/)

Powered by Discuz! X3.2