Written by razrlele
14:53 August 4, 2014
《算法竞赛入门经典》（刘汝佳） 5.2.2 阶乘的精确值：输入不超过1000的正整数n。输出n!=1234...n的精确结果。
这个代码粗略地介绍了一下大数运算的实现，主要是用数组来存储位数，估计gmp函数库原理跟这个差不多。
为了保存结果，需要先分析1000！有多大。用计算器一算可以看出约等于4*10^2567，这样的话用一个3000个元素的数组f保存即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/************************************************************************* > File Name: bignum.c > Author: razrLeLe > Personal homepage: https://razrLeLe.com > Created Time: Mon 04 Aug 2014 08:58:52 AM CST ************************************************************************/ #include<stdio.h> #include<string.h> const int maxn = 3000; int f[maxn]; int main() { int i,j, n; scanf("%d", &n); memset(f, 0, sizeof(f)); f[0] = 1; for(i = 2; i <= n; i++) { int c = 0; for(j = 0; j < maxn; j++) { int s = f[j] * i + c; //这个地方就是模拟手算，手算就是比如说算1234*23的时候，先是4*23，再是3*23，再试2*23，再试1*23，其中进位都有保存 f[j] = s % 10; c = s/ 10; } } for(j = maxn-1; j >= 0; j--) if(f[j]) break; //输出的时候没有用到的零位就直接跳过 for(i = j; i >= 0; i--) printf("%d", f[i]); printf("n"); return 0; } |