PTA 6-10 阶乘计算升级版（详讲）

6-10 阶乘计算升级版 - 基础编程题目集 (pintia.cn)https://pintia.cn/problem-sets/14/exam/problems/type/6?problemSetProblemId=742&page=0

首先这道题不能用我们之前学过的阶乘计算方法来解决，比如下面这段代码就无法通过全部的样例

void Print_Factorial ( const int N )
{if(N < 0){printf("Invalid input");return ;}unsigned long long int ret = 1;for(int i = 1; i <= N; i++){ret *= i;}printf("%lld\n",ret);
}

运行结果：

这道题的难点就是N值的大小，如果N为1000，那么1000的阶乘所得的值，是无法被目前C语言中任何内置类型所定义的变量来接收。

C类型	32位平台	64位平台
char	1	1
short int	2	2
int	4	4
long int	4	8
long long int	8	8
float	4	4
double	8	8

首先我们来看下题目输入的样例

我们不难看出15的阶乘所得的值的长度是13位

那int类型定义的变量最大能储存值的长度是几位呢？

那么把15!的值赋给int类型定义的变量，就会产生数据的截断(数据丢失)，所以不能用int变量来存储数据

那么有人可能会问，那用long long int可以吗，我看它是8字节的，因该是能保存的下吧？

好，那我们来大概看看8字节最多能保存几位

那我们看看N最大可以是多少

不超过1000，也就是可以是1000的阶乘，那我们大概看下1000的阶乘是多少

因为8字节定义的变量最大可以存储数据的长度大概是2^10次方，所以我们无法用其存储1000阶乘的数据，那在我们的知识范围内是不是还有数组这个概念？所以这道题我们可以用数组来解决问题

再次之前我们可以看看100!和1000!阶乘大概有几位

在我们用数组来解决问题的时候我在抛个引例来方便后续理解

我们一般计算234×12是不是用下面这种方式来做的？

接下来我在用另一种方法来求得结果，大家继续往下看

本题代码展示

#define MAX_DIGITS 10000 // 足够存储1000!的位数void Print_Factorial(const int N)
{if (N < 0){printf("Invalid input\n");return;}int result[MAX_DIGITS]; // 用于存储大数int result_size = 1; // 当前大数的位数result[0] = 1; // 初始值为1（即0! = 1, 1! = 1）// 计算阶乘for (int i = 2; i <= N; i++){int carry = 0; // 进位// 逐位乘以i，并处理进位for (int j = 0; j < result_size; j++){int product = result[j] * i + carry;result[j] = product % 10; // 取个位数carry = product / 10; // 计算进位}// 处理剩余进位while (carry){result[result_size] = carry % 10;carry /= 10;result_size++;}}// 从数组的高位到低位输出结果for (int i = result_size - 1; i >= 0; i--){printf("%d", result[i]);}printf("\n");
}

接下来我就用我对本题目的理解做个分析

1. 首先我们要定义一个数组，那数组的长度我们可以给大于等于3000，我这代码给1万

2. 如果N小于0，那我们就输出字符串"Invalid input\n"，并结束函数运行，题目要求的

3. 因为数组有10000个元素，那我们是不是要统计我们用了有多少个元素？也叫做统计有效位数，因为0的阶乘是1，所以初始化的时候我们目前最大位数就是1，并且我们将数组第一个元素，也就是下标为0的位置初始化为1（0! = 1，1! = 1）

4. 首先我们i是从2开始的，因为1乘任何数，都是任何数(>0)，其次我们定义了carry用于统计进位数，初始化为0

5. 接下来定义的j是从0开始，并且j的值要小于目前最大存储有效位数，后续定义的product是求数组中的每一位乘于i，可以理解成上面计算234×12的计算过程，让234中的每一位依次乘12，并加上进位数carry（carry初始为0）

6. 而result[j]则是用于将刚刚上面相乘的结果取个位，存进result[j]中，这里我就先点到这里，我后面在补充

7. carry用于保存product除个位以外的数据，如果product是20，那carry就为2，如果product是200，那carry就是20,

8. 当上面for循环结束后，如果有产生进位那我们就要处理进位，处理进位之所以下标是result_size是因为不想修改之前得到的各各位数，就比如上面让234依次乘12，保留8，result[0] = 8，result_size = 1；保留0，result[1] = 0，result_size = 2；保留8，result[2] = 8，result_size = 3。此时是不是只剩进位数2，那我们就可以把2存到result[result_size]中，也就是result[3] = 2，然后因为数组增加了一位有效位，所以result_size需要++，而result数组保留了carry中的个位数，所以carry就需要除等10（去掉个位数，如果carry是20，去掉个数就是2）

9. 注意：最终for循环输出语句一开始i要等于result_size - 1

---

上面说的做个补充：

在for循环中，如果没有产生进位，比如3的阶乘，那result中保存的值就不会进入while循环被修改，最终的结果就是result数组中保存的值。

如果有产生进位，比如5的阶乘，一开始for循环当i不等于5的时候，每次相乘都会产生不同的值，这个值所得的个数可能会在循环中不断的被修改（比如result[0]或者result[1]会在当i不等5的时候可能会一直产生变化），只有当i等于N的时候，才能确定最终的结果