10000的阶乘-HDU1042
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;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-01-06，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读