Problem Description
Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
Input
One N in one line, process to the end of file.
Output
For each N, output N! in one line.
Sample Input
1
2
3
Sample Output
1
2
6
算法解读:
看似简单的问题,背后实际上有许多道理。
阶乘值随着n的增大,增大的速度相当的快,是一个大整数。似乎这个题可以使用大整数类进行计算,然而类计算相对复杂,时间上溢出的可能性比较大。一般的整数计算,在计算机中是一种相对比较快的运算。
用10000进制(万进制)来计算是一个有效的办法。10000进制的数可以放进数组中,每个元素放1位。人们通常使用10进制,采用逢10进1。采用10000进制的话,就是逢10000进1了。
为什么采用10000进制而不采用其他的进制?原因还是有几点的,一是计算结果输出时相对比较方便;二是digit_number比较小,遍历的次数也会少很多;三是C语言或C++语言的整数类型在不同的编译运行环境中,其值范围是不一样的,一般整数类型int至少是16位的,其值>30000,采用10000进制是一种保守的做法。
实际上,目前绝大多数计算机是64位的,使用更高的进制(例如100000000,亿进制)进行计算效率会更高。
这个题计算的是阶乘,只需要单一的乘法运算,计算逻辑并不复杂,对于10000进制逻辑实现上不是问题。
程序里的数组,下标小的放的是低位,下标大的放高位。
g++:264ms
#include <stdio.h>
/*计算n的阶乘函数*/
void factorial(int n)
{
/*这里初始化为1*/
static int num[10000 + 1];
num[0] = 1;
/*当前数字的位数*/
int digit_number = 1;
/*从2开始进行乘法运算*/
for (int i = 2; i <= n; i++)
{
/*是否进位*/
int carry = 0;
/*示例:
2583
x 35
将35与3、8、5、2依次进行乘法,每次乘之后计算进位
*/
for (int j = 0; j < digit_number; j++)
{
/*采用10000进制,每次乘的时候加上进位*/
num[j] = num[j] * i + carry;
/*取得进位*/
carry = num[j] / 10000;
/*计算j位的数值*/
num[j] %= 10000;
}
/*最高位的进位,如果进位了,则当前数字的位数digit_number+1*/
if (carry > 0)
num[digit_number++] = carry;
}
/*输出:高位原样输出,低位的高位补0*/
printf("%d", num[digit_number - 1]);
/*可以在纸上画一下10000进制转成10进制的输出*/
for (int i = digit_number - 2; i >= 0; i--)
printf("%04d", num[i]);
printf("\n");
}
int main()
{
int n;
/*输入,计算*/
while (~scanf("%d", &n))
factorial(n);
return 0;
}