另一种求大数阶乘的算法

忘是亡心i 2022-05-13 00:06 190阅读 0赞

大数阶乘

问题描述：编写程序，对给定的n(n <= 100),计算并输出k的阶乘k!的全部有效数字。

注意：如果要求一个5的阶乘，用整型可以存储，求10的阶乘可以用长整型表示，但若要求100的阶乘，就无法用长整型表示，此时就必须考虑别的方法。

要求的k!的值，必定已求得（k-1)!的值，依次地推，当 k = 2时，要求的1！ = 1为已知。求得(k-1)!的值后，对（k-1)!连续累加k-1此后即可求得K!值。

例如：5！= 120，计算6！,可对原来的120累加5次120后得到720.

由于k!可能大大超出一般整数的位数，因此程序用一个一维数组存储长整型，存储长整数数组的每个元素只存储长整数的一位数字。如有m位长整数N用数组a\[\]存储,并用a\[0\]存储长整数N的位数m，即a\[0\] = m。按上述约定，数组的每个元素存储k的阶乘k!的一位数字，并从低位到高位依次存于数组的第二个元素、第三个元素....

例如：6！ = 720，在数组中的存储形式为：

a\[0\] a\[1\] a\[2\] a\[3\]

30 2 7

a\[0\] = 3表示长整数是一个3位数，接着从低位到高位依次是0、2、7，表示成整数720.

程序实现：

/*
     *程序功能：计算任意位数的阶乘
     *作者Blog:http://blog.csdn.net/u012027907
     */
    #include <stdio.h>
    #include <malloc.h>
    #define MAXN 1000
    
    //已知a中的(k-1)!,求k!
    void PreNext(int a[],int k) 
    {
    	int *b,m = a[0],i,j,r,carry;
    	b = (int*)malloc(sizeof(int)*(m+1));
    	for(i = 1; i <= m; i++)  
    		b[i] = a[i];
    	for(j = 1; j < k; j++)   //控制累加k-1次
    	{
    		for(carry=0,i = 1;i <= m;i++)
    		{
    			r = (i <= a[0]?a[i]+b[i]:a[i])+carry; //计算加的结果
    			a[i] = r % 10; //计算本位结果
    			carry = r / 10; //计算进位数字
    		}
    		if(carry)  //向最高为进位
    			a[++m] = carry;
    	}
    	free(b);
    	a[0] = m;
    }
    void Print(int *a,int k)
    {
    	int i;
    	int m = 0;
    	for(i = a[0]; i >0; i--){
    		printf("%d",a[i]);
    		m++;
    		if(m % 5 == 0)             //每5个数字空一格   
                printf(" ");  
            if(40 == m)                //每行输出40个数字   
            {  
                printf("\n");  
                m = 0;          
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	int a[MAXN],n,k;
        n = 1;
    	printf("本程序计算任意位数的阶乘！\n");
    	
    	while(n){
    		printf("请输入一个数：");
    		scanf("%d",&n);
    		a[0] = a[1] = 1;
    		for(k = 2; k <= n; k++)
    		{
    			PreNext(a,k);		
    			if(k == n)
    				Print(a,k);
    		}
    	}
    }

运行截图：

![SouthEast][]

转载请标明出处：[http://blog.csdn.net/u012027907][http_blog.csdn.net_u012027907]

[SouthEast]: /images/20220513/3bbfea14baea4fd5930562b7c114e706.png
[http_blog.csdn.net_u012027907]: http://blog.csdn.net/u012027907