首页 > 代码库 > 求n的阶乘的精确值

求n的阶乘的精确值

2024-08-05 12:08:46   222人阅读


斯特林公式可以求出n！的近似值，但是如果需要求精确值的话，就要采取另外的办法了。‘

当n<=1000的时候，可以直接模拟求阶乘，用一个数组保存阶乘的每一位，大概3000的数组就行。程序如下：

#include<stdio.h>
#include<string.h>
#define N 3000
int f[N];//保存阶乘的位数
int main()
{
    int n,i,j,c;
    while(~scanf("%d",&n))
    {
        memset(f,0,sizeof(f));
        f[0]=1;  //f[0] 必须初始为1
        for(i=2;i<=n;i++)
        {
            c=0; //进位
            for(j=0;j<N;j++)
            {
                f[j]=f[j]*i+c;
                c=f[j]/10;
                f[j]=f[j]%10;
            }
        }
        for(i=N-1;i>=0;i--) if(f[i]) break; //忽略前导0
        for(j=i;j>=0;j--) printf("%d",f[j]);
        printf("\n");
    }
    return 0;
}

但是当n太大的时候，比如10000，上述算法会超时，所以 还可以采用一种万进位的方法，就是数组中的每一个数都保存4位数，超过四位数才进位，形式跟上面类似，但是减少了循环次数，节省时间。

#include<stdio.h>
#include<string.h>
#define N 10000
int f[N]; //每一个数保存阶乘中的四位数
int main()
{
    int n,i,j,p,c; //p表示已经用了数组的几个数  c是进位
    while(~scanf("%d",&n))
    {
        memset(f,0,sizeof(f));
        f[0]=1;
        p=1;
        for(i=2;i<=n;i++)
        {
            c=0;
            for(j=0;j<p;j++)
            {
                f[j]=f[j]*i+c;
                c=f[j]/N;
                f[j]=f[j]%N;
            }
            if(c)
            {
                p++;
                f[p-1]+=c;
            }
        }
        printf("%d",f[p-1]);
        for(i=p-2;i>=0;i--)
            printf("%04d",f[i]);  //不足4位前面补0 
        printf("\n");
    }
    return 0;
}



求n的阶乘的精确值


联系
我们