Факторная функция - проектирование и тестирование

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. Должен ли я использовать флажок контекст или этот трюк (n> 12) в порядке?
4. Лучше ли использовать uint вместо проверки на отрицательные значения?
5. Будущее улучшение: перегрузка для длинных, десятичных, BigInteger или, возможно, универсального метода?

Спасибовы

Answer 1

1. Да, это выглядит правильно
2. Исключения кажутся мне нормальными, а также как интервьюер, я не вижу себя там обеспокоенным
3. Проверено.Кроме того, в интервью вы никогда не узнаете, что число 12 оказалось правильным.
4. Uint.Если вы можете применить что-то с помощью подписи вместо исключения, сделайте это.
5. Вы должны просто сделать это длинным (или bigint) и покончить с этим (int - глупый выбор типов возврата здесь)

Вот несколько дополнительных вопросов, которые я бы задал, если бы я был вашим интервьюером:

1. Почему вы не решили это рекурсивно?Факториал - это естественно рекурсивная проблема.
2. Можете ли вы добавить памятку к этому, чтобы он быстрее выполнял вычисления 12!если это уже сделано 11!?
3. Вам нужен случай n==0 здесь?

Как интервьюер, я бы определенно имел несколько подобных шариков, чтобы бросить в вас.В целом, мне нравится практиковаться с доской и издевательским интервьюером, потому что многое из этого - ловкость и мышление на ногах.

Answer 2

Это выглядит правильно для меня, но это было бы неэффективно с большими числами.Если вы допускаете большие целые числа, число будет расти с каждым умножением, поэтому вы увидите огромное (асимптотически лучшее) увеличение скорости, если вы умножите их иерархически.Например:

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. Умножить все степени простых чисел вместе иерархически

Answer 3

В цикле for вы можете начать с for (int i = 2 ...). Умножение на 1 совершенно бесполезно. Я бы бросил одну ArgumentOutOfRangeException для обоих <0 и> 12. Debug.Assert замаскирует исключение, когда вы используете свой модульный тест (вам придется тестировать его в режиме Release).