UVA OJ 623 500!
500! |
In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm.
As an examples we can give programs which calculate primary numbers.
One can also imagine a program which calculates a factorial of given numbers. In this case it is the time complexity of order O(n) which makes troubles, but the memory requirements. Considering the fact that 500! gives 1135-digit number no standard, neither integer nor floating, data type is applicable here.
Your task is to write a programs which calculates a factorial of a given number.
Assumptions: Value of a number ``n" which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a small limit).
Input
Any number of lines, each containing value ``n" for which you should provide value of n!
Output
2 lines for each input case. First should contain value ``n" followed by character `!'. The second should contain calculated value n!.
Sample Input
10
30
50
100
Sample Output
10!
3628800
30!
265252859812191058636308480000000
50!
30414093201713378043612608166064768844377641568960512000000000000
100!
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
算法竞赛入门经典上的解法如下:会超时。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 3000;
int a[maxn];
int main()
{
int n;
int i, j;
int c, s;
while (scanf("%d", &n) == 1)
{ memset(a,0,sizeof(a));
a[0] = 1;
for (i = 2; i <= n; i++)
{
c = 0;
for (j = 0; j < maxn; j++)
{
s = a[j] * i + c;
a[j] = s % 10;
c = s/10;
}
}
for (i = maxn; i >= 0;i--)
if (a[i])
break;
printf("%d!\n",n);
for (j = i; j >= 0; j--)
printf("%d",a[j]);
printf("\n");
} return 0;
}
修改后如下:
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500;
int a[maxn];
int main()
{
int n;
int i, j;
int len;
int c, s;
while (scanf("%d", &n) == 1)
{ memset(a, 0, sizeof(a));
a[0] = 1;
len = 1;
for (i = 2; i <= n; i++)
{
c = 0;
for (j = 0; j < len; j++)
{
s = a[j] * i + c;
a[j] = s % 1000000;
c = s / 1000000;
}
if (c)
a[len++] = c;
}
printf("%d!\n", n);
printf("%d",a[len-1]);
for (j = len-2; j >= 0; j--)
printf("%06d", a[j]);
printf("\n");
} return 0;
}
最新文章
- 谁是2016年的.NET开发者?
- LayaAir引擎——(三)
- java.lang.ClassNotFoundException: oracle.jdbc.driver.OracleDriver 错误的解决办法
- Bash实用技巧:同时循环两个列表
- HTML5 Canvas核心技术—图形、动画与游戏开发.pdf8
- js 终止页面加载
- ecshop各个文件夹作用
- hdu4336压缩率大方的状态DP
- how tomcat works 读书笔记 十一 StandWrapper 上
- [官网]Windows modules
- C++多态、虚函数、纯虚函数、抽象类、虚基类
- 使用datagrip链接mysql数据库的报错问题.
- U盘文件被隐藏
- 在n个数字中求为k的和————Java
- python 正则表达提取方法 (提取不来的信息print不出来 加个输出type 再print信息即可)
- Kylin介绍,功能特点【转】
- webpack提取库
- /etc/sysconfig/network-scripts/下文件介绍
- [AWS vs Azure] 云计算里AWS和Azure的探究(2)
- Git项目协同开发学习笔记2:项目库开发协作相关命令