您的位置：程序门 -> c/c++ -> c++ 语言

大数据n！（n的阶乘)计算方法讨论

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

大数据n！（n的阶乘)计算方法讨论[已结贴,结贴人:yuhan_0110]

发表于：2007-10-16 16:41:16 楼主

如题，以下是我找到的两种方法。

#include <stdio.h>
#include <time.h>
void main（)
{
int n = 10000;
int a[50000] = {0};
a[0] = 1; //用数组的一项存放计算结果的位数
a[1] = 1; //将第一项赋值为一

//计算
clock_t time_begin = clock（);
for（int j= 2; j <=n; j++)
{
int c = 0; //c表示向高位的进位
for（int i=1; i <=a[0]; i++)
{
a[i] = a[i] * j + c;//将来自低位的计算结果和本位的结果相加
if（ c=a[i]/10 )
{
a[i] = a[i] % 10;
}
}

for（; c != 0; i++)
{
a[i] = c%10;
c = c / 10;
}
a[0] = i - 1;
}
clock_t runtime = clock（)-time_begin;
printf（"runtime:%ld\n",runtime);

//输出
printf（"位数=%d\n",a[0]);

printf（"值=");
for（int x=1; x <=a[0]; x++)
{
printf（"%d",a[a[0]-x+1]);
}
printf（"\n");
}

#include <stdio.h>
#include <time.h>
int main（int argc, char *argv[])
{
long n=10000;

long a[4*10000] = {0};
a[0]=1;

long i,j,c,temp,len;
temp=0;
len=1;

//计算
clock_t time_begin = clock（);
for（i=1; i <=n; i++)
{
c=0;
for（j=0;j <len;j++)
{
temp=a[j]*i+c;
c=temp/100000;
a[j]=temp%100000;
}
while（c> 0)
{
len=len+1;
a[len-1]=c;
c/=100000;
a[len-1]%=100000;
}
}
clock_t runtime = clock（)-time_begin;
printf（"runtime:%ld\n",runtime);

//输出
printf（"%ld",a[len-1]);
for（i=len-2;i> =0;i--)
printf（"%05ld",a[i]);
return 0;
}

这两种的运行效率相差较大，大家还有更好的方法吗？

发表于：2007-10-16 16:47:211楼得分:0

在同一个机子上测试：第一种运行时间：7000；第二种运行时间：1200。

发表于：2007-10-16 16:53:452楼得分:10

发表于：2007-10-16 17:08:523楼得分:10

第一个用的是10进制来模拟,第二种是10w进制来模拟.
次数比第一次少了n多次,所以速度快

其他资讯