面试中遇到的阶层问题1000！

 

根据阶乘的定义和它满足的递归关系，我们很容易得到这样的算法：

publicstaticlong Calculate(int n)
{
if (n < 0) { thrownew ArgumentOutOfRangeException("n必须为非负数。"); }
if (n == 0) { return 1; }

return n * Calculate(n - 1);
}

随着n的增大，n!会迅速增大，其速度可能会超出你的想象。如果n不大，这种算法还可以，但对long类型来说，很快就会溢出。对计算器来说，大多数可以计算到69!，因为70! > 10¹⁰⁰。

上面这种累积相乘的算法的主要问题在于普通类型所容纳的数值太小，即使是double类型，它的最大值不过是1.79769313486232e308，即一个309位的数字。

我们来考虑另外一种方案，将乘积的每一位数字都存放在数组中，这样的话一个长度为10000的数组可以存放任何一个10000位以内的数字。

假设数组为uint[] array = new uint[10000]，因为1! = 1，所以首先置a[0] = 1，分别乘以2、3，得到3! = 6，此时仍只需要一个元素a[0]；然后乘以4得到24，我们把个位数4放在a[0]，十位数2放在a[1]，这样存放结果就需要两个元素；乘以5的时候，我们可以这样进行：用5与各元素由低到高逐一相乘，先计算个位数（a[0]）4 × 5，结果为20，这样将a[0]置为0，注意要将2进到十位数，然后计算原来的十位数（a[1]）2 × 5，结果为10加上刚才进的2 为12，这样十位数是2，而1则进到百位，这样就得到5! = 120；以此类推……

下面给出上述方案的一个实现：

publicstaticuint[] CalculateLargeNumber(int n)
{
if (n < 0) { thrownew ArgumentOutOfRangeException("n必须为非负数。"); }
if (n == 0 || n == 1) { returnnewuint[] { 1 }; }

// 数组的最大长度
constint MaxLength = 100000;
uint[] array = newuint[MaxLength];
// = 1
    array[0] = 1;

int i = 0;
int j = 0;
// = 120，此时valid = 3）
int valid = 1;
for (i = 2; i <= n; i++)
    {
long carry = 0;
for (j = 0; j < valid; j++)
        {
long multipleResult = array[j] * i + carry;
// 计算当前位的数值
            array[j] = (uint)(multipleResult % 10);
// 计算进到高位的数值
            carry = multipleResult / 10;
        }
// 为更高位赋值
while (carry != 0)
        {
            array[valid++] = (uint)(carry % 10);
            carry /= 10;
        }
    }

// 截取有效元素
uint[] result = newuint[valid];
    Array.Copy(array, result, valid);

return result;
}

用这个方法可以得出70!是101位（1.1979 × 10¹⁰⁰），450!是1001位，而1000!有2568位。需要注意的是，结果数的最高位存放在数组的索引最大的元素中，所以打印结果时要按正确的顺序。

曾经的一道面试题

我去年在某公司面试的时候曾经遇到这样的一个面试题：100!的后面会带多少个0？

这个问题该怎么分析呢？先找简单的情况来看，5! = 120，后面带着一个0，这个0是怎么产生的？1×2×3×4×5，应该是4×5产生的，而4 = 2×2，我们应该看到如果乘积的因子中包含2和5，就会产生在结尾的0。根据数论知识，我们知道任何大于1的整数都可以分解为若干个素数的乘积，那么如果我们把一个阶乘按此分解，其形式必然是2^a×5^b×p₁^a1...p_n^an，这样可以得到0的个数为Min(a, b)。这样我们就可以知道面试题的答案了。不过我们再深入看一下。

根据上面的分析，问题可以转化为阶乘分解后包含多少个2和5的因子。直觉告诉我，5的个数一定会少于2的个数，如果能证明这个，那么结论是：0的个数就是因子5的个数。

假设函数F2(n!)表示n!所包含的因子2的个数，可以证明F2((2n)!) = F2(n!) + n，比如当n = 2时，F2(2!) = 1，F2(4!) = 1 + 2 = 3。令n = 2^t，可以得到F2(2^t+1!) = F2(2^t!) + 2^t，再根据数学归纳法，可以得到结论：F2(2ⁿ!) = 2ⁿ - 1。

类似地，假设函数F5(n!)表示n!所包含的因子5的个数，可以证明F5(5ⁿ!) = (5ⁿ - 1)/(5 - 1)。有了这两个结论，我们可以进一步确定：F5(n!) <= F2(n!)。（证明过程略，仍使用数学归纳法）

那么结论便是：0的个数就是因子5的个数。F5(5!) = 1，所以5!带1个0，即120；F5(10!) = 2，所以10!带2个0，即3,628,800。