求大数的阶乘问题


问题描述

求一个大数(如100)的阶乘。

问题分析

  1. C语言当中各种数据类型的取值范围:
    • 整型数据:-32768——32767
    • 长整型:-2147483648——2147483647
    • 单精度:六位精度,$\pm(1.7e-38—1.7e+38)$
    • 双精度:17位精确度,$\pm(1.7e-308—1.7e+308)$
    • 要么不够大,要么不够精确
  2. 存储:可用整型数组,每个元素存储若干位(6位)
  3. 数组长度:由式$\log(n!)=\theta(n\log{n})$确定。若每个元素存储6位,则$log(n!)=100\log{(100)}/6=34$
  4. 采用竖式乘法原理,每次一个元素和一个较小的整数i相乘,该过程进行迭代(i从1到n)。相乘的结果记为b,$b\ mod\ 10^6$为当前位(6位数),存入a[j],$b/10^6$为进位,下一位的$b=a[j+1]+d$
  5. 因此,采用两层循环:外层循环迭代n($2\rarr n$),内层循环迭代j($1\rarr len$),最后一次的进位再用一个元素存储
  6. 时间复杂度:

$$
O(n)=\sum_2^n\sum_1^{len}C\=C\sum_2^n{len}\ =C(n-1){len}\=C(n-1)\Theta(n\log{n})/6\=O(n^2\log{n})
$$

/*
求大数的阶乘,如100!
*/
#include <stdio.h>

void output(int a[], int len)
{
    int i = len;
    for (; i > 0; --i)
        printf("%d", a[i]);
}

void factorial(int n)
{
    int a[100] = {0}, j;
    a[1] = 1;
    int len = 1;
    for (int i = 2; i <= n; ++i)
    {
        int d = 0;
        for (j = 1; j <= len; ++j)
        {
            int b = a[j] * i + d;
            a[j] = b % 1000000;
            d = b / 1000000;
        }
        if (d != 0)
        {
            a[j] = d;
            len += 1;
        }
    }
    output(a, len);
}

int main()
{
    int n;
    printf("Input n: ");
    scanf("%d", &n);
    factorial(n);
    return 0;
}

文章作者: 恰醋
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 恰醋 !
评论
  目录