主题:[讨论]关于大整数存储及运算的问题
题目:编程求当N<=100时,求N!的准确值。
算法设计:乘法的结果是按由低位到高位存储在数组a中,由于计算结果位数可能很多,若存储结果的数组每个存储空间只存储一位数字,对每一位进行累乘次数太多。所以将数组定义为长整型,每个元素存储结果的6位数字。
一个高精度数据与一个自然数的乘法运算,比较简单的方法就是高精度数据按元素与自然数相乘。用二重循环来实现,其中一个循环变量i代表要累乘的数据,循环变量j代表当前累乘结果的数组下标。数据b存储计算的中间结果,d存储超过6位数后的进位,数组a存储每次累乘的结果,每个元素存储6位数据。
main()
{ long a[256],b,d;
int m,n,i,j,r;
input(n);
[color=FF0000]m=log(n)*n/6+2;[/color]
a[1]=1;
for(i=2;i<=m;i=i+1)
a[i]=0;
d=0;
[color=FF0000]for(i=2;i<=n;i=i+1)
{for(j=1;j<=m;j=j+1)
{b=a[j]*i+d;
a[j]=b mod 1000000;
d=b/1000000;}
if(d<>0)
a[j]=d;
}[/color]
for(i=m;i>=1;i=i-1)
if(a[i]=0)
continue;
else
{
r=i;
break;
}
print(n,"!=");
print(a[r]," ");
for(i=r-1;i>=1;i=i-1)
{
if(a[i]>99999)
{print(a[i]," ");
continue;}
if(a[i]>9999)
{print("0",a[i]," ");
continue;}
if(a[i]>999)
{print("00",a[i]," ");
continue;}
if(a[i]>99)
{print("000",a[i]," ");
continue;}
if(a[i]>9)
{print("0000",a[i]," ");
continue;}
print("00000",a[i]," ");
}
}
请高手解释红色字体部分的功能。
算法设计:乘法的结果是按由低位到高位存储在数组a中,由于计算结果位数可能很多,若存储结果的数组每个存储空间只存储一位数字,对每一位进行累乘次数太多。所以将数组定义为长整型,每个元素存储结果的6位数字。
一个高精度数据与一个自然数的乘法运算,比较简单的方法就是高精度数据按元素与自然数相乘。用二重循环来实现,其中一个循环变量i代表要累乘的数据,循环变量j代表当前累乘结果的数组下标。数据b存储计算的中间结果,d存储超过6位数后的进位,数组a存储每次累乘的结果,每个元素存储6位数据。
main()
{ long a[256],b,d;
int m,n,i,j,r;
input(n);
[color=FF0000]m=log(n)*n/6+2;[/color]
a[1]=1;
for(i=2;i<=m;i=i+1)
a[i]=0;
d=0;
[color=FF0000]for(i=2;i<=n;i=i+1)
{for(j=1;j<=m;j=j+1)
{b=a[j]*i+d;
a[j]=b mod 1000000;
d=b/1000000;}
if(d<>0)
a[j]=d;
}[/color]
for(i=m;i>=1;i=i-1)
if(a[i]=0)
continue;
else
{
r=i;
break;
}
print(n,"!=");
print(a[r]," ");
for(i=r-1;i>=1;i=i-1)
{
if(a[i]>99999)
{print(a[i]," ");
continue;}
if(a[i]>9999)
{print("0",a[i]," ");
continue;}
if(a[i]>999)
{print("00",a[i]," ");
continue;}
if(a[i]>99)
{print("000",a[i]," ");
continue;}
if(a[i]>9)
{print("0000",a[i]," ");
continue;}
print("00000",a[i]," ");
}
}
请高手解释红色字体部分的功能。