大数阶乘
发布时间:2020-12-14 02:29:12 所属栏目:大数据 来源:网络整理
导读:/*【分析】 为了保存结果,先分析1000!大约等于4×102567,因此可以用一个3000个元素的数组f保存。 让f[0]保存结果的个位,f[1]是十位,f[2]是百位,…,则每次只需要模似手算即可完成n!。 在输出时需要忽略前导0。 注意,如果结果本身就是0,那么忽略所有前
/*【分析】
为了保存结果,先分析1000!大约等于4×102567,因此可以用一个3000个元素的数组f保存。 让f[0]保存结果的个位,f[1]是十位,f[2]是百位,…,则每次只需要模似手算即可完成n!。 在输出时需要忽略前导0。 注意,如果结果本身就是0,那么忽略所有前导0后将什么都不输出。所幸n!肯定不等于0,因本题可以忽略这个细节。 */#include <stdio.h> #include <string.h> const int maxn = 3000; int f[maxn]; int main() { int i,j,n; scanf("%d",&n); memset(f,sizeof(f)); f[0] = 1; for(i = 2; i <= n; i++) { /* 乘以i */ int c = 0; for(j = 0; j < maxn; j++) { int s = f[j] * i + c; f[j] = s % 10; c = s / 10; } } for(j = maxn-1; j >= 0; j--) if(f[j]) break; /* 忽略前导0 */ for(i = j; i >= 0; i--) printf("%d",f[i]); printf("n"); return 0; } 这段代码: for(i = 2; i <= n; i++) { /* 乘以i */ int c = 0; for(j = 0; j < maxn; j++) { int s = f[j] * i + c; f[j] = s % 10; c = s / 10; } }实际上就是求阶乘的核心代码。由于计算机的字长有限,能表示的整数范围远远小于1000阶乘的结果。目前PC机通常是32位,只能表示最大4294967295的(无符号)整数。而15阶乘的结果就已经是:1307674368000,远远超过32位的表示范围,更不用说1000的阶乘了。因此,程序里采用整数数组的方式存储“超长整数”,以保持精度。程序里采用int f[]存储阶乘的结果。例如,15阶乘为1307674368000,采用int f[]表示为:f[0] = 0 f[1] = 0 f[2] = 0 f[3] = 8 f[4] = 6 f[5] = 3 f[5] = 4 f[5] = 7 f[5] = 6 f[5] = 7 f[5] = 0 f[5] = 3 f[5] = 1 程序里,f[j] = s % 10;c = s / 10; 就是模仿手工计算的方式,采用10进制,一位位计算,大于10就进到下一位。你自己手工演算一下就明白了。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |