6-10 阶乘计算升级版

本题要求实现一个打印非负整数阶乘的函数。

函数接口定义

void Print_Factorial ( const int N );

其中N是用户传入的参数，其值不超过1000。如果N是非负整数，则该函数必须在一行中打印出N!的值，否则打印“Invalid input”。

裁判测试程序样例

#include <stdio.h>

void Print_Factorial ( const int N );

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

/* 你的代码将被嵌在这里 */

输入样例

15

输出样例

1307674368000

分析及答案

与6-8相比，这道题有两处不同：

1. 输入小于0时要求输出指定语句，这在6-8是由裁判程序实现的；
2. 扩大了输入的范围，6-8的输入不大于12，甚至可以将答案储存到数组中直接取出，这里的输入范围扩大到了1000.

第2点不同意味着6-8的程序没有办法直接用在这里，因为输入范围的扩大意味着结果范围的扩大。为什么6-8的输入被限定在了12？因为$12!=479001600$，而$13!=6227020800$，已经超出了整型所能表示的范围，在这里我们还能用unsigned long救一下，但对于更大的数字，任何现有的数据类型都没法完整地储存，溢出是必然的。因此，我们必须使用不同的方式来进行这种大数阶乘。

下面的函数采用的方式是，用一个足够大的数组来表示数字，当中每一个元素都表示某一位上的数字（0~9），并建立一个变量count来储存当前数组表示数字的位数。进行阶乘计算时，采取以下方式：

1. 先对每一位去乘当前的乘数
2. 从个位开始往上遍历，如果有某一个元素大于9的就进位，如果最高位也需要进位的，同时也更新count变量。

最后，从count指定的最高位开始，一路输出到个位。

void Print_Factorial ( const int N ){
    if(N<0) {
        printf("Invalid input");
        return 0;
    }
    //考虑N为1000时位数已经超过一般数据类型的上限，使用数组进行”模拟乘法“
    //1000!<10^(3x1000)=10^3000,该数有3000位
    int num[3000]={0},i,count=0,j=0,k;
    num[0]=1;//个位数为1
    for(i=1;i<=N;i++){
        j=0;//每次都要从个位开始计算
        while (j<=count)
        {
            num[j]*=i;
            j++;
        }
        for (j = 0; j  <= count; j++)
        {
            if (num[j]>=10)
            {
                if (num[j+1]==0&&j+1>count)
                {
                    count++;//最高位需要进位时，位数新增一位
                }
                num[j+1]+=num[j]/10;
                num[j]=num[j]%10;
            }
        }
        
    }
    while(count>=0){
        printf("%d",num[count]);
        count--;
    }
}