1000的阶乘问题

问题引入

这些天看到了有关1000的阶乘的问题，决定对这个问题做一个整理，方便日后观看。1000的阶乘有以下几个问题值得探讨：

1. 1000的阶乘结果末尾有多少个0
2. 1000的阶乘的值有多少位
3. 1000的阶乘的精确值是多少

下面对这三个问题进行研讨，并会给出相关代码

1. 1000的阶乘结果后面有多少个0

1000个数每一个数都可以分解成几个质数的乘积，而能够产生0的最小的两个质数是2和5，所以我们只用知道1000里面有多少个5和多少个2，因为2的数量是远远多余5的，所以问题就变成了求解1000里面有多少个5。

1、首先5的个数是 1000/5 = 200；
2、如果分解成的质数有两个5，即包含55，这种结果要多出一个5，共 1000/25 = 40；(由于只有一个5的情况包含了一次有两个5的情况，所以这里只用算25的个数就行了，不用乘以2）
3、同理，对于555 共有 1000/125 = 8
4、对于5555 = 1000/625 = 1;

所以一共有 200+40+8+1 = 249个0；

2. 1000的阶乘有多少位

这个我们值需要一点点数学知识就行了，假设结果是M，把这个数变成科学计数法为0.M*10n次方，这里的n显然就是M的位数，也就是得到的结果的位数。

所以我们可以有1234…1000 = 0.M10n次方，两边同时取对数，即
lg(123*…*1000) = lg(0.M)+n
n =int(lg(1)+lg(2)+…+lg(1000)-lg(M)=lg(1)+lg(2)+…+lg(1000)+1)；
（因为n肯定是整数，而且-1<lg(0.M)<0,所以lg(0.M)只用取-1，然后把多余的会在int取整时去掉）
这里代码只用一个简单循环就行了。结果为2568

3. 1000的阶乘精确值是多少

因为1000的阶乘的值特别大，所以没有一种数据类型可以来存储，所以我们用数组来存储，将结果的低位放在数组的开头，高位放在末尾，对于1-1000每个数都遍历一次数组。然后进行乘法和进位的处理。

/*
 * 例如1*2*3*4=24 那么数组中a[0]=4 a[1]=2   //将大数倒序装进数组
 * 24*5 = 120  那么就是a[0]*5 = 20 a[1]*5=10  //每一位只能是0-9
 * 所以需要进位  那么就是a[0]=20%10=0 
 * a[1]=a[1]+a[0]/10=12 
 * a[1] = a[1]%10=2  
 * a[2] = a[2]+a[1]/10 =1  
 * 就变成120了  
 * 关键在于对进位的控制
 */

代码：

#include <iostream>
#include <cmath>

const int EXT = 5;

//求数组的长度
int length(int n)
{
    double m = 0;
    for (int i = 1; i <= n; ++i)
    {
        m += log(i);
    }
    return int(m + 1);
}
//计算值
void fact(int n)
{
    //------n<=0---------
    if (n < 0)
    {
        std::cout << "error\n";
        return;
    }
    else if (0 == n)
    {
        std::cout << 1;
        return;
    }

    //---------construct--------------
    int len = length(n) + EXT;
    short *num = new short[len];
    short carry, sum;

    //----------init-------------
    for (int i = 0; i < len; ++i)
    {
        num[i] = 0;
    }
    num[0] = 1;

    //---------calc---------
    for (int i = 2; i <= n; ++i)
    {
        carry = 0;
        for (int j = 0; j < len; ++j)
        {
            sum = num[j] * i + carry;
            num[j] = sum % 10;
            carry = sum / 10;
        }
    }
    //-----------end------------

    //-----------output----------
    bool zero = true;
    for (int i = len - 1; i >= 0; --i)
    {
        if (zero)
        {
            if (0 != num[i - 1])
            {
                zero = false;
            }
        }
        else
        {
            std::cout << num[i];
        }
    }

    //-----------destruct-----------
    delete[] num;
}

int main()
{
    fact(1000);
    return 0;
}

第二种方法：使用vector动态添加。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<int> nums;

int len(int num)
{
    int len = 0;
    while (num)
    {
        num /= 10;
        len++;
    }
    return len;
}

void cal(int n)
{
    int carry;
    nums.push_back(1);
    for (int k = 2; k <= n; ++k)
    {
        carry = 0;
        for (int &num : nums)
        {
            num = num * k + carry;
            carry = (num / 10);
            num = (num % 10);
        }
        if (carry != 0)
        {
            int mod = 0;
            for (int i = 0; i < len(carry); ++i)
            {
                mod = (carry / int(pow(10, i))) % 10;
                nums.push_back(mod);
            }
        }
    }

    for (int i = nums.size() - 1; i >= 0; i--)
    {
        cout << nums[i];
    }
}
int main()
{
    cal(1000);
    return 0;
}

结果：