求N的阶乘

Description

用递归算法，求N！的精确值(N以一般整数输入,N<100)。

Input

输入一个整数n

Output

输出n！

Sample Input

10

Sample Output

10!=3628800

Solution

显然100数据规模的阶乘是无法用longlong存下的，所以我选择用数组来模拟大数乘法，具体代码实现是从社团那里学到的，这里附上我的理解：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>

#define MAX 10001
#define ll long long int
#define scf(a) scanf("%d", &a)
#define mms(a) memset(a, 0, sizeof(a))

using namespace std;

int num[100], endn = 0;

void Bignum(int n)
{
    if (n == 1) return;		//如果递归到1即阶乘结束

    int temp = 0;		//temp用来存每位数做乘法之后多出来的值
    for (int i = 0; i <= endn; i++)		//endn用来表示当前数组长度
    {
        num[i] = num[i] * n + temp;		//当前位数先与n做乘法并加上上一位进位的数temp
        temp = num[i] / 10;		//进位的temp是当前位数与n的乘积减去个位数（数组一个单元只存一位数）
        num[i] %= 10;		//将乘积的个位数存进数组中
    }
    while (temp)		//如果乘完了但是temp不为0，则还需要进位
    {
        num[++endn] = temp % 10;		//endn需要向后扩张以保存temp
        temp /= 10;			//temp需要一位一位的存进数组中
    }

    Bignum(n - 1);		//递归继续与n-1相乘
}

int main()
{
    int n;
    while (cin >> n)
    {
        mms(num);
        num[0] = 1;			//这里有个细节，数组的第一位需要初始化为1，否则结果将为0
        Bignum(n);

        printf("%d!=", n);
        for (int i = endn; i >= 0; i--)
            cout << num[i];		//逆向输出数组
        cout << endl;
    }
}

一开始发现long long不够用的时候，我第一反应也是用数组来模拟乘法，但是当时脑子里一直想的都是列竖式计算的时候的进位方法，也就是一位一位的去跟所有数乘，然后每次只会进一位。

在看了社团那边的代码之后才恍然大悟，可以每次直接用n去和数组的每一位数字相乘，多出来的数全部进位就好，不用顾忌“进位的数有好几位怎么办”这样愚蠢的问题。