题目title: 阶乘计算升级版 题目作者: 陈越 浙江大学
本题要求实现一个打印非负整数阶乘的函数。
函数接口定义:
void Print_Factorial ( const int N );
其中N
是用户传入的参数,其值不超过1000。如果N
是非负整数,则该函数必须在一行中打印出N
!的值,否则打印“Invalid input”。
裁判测试程序样例:
#include <stdio.h>int Factorial( const int N );int main()
{int N, NF;scanf("%d", &N);NF = Factorial(N);if (NF) printf("%d! = %d\n", N, NF);else printf("Invalid input\n");return 0;
}/* 你的代码将被嵌在这里 */
输入样例:
15
输出样例:
1307674368000
思路:这道题目的最后一个测试点是一个坑,要通过最后一个测试点就不能用普通的int、long long去存放计算出来的阶乘了,因为会越界!
我们的思路是用一个数组F[N]来存放阶乘(这里数组长度最小设置为N=2568,这个长度是我试出来的刚好能通过最后一个测试点的最小数组长度,多写点也无所谓)。存放的结构是低位在前,即F[0]存放的是个位,依此类推。
计算阶乘的时候我们用外层循环让i从2迭代到N,每次迭代给F"乘以"i。
这里的这个给数组"乘以"一个数,是用里层循环完成的,就按照我们小学学过的整数带进位的乘法。遍历从F[0]到F[N-1],比如遍历到某个F[j],我们要做的运算下面3步:
(1)给F[j]乘以外层循环当前的i,在加上F[j]前一项进位过来的值carry,然后把结果赋值给F[j],即F[j]=F[j]*i+carry;
(2)计算出要进位给下一位F[j+1]的值,carry = F[j]/10;
(3)F[j]只保留个位数字,F[j] = F[j]%10。
当里层循环遍历完,就像相当于给当前的阶乘F"乘以"外层循环当前的i,
当外层循环迭代完,F就存储了我们想要的阶乘了,只不过存储的结构是低位在前。
最后,我们要找到数组最后一个不为0的元素,从这个元素开始倒序输出数组即可。
代码:
void Print_Factorial ( const int N ) {int i, j, carry = 0;int M = 2568, F[2568] = {1}; // 初始化一个长度为2568的数组,为什么是2568呢?因为刚好能通过最后一个测试点。比2568长,是可以的。if (N < 0) {printf("Invalid input");return;} else if (N == 0) {printf("1");return;} else if (N > 0) {for (i = 2; i <= N; i++) { // 用数组F来存放每次迭代算出来的阶乘,存放时低位在前,即F[0]存放的是个位,依此类推。for (j = 0; j < M; j++) { // 乘的时候,用for循环对数组F的每个元素进行处理,计算的原则就是带进位的乘法。F[j] = F[j]*i+carry;carry = F[j]/10;F[j] = F[j]%10;}}for (i = M-1; i >= 0; i--) {if (F[i] != 0) {break;}}for (j = i; j >= 0; j--) {printf("%d",F[j]);}return;}
}