大数，高精度计算---大数阶乘

秒速五厘米 2021-11-26 13:08 387阅读 0赞

**大数是算法语言中的数据类型无法表示的数，其位数超过最大数据类型所能表示的范围，所以，在处理大数问题时首先要考虑的是怎样存储大数，然后是在这种存储方式下其处理的实现方法。**

**一般情况下大数的存储是采用字符数组来存储，即将大数当作一个字符串来存储，而对其处理是按其处理规则在数组中模拟实现。**

# 六 大数阶乘。 #

阶乘问题比较典型，下面，将通过自己的学习逐步介绍。

首先介绍两种常规方法。

## 1.迭代法 ##

/* 利用 迭代 来计算整数n的阶乘 */ 
    #include <stdio.h>
    int main()
    {
        int n;
        long result = 1;
        scanf("%d",&n);
        while( n>1 )
        {
            result *=n;
            n--;
        }
        printf("%ld",result);
        return 0;
    }

## 2.递归法 ##

/* 利用 递归 来计算整数n的阶乘 */
    #include <stdio.h>
    long factorial_recursion( int n )
    {
        if( n<=0 )
        {
            return 1;
        }
        else
        {
            return n * factorial_recursion( n-1 );
        }
    }
    int main()
    {
        int n;
        long result;
        scanf("%d",&n);
        result = factorial_recursion( n );
        printf("%ld",result);
        return 0;
    }

这两种方法都比较常规，也比较简单，初学c的时候，还没接触算法，就是利用这样的思路完成。

但是，一旦求N!中N的值大了，那么不管是int 还是 long 都无法满足。这时候就涉及到大数处理的问题上了。

下面介绍常规的大数阶乘。

## 3.利用数组存结果。 ##

#include <stdio.h>
    int main()
    {
        int n;
        int a[9000]; //确保保存最终运算结果的数组足够大
         int digit = 1; //位数
         int temp;   //阶乘的任一元素与临时结果的某位的乘积结果
         int i, j, carry; //carry：进位
    
         printf("please in put n:\n");
        scanf("%d",&n);
        a[0] = 1;   //将结果先初始化为1
    
        for ( i=2; i<=n; i++ )  //开始阶乘，阶乘元素从2开始依次"登场"
        {  //按最基本的乘法运算思想来考虑，将临时结果的每位与阶乘元素相乘
             for( j=1, carry=0;  j<=digit; j++ )
            {
                temp = a[j-1] * i + carry; //相应阶乘中的一项与当前所得临时结果的某位相乘（加上进位）
                  a[j-1] = temp % 10; //更新临时结果的位上信息
                  carry = temp / 10; //看是否有进位
             }
            while(carry)
            {    //如果有进位
                  a[++digit-1] = carry % 10; //新加一位，添加信息。位数增1
                carry = carry / 10; //看还能不能进位
             }
        }
        printf("n ! = ");    //显示结果
        for(j = digit; j >=1;j--)
        {
            printf("%d",a[j-1]);
        }
        printf("\n");
        return 0;
    }

这种大数阶乘算法也比较常规，目前水平能看懂。

具体思路代码中的注释也比较详细，就不重复了。 还是模拟笔算的过程。

下面附带两个大牛的算法 ， 虽然现在还看不懂，但是先mark一下。以后慢慢琢磨。

## 4. 大牛算法一 ##

出处 ： [ http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152430.html][http_www.cnblogs.com_xianghang123_archive_2011_08_24_2152430.html]

#define N 400
    long a[8916]={1,0},n,i,c,len; 
    int main(void)  
    { 
        n=N; 
        for ( len=1;n>1; n--) 
        { 
            for (c=0,i=0; i<len;i++ ) 
            { 
                a[i]= ( c+= a[i]*n ) % 10000; c/=10000; 
            } 
             
            ((a[i]=c)>0)?len++:0; 
    
        }    
        for( len--,printf("%d",a[len--]);len>=0; len--) printf("%04d",a[len]); 
             
        return 0; 
    }

【解释】

for ( len=1;n>1; n--) //把len的长度初始为1，因为数组中已经有一个元素了a\[0\]=1  
\{  
for (c=0,i=0; i<len;i++ ) //c初始为0，一开始还没运算哪来的进位，这是个内层循环，数组a中的len  
//个元素都必须参与运算，都必须\*n，这就是下面a\[i\]\*n的来由

\{  
a\[i\]= ( c+= a\[i\]\*n ) % 10; c/=10; //c是进位，不用说了，c+=a\[i\]\*n，a每个元素与n  
//相乘必须考虑低位是否有进位，有就加起来  
\}

((a\[i\]=c)>0)?len++:0; //最后一个元素也有进位吗，有的话就在当前的元素的下个数组位置直接等于进位值，并  
// 且数组的元素值 要加1,没有的话什么都不干 ,光一个0什么都不是  
  
\}

## 5.大牛算法二 ##

出处：[http://bbs.csdn.net/topics/390025206][http_bbs.csdn.net_topics_390025206]

int a[100000]={1},n,i,c,m=1;
    main()
    {
        scanf("%d",&n);
        for(;n;n--)
        {
            for(c=i=0;i<m||c;)
                a[i++]=(c+=a[i]*n)%10,c/=10;m=i;
        }
        for(;m;)
            putch(a[--m]+48);
    }

另外，网上关于大数阶乘的讨论也比较多。我也google了一些，学习后，感觉下面几个比较有意义。

还是先mark下。 便于以后温习。

[http://www.cnblogs.com/qlwy/archive/2012/07/18/2598028.html][http_www.cnblogs.com_qlwy_archive_2012_07_18_2598028.html]

[http://blog.csdn.net/hikaliv/article/details/4242988][http_blog.csdn.net_hikaliv_article_details_4242988]

[http://blog.csdn.net/yxnk/article/details/1665052][http_blog.csdn.net_yxnk_article_details_1665052]

[http_www.cnblogs.com_xianghang123_archive_2011_08_24_2152430.html]: http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152430.html
[http_bbs.csdn.net_topics_390025206]: http://bbs.csdn.net/topics/390025206
[http_www.cnblogs.com_qlwy_archive_2012_07_18_2598028.html]: http://www.cnblogs.com/qlwy/archive/2012/07/18/2598028.html
[http_blog.csdn.net_hikaliv_article_details_4242988]: http://blog.csdn.net/hikaliv/article/details/4242988
[http_blog.csdn.net_yxnk_article_details_1665052]: http://blog.csdn.net/yxnk/article/details/1665052