題目描述

輸入一個正整數(shù)N，輸出N的階乘。

輸入描述:

正整數(shù)N(0<=N<=1000)

輸出描述:

輸入可能包括多組數(shù)據(jù)，對于每一組輸入數(shù)據(jù)，輸出N的階乘

示例1

輸入

4
5
15

輸出

24
120
1307674368000

思路

這題相對于前面那一題階乘，數(shù)據(jù)規(guī)模擴大了，為 1000 以內(nèi)的正整數(shù)，所以只能用數(shù)組存數(shù)，于是想到把數(shù)組的每一位當作萬進制的每一位，之所以選用萬進制，是因為最大值 1000 乘以一萬也不會溢出 int，如果數(shù)據(jù)規(guī)模給的是100000以內(nèi)，那么可以選擇千進制，保證 int 不溢出

解法

#include <stdio.h>

void factorial(int N) {
    int a[1001] = {0};    //使用萬進制，數(shù)組的每個值當作萬進制的一位，則每個數(shù)組位可以存4位數(shù)，最大可以存4004位數(shù)，如果還不夠，可以再加
    int tag = 1;    //下方控制輸出用得到
    a[1000] = 1;    //由于是倒著存，便于正著輸出，所以初始最后一個數(shù)組為 1
    for (int i = 1; i <= N; i++) {    //待求階乘的數(shù)遍歷一遍
        for(int k = 0; k < 1001; k++)    //由于進位規(guī)則是先乘再進位，所以先把每一位都乘 i，下面再處理進位
            a[k] *= i;
        for(int j = 1000; j >=0; j--){    //大于一萬的進位
            if (a[j] > 10000) {
                a[j - 1] += a[j] / 10000;
                a[j] %=10000;
            } 
        }
    }
    for (int i = 0; i < 1001; i++) {    //每位數(shù)組夠四位直接輸出，不夠則前面補零
        if (!tag) {    //tag 改變則說明已經(jīng)不是第一個數(shù)了，則需要補零
            if (a[i] >= 1000)
                printf("%d", a[i]);
            else if (a[i] >= 100)
                printf("0%d", a[i]);
            else if (a[i] >= 10)
                printf("00%d", a[i]);
            else
                printf("000%d", a[i]);
        }
        if (a[i] != 0 && tag) {    //第一個數(shù)不用補零，tag 用來記錄第一個數(shù)
            printf("%d", a[i]);
            tag = 0;
        }
    }
    printf("\n");
}

int main() {
    for(int N; ~scanf("%d", &N);)
        factorial(N);
    return 0;
}