较大的整数阶乘

分手后的思念是犯贱 2022-09-11 04:13 162阅读 0赞

## 思路： ##

考虑将多位数相乘化解为一位数相乘。

*  例如，11 的阶乘为 39916800，
 *  若需要求 12 的阶乘，则需要将 39916800 与 12 相乘，
 *  按手工计算乘法的竖式方法，可用 2 与 39916800 相乘的结果加上用 1 与 39916800 相乘的结果，然后再将结果相加，得到 12 的阶乘。

--------------------

## AC： ##

#include <stdio.h>
    #include <math.h>
    #include <stdlib.h>
    void carry(int bit[],int pos){ 
        int i,carray=0;
        for(i=0;i<=pos;i++){ 
            bit[i]+=carray;
            if(bit[i]<=9)
                carray=0;
            else if(bit[i]>9&&i<pos){ 
                carray=bit[i]/10;
                bit[i]=bit[i]%10;
            }
            else if(bit[i]>9&&i>=pos){ 
                while(bit[i]>9){ 
                    carray=bit[i]/10;
                    bit[i]=bit[i]%10;
                    i++;
                    bit[i]=carray;
                }
            }
        }
    }
    int main(){ 
        int num,pos,digit,i,j,m,n;
        double sum=0;
        int *fact;
        printf("输入计算其阶乘的数：Num= ");
        scanf("%d",&num);
        for(i=1;i<=num;i++)
            sum+=log10(i);
        digit=(int)sum+1;
        if(!(fact=(int *)malloc((digit+1)*sizeof(int)))){ 
            printf("分配内存失败！\n");
            return 0;
        }
        for(i=0;i<=digit;i++)
            fact[i]=0;
        fact[0]=1;
        for(i=2;i<=num;i++){ 
            for(j=digit;j>=0;j--)
                if(fact[j]!=0){ 
                    pos=j;
                    break;
                }
            for(j=0;j<=pos;j++)
                fact[j]*=i;
            carry(fact,pos);
        }
        for(j=digit;j>=0;j--)
            if(fact[j]!=0){ 
                pos=j;
                break;
            }
        m=0;
        n=0;
        printf("\n输出%d的阶乘结果（按任意键显示下一屏）:\n",num);
        m=2-pos%3;
        for(i=pos;i>=0;i--){ 
            printf("%d",fact[i]);
            m++;
            if(m%3==0)
                printf(" ");
            if(m==40){ 
                printf("\n");
                m=0;
                n++;
                if(n==10){ 
                    getchar();
                    printf("\n");
                    n=0;
                }
            }
        }
        printf("\n\n");
        printf("%d 的阶乘共有 %d位。\n",num,pos+1);
        getchar();
        return 0;
    }

--------------------