c# - 阶乘函数 - 设计和测试

Question

我想确定一些面试问题，所以我盯着一个简单的问题看。

设计阶乘函数。

这个函数是一个叶子(没有依赖性——易于测试)，所以我在帮助类中将它设为静态。

public static class MathHelper
{
    public static int Factorial(int n)
    {
        Debug.Assert(n >= 0);
        if (n < 0)
        {
            throw new ArgumentException("n cannot be lower that 0");
        }

        Debug.Assert(n <= 12);
        if (n > 12)
        {
            throw new OverflowException("Overflow occurs above 12 factorial");
        }

        int factorialOfN = 1;
        for (int i = 1; i <= n; ++i)
        {
            //checked
            //{
                factorialOfN *= i;   
            //}
        }
        return factorialOfN;
    }
}

测试:

    [TestMethod]
    [ExpectedException(typeof(OverflowException))]
    public void Overflow()
    {
      int temp = FactorialHelper.MathHelper.Factorial(40);
    }

    [TestMethod]
    public void ZeroTest()
    {
        int factorialOfZero = FactorialHelper.MathHelper.Factorial(0);
        Assert.AreEqual(1, factorialOfZero);
    }

    [TestMethod]
    public void FactorialOf5()
    {
       int factOf5 = FactorialHelper.MathHelper.Factorial(5);
       Assert.AreEqual(5*4*3*2*1,factOf5);
    }

    [TestMethod]
    [ExpectedException(typeof(ArgumentException))]
    public void NegativeTest()
    {
        int factOfMinus5 = FactorialHelper.MathHelper.Factorial(-5);
    }

我有几个问题:

1. 是否正确？ (我希望如此；))
2. 它会抛出正确的异常吗？
3. 我应该使用 checked 上下文还是这个技巧 ( n > 12 ) 可以？
4. 使用 uint isteast 是否比检查负值更好？
5. future 的改进:重载 long、decimal、BigInteger 或泛型方法？

谢谢

Answer 1

它在我看来是正确的，但如果数字较大，效率会很低。如果你允许大整数，数字将随着每次乘法而不断增长，所以如果你将它们分层相乘，你会看到速度的巨大(渐近更好)增加。例如:

bigint myFactorial(uint first, uint last)
{
    if (first == last) return first;
    uint mid = first + (last - first)/2;
    return myFactorial(first,mid) * myFactorial(1+mid,last);
}
bigint factorial(uint n)
{
    return myFactorial(2,n);
}

如果你真的想要一个快速的阶乘方法，你也可以考虑这样的事情:

1. 使用改进的埃拉托色尼筛法分解阶乘
2. 使用快速求幂算法(以及快速乘法和平方算法)计算每个质因数的幂
3. 分层将质数的所有幂相乘