返回首页 - Notes - 2012

高精度阶乘


问题描述

输入不超过 1000 的整数,要求精确计算并输出该数的阶乘


算法求解

1000 的阶乘约等于 4*10的2567次方,使用常规的整数类型来计算肯定是办不到的了

这儿使用数组来解决,每一次相乘操作结束就将结果保存进数组,下一次计算就用当前值与数组已存值相乘,结果再次存入数组。。依次类推

由于两数相乘会出现进位,所以为方便操作,数组元素从个位开始存储,低位在前,高位在后

计算完成后,数组末尾极可能还有大量单元没有用到,输出时要把这些未用到的单元忽略

代码如下:

#include <stdio.h>
#include <string.h>

int
main(int argc, char *argv[]){
    const int max = 3000;
    int sum[max], num;

    scanf("%d", &num);

    // 将存储结果的数组元素除个位(也就是数组的第一位)置1以外,其他全部置0
    memset(sum, 0, sizeof(sum));
    sum[0] = 1;

    // 从2开始乘起
    for(int i = 2; i <= num; ++i){
        // 保存进位值
        int c = 0;
        // 每一次阶乘操作都将当前值与已有结果乘一遍
        for(int j = 0; j < max; ++j){
            // 各个位都乘上一遍,并加上低位乘法所得的进位值
            int s = sum[j]*i + c;
            // 取结果的个位数存储
            sum[j] = s % 10;
            // 取进位值进入下一轮的高位乘法
            c = s / 10;
        }
    }

    // j的值在循环外还要用到,所以声明在main里面,而不是声明在循环内
    int j;
    // 跳过数组结尾部分的若干零值,遇非零值结束跳跃操作
    for(j = max-1; j >= 0; --j){
        if(sum[j]){
            break;
        }
    }
    // 从数组末尾算起,从第一个非零值开始输出,直到第一个数组元素(也就是结果的个位)
    for(int i = j; i >= 0; --i){
        printf("%d", sum[i]);
    }
    printf("\n");

    return 0;
}

date : 2012-09-20