最新消息:点击查看大S的省钱秘笈

任意位数的高精度阶乘算法 C语言版

编程相关 Slyar 6298浏览 8评论

文章作者:姜南(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 
#include 
#include 

/* 求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语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (8)

  1. 好厉害,赞
    莘莘学子5年前 (2015-06-28)回复
  2. 其中的x[j-1]至少也是个四位数吧?那么其中的i呢?是不是从2~n,那么这个n可以是多少?它们相乘起来就没有溢出的可能性吗? 尤其是你的temp还是int类型的,嘿嘿!~
    一笑而过12年前 (2008-11-15)回复
  3. x[j-1]*i 而且还定义为int型,难道博主不怕会溢出的吗? 嘿嘿!~
    一笑而过12年前 (2008-11-14)回复
    • 那个怎么会溢出呢。。。
      Slyar12年前 (2008-11-14)回复
  4. 囧,wp怎么用了striptags? 应该用htmlspecialchars来处理标签会比较好阿。
    felix02112年前 (2008-10-06)回复
  5. 试试这个: #include vector ooxx; 还有 class maxMulti{ //...... friend inline maxMulti operator * (const maxMulti &a, const maxMulti &b){ //.... } };
    felix02112年前 (2008-10-06)回复
    • 呃。。。用到class的问题以后再议。。。
      Slyar12年前 (2008-10-06)回复
  6. 不错,学习了
    自然堂12年前 (2008-10-04)回复