来自"Slyar Home"的最新文章,如果您不希望再收到此邮件,请退订;如果您需要更换其它邮箱接收邮件,请点击这里!
任意位数的高精度阶乘算法 C语言版
Fri, 03 Oct 2008 23:32:34 +0800
文章作者: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。
代码如下:
#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;
}
您可以直接回复此邮件与作者联系,该服务由Feedsky提供技术支持,祝您使用愉快