1 题目描述
输入某一个自然数N，求N（0≤N≤10000）的阶乘即N!是多少。
1.1 输入
输入只有一个数N。
1.2 输出
输出N!的结果。
1.3 样例输入
3
1.4 样例输出
6
2 解题
2.1 数学基础
对于某一正整数N，肯定比高其一位的最小整数小，大于甚至等于同位数的最小整数，因此N满足以下关系：
其中x代表10的幂次，同时也有另外一层含义，即在10的x次方里有x个零。如果再加上最高位的1，x+1就代表了10的x次方的位数。同理，对于10的x-1次方，其位数为x-1+1=x位，x即为正整数N的位数。对以上不等式关系我们取10的对数可得：
即：
如果我们定义[k]所表示的为不超过k这个数的最大整数，便可得到：
我们在等式两边同时加1即可得到N与其位数x的关系：
转化为C++代码中的表示即为int x = (int)log10(N) + 1，特别地，使用log10()函数需要引入头文件<cmath>。
2.2 解决思路
题目中很明显指出了输入数N的取值范围，最大为10000。要让计算机求解10000阶乘级别的数值并且全部输出，这对精度和运算速度要求是十分苛刻的，采用常规的递归和循环解法绝对不行。一般来说，进行高精度的计算求解，必须要用到数组来存储各个位的数字，此外要得到精确数值的话可以使用模拟手工运算的算法。但模拟手工运算的算法是有时间瓶颈的，我们可以对此进行优化，不再使用十进制的进位方式，可以采用千进制、万进制的进位方式来减少多余的进位运算。经过测试，十万进制效果显著，因此代码里采用十万进制进位。
我们首先要确定最大数的阶乘即10000!的位数能够达到多少，经过编程计算，10000!的位数为35660，所以我们可以定义一个长度超过35660的数组来存储结果。由于阶乘的运算是递减型的，即10000!=10000×9999×...×1，只要在算法里采用“乘完就进位”的思想，那么对数组里每个元素来说，其值最大绝对不超过10000×10000，这对int类型的变量来说不会发生溢出，因此我们定义的数组类型为整型。
由于输入N的不同，位数也会随之变化，因此需要再定义一个double型数组来存储对数，以便后续的快速查找来计算得出位数。由对数知识：
可以采用循环来计算对数的值。
3 代码
#include <cstdio>
#include <cmath>
const int MAXN = 10000;
int N;
int ans[4*MAXN];
double lgn[10005];
//定义全局变量默认初始化为0。
int main()
{
scanf("%d",&N);
for(int i = 1; i <= 10000; ++i)
lgn[i] = lgn[i-1] + log10(i);
//lgn数组存储了0阶乘到10000阶乘的位数，以便快速查找
ans[0]=1; //数组最低位必须为1，以便后续进位
for(int i = 1; i <= N; ++i){
int x = (int)lgn[i] + 1;
for(int j = 0, carry_value = 0; j <= x / 5; ++j){
ans[j] = ans[j] * i + carry_value;
carry_value = ans[j] / 100000;
ans[j] %= 100000;
}
}
/*
采用100000进制的进位，对于100000进制的数，最大为99999，
因此数组里每个元素都能表示五位的数字，即x/5。在第二层循环
中为了减少多余的计算，每次循环乘数，循环次数和当前数值位数
正相关。
*/
int x = (int)lgn[N] + 1; //N阶乘的位数
for(x = x / 5; x >= 0; --x)
if(ans[x] != 0) break;
//剔除掉最高位数组元素为0的情况
printf("%d",ans[x]); //因为最高位数组元素表示的数字可能不足五位，所以直接输出
for(int i = x - 1; i >= 0; --i)
printf("%05d",ans[i]);
/*
在输出完最高位数组元素后，其后的元素如果不足五位代表不足
那几位的数字为0，使用%05d输出格式，输出五位不足五位补0到
五位
*/
printf("\n");
return 0;
}
网友评论