文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
今天就研究这个"任意位数的高精度阶乘算法"了，通过和大三的一个学长讨论，最终写出了这个还比较满意的算法：
1、利用C语言的动态数组来达到任意位数，但是首先需要知道数组的长度，也就是N!有多少位。
2、求出N!的结果有多少位，这个公式我就不证明了，是log10(1)+log10(2)+···+log10(n) 取整加1。
3、使用万进制来进位，减少空间的利用，提高运算速度。
4、高精度阶乘算法。
5、因为使用万进制，所以输出各位的时候需要补0。
6、最后发现如果N<1000的话结果的首位会出现0，因此单独输出第一位保证首位没有0。
代码如下：
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <stdio.h> #include <math.h> #include <stdlib.h> /* 求N!的位数公式 log10(1)+log10(2)+···+log10(n) 取整加1 */ int wei(int n) { int i; double sum=0; for(i=1;i<=n;i++) sum+=log10((double)i); /* 以万为进制，一位可以表示4个数，减少存储空间 */ return (int)((sum+1)/4+1); } /* 高精度阶乘核心 */ int main() { int i,j,n,jinwei,weishu=1,temp; unsigned int *x; scanf("%d",&n); /* 依据阶乘位数申请动态数组 */ x=(unsigned int*) malloc(wei(n)*sizeof(int)); x[0]=1; for(i=2;i<=n;i++) { jinwei=0; for(j=1;j<=weishu;j++) { temp=x[j-1]*i+jinwei; if (temp>=1) { /* 以万为进制，提高运算速度 */ x[j-1]=temp%10000; jinwei=temp/10000; } } while(jinwei) { weishu++; x[weishu-1]=jinwei%10000; jinwei/=10000; } } /* 先输出第一个数，防止首位出现0 */ printf("%d",x[weishu-1]); /* 输出其余的数，因为万进制，需要补0 */ for(j=weishu-2;j>=0;j--) printf("%04d",x[j]); /* 释放申请的内存 */ free(x); system("pause"); return 0; } |
转载请注明：Slyar Home » 任意位数的高精度阶乘算法 C语言版
