大数运算之大数阶乘

c/c++

浏览数:55

2019-8-9

阶乘会使得位数增长的非常快,比如20!的值的位数就已经要突破long long的上限了。所以常规的做法是处理不了的,要通过数组的方式来处理。当然这个数字本身不能超过int的范围,并且要提前预估这个数字的阶乘会有多少位。

以计算5的阶乘为例,来说明这个算法:

STEP1
初始化array[0] = 1

STEP2
从2开始乘,1*2 = 2,结果只有1位数,直接存到array[0]

STEP3
2*3 = 6,结果只有1位数,直接存到array[0]

STEP4
6*4 = 24,结果有2位数,2存到array[1],4存到array[0]

STEP5
24*4 = 120,结果有3位数,1存到array[2],2存到array[1],0存到array[0]

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define MAXLENGTH 50000
int main()
{
    int n;
    while(cin >> n)
    {
        int* array = NULL;
        array = (int*)malloc(MAXLENGTH*sizeof(int));
        if(!array)
        {
            cout << "malloc failed" << endl;
            break;  
        } 
        else
        {
            array[0] = 1;
            int digit = 1;//位数,随着计算不断更新 
            for(int i = 2;i <= n;i++)
            {
                int temp;
                int carry = 0;//进位 
                for(int j = 0;j < digit;j++)//将一个数每一位都乘以i 
                {
                    temp = array[j]*i+carry;
                    array[j] = temp%10;//将一个数的每一位拆开存放到数组的每一位 
                    carry = temp/10;
                }
                while(carry)
                {
                    array[digit] = carry%10;
                    carry /= 10;
                    digit++;
                }
            }
            while(digit >= 1) cout << array[--digit];//逆序输出 
            cout << endl;
        }
        free(array);
    }
    return 0;
} 
 

以上的代码计算10000的阶乘没有问题

作者:闽A2436