Решение проблемы Эйлера проекта 1 с использованием методов расширения

Как разработчик, я никогда не делал проблем с Project Euler, поэтому решил начать с проблемы 1, в которой говорится

  

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, получим 3, 5, 6 и 9. Сумма этих кратных значений равна 23.

     

Найдите сумму всех кратных 3 или 5 ниже 1000.

Первым шагом было создание метода расширения, который принимает lowerLimit и upperLimit возвращает IEnumerable<int>

public static IEnumerable<int> GetSequence(this int lowerLimit, int upperLimit)
{
    if (upperLimit < lowerLimit) { throw new ArgumentOutOfRangeException("lowerLimit needs to be less or equal to upperLimit"); }

    for (int i = lowerLimit; i < upperLimit; i++)
    {
        yield return i;
    }
}

, который можно вызвать, например, так

int lowerLimit = 1;
var sequence = lowerLimit.GetSequence(1000);  

Я не уверен на 100% относительно имени этого метода, но не мог найти альтернативное имя, поэтому я хотел бы услышать предложения для этого.

Мясо о решении проблемы

public static class SolverOfProblemOne
{
    public static int Solve(this int lowerLimit, int upperLimit, params int[] multiples)
    {
        if (upperLimit < 0 || lowerLimit < 0) { throw new ArgumentOutOfRangeException("lowerLimit and upperLimit needs to be greater than or equal to 0"); }
        if (multiples == null || multiples.Length == 0) { return 0; }

        return lowerLimit.GetSequence(upperLimit)
            .Where(i => i.IsMultipleOf(multiples))
            .Sum();
    }

    private static bool IsMultipleOf(this int value, IEnumerable<int> multiples)
    {
        foreach (int multiple in multiples)
        {
            if (value % multiple == 0) { return true; }
        }
        return false;
    }

}  

Чтобы решить настоящую проблему, назовите ее как

int lowerLimit = 1;
int upperLimit = 1000;
int res = lowerLimit.Solve(upperLimit, 3, 5);

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

11 голосов | спросил Heslacher 1 Jpm1000000pmFri, 01 Jan 2016 17:00:53 +030016 2016, 17:00:53

5 ответов


10

Это не столько ответ кода, сколько математический ответ.

Мы можем прямо вычислить число кратных \ $ m \ $ натурального числа \ $ n \ $, которые ниже предела \ $ x \ $. Это просто \ $ \ lceil x /n \ rceil \ $. Сумма этих кратных значений: $$ n \ sum_ {i = 1} ^ {\ lceil x /n \ rceil} = n \ left (\ frac {1} {2} (\ lceil x /n \ rceil) (\ lceil x /n \ rceil +1) \ справа) $$ Итак, для \ $ n = 3 \ $ и \ $ x = 999 \ $ получаем $$ 3 \ left (\ frac {1} {2} (333) (333 + 1) \ right) = 166833 $$ И для \ $ n = 5 \ $ и \ $ x = 999 \ $ мы получаем $$ 5 \ left (\ frac {1} {2} (200) (200 + 1) \ right) = 99500 $$ Таким образом, мы могли бы рассчитать ответ: $$ 166833 + 99500 = 266333 $$ Однако проблема здесь (подсказка шляпы к @MartinR!) Состоит в том, что у нас есть двойные подсчеты с кратным 15. Чтобы исправить это, нам нужно вычесть это число:

$$ 15 \ left (\ frac {1} {2} (66) (66 + 1) \ right) = 33165 $$ Таким образом, окончательный ответ correct равен $$ 266333 - 33165 = 233168 $$

ответил Edward 1 Jpm1000000pmFri, 01 Jan 2016 17:33:43 +030016 2016, 17:33:43
7

Именование GetSequence

Некоторые примеры из для вдохновения:

scala> 1.to(3)
res0: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3)

scala> 1.until(3)
res1: scala.collection.immutable.Range = Range(1, 2)

Основываясь на этих примерах, я предлагаю переименовать GetSequence в Until

Используйте Math, @Heslacher ...

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

  • Рассчитать количество кратных значений в диапазоне: int count = (target - 1) / multiple
  • Поймите, что мультипликаторы образуют последовательность, которая может быть упрощена, например:
    • 3, 6, 9, 12, ...
    • = 3 * (1, 2, 3, ...)
    • В этой последовательности 1, 2, 3, ... мы знаем, что существуют термины count. Формула для вычисления суммы такой последовательности: n * (n + 1) / 2

С помощью вспомогательной функции:

private int SumOfMultiples(int target, int multiple) {
    int count = (target - 1) / multiple;
    return multiple * count * (count + 1) / 2;
}

Это дает прямое решение \ $ O (1) \ $ для одного кратного. Для двух кратных a и b, вы не можете просто суммировать их, так как это будет включать в себя кратность их кратности дважды. Поэтому после суммирования вы должны были бы вычесть кратность a * b:

return SumOfMultiples(target, a)
    + SumOfMultiples(target, b)
    - SumOfMultiples(target, a * b);

Спасибо за @MartinR за подсказку, и @BorisTheSpider , чтобы указать на проблему с моим первоначальным ответом, который не вычитал.

В этом примере легко обрабатывать два параметра, например 3 и 5. Но, обрабатывая произвольное количество параметров, математика становится намного сложнее.

В заключение, когда multiples.Length <= 2, существует довольно простое математическое решение. Когда multiples.Length > 2 для реализации требуется больше работы и больше математики.

Ваше решение с итерацией может быть немного неэффективно, но оно простое и работает.

Проверка ввода

В этом коде:

public static int Solve(this int lowerLimit, int upperLimit, params int[] multiples)
{
    if (upperLimit < 0 || lowerLimit < 0) { throw new ArgumentOutOfRangeException("lowerLimit and upperLimit needs to be greater than or equal to 0"); }
    if (multiples == null || multiples.Length == 0) { return 0; }

Мне кажется, что lowerLimit задается областью проблем как 0, поэтому нет необходимости проверять это. Вместо делегирования проверки на GetSequence, было бы лучше сделать это раньше, здесь в Solve, а GetSequence может с уверенностью предположить получение действительных значений. Вы можете добавить оператор assert (если он существует в C #, я не знаю), чтобы документировать ваше предположение, если вы захотите скопируйте этот метод в библиотеку позже.

У меня теперь нет компилятора C #, но я догадываюсь, что multiples будет только null, если программист явно передает null. Которая была бы ошибкой программирования, так же как передача отрицательного upperLimit, поэтому я предлагаю исключить исключение в этом случае.

ответил janos 1 Jpm1000000pmFri, 01 Jan 2016 17:32:44 +030016 2016, 17:32:44
5

Вы можете упростить свой метод IsMultipleOf, используя Any из пространства имен System.Linq:

private static bool IsMultipleOf(this int value, IEnumerable<int> multiples)
{
    return multiples.Any(multiple => value % multiple == 0);
}
ответил RobH 1 Jpm1000000pmFri, 01 Jan 2016 17:25:55 +030016 2016, 17:25:55
4

Этот метод расширения GetSequence() уже существует в Linq в качестве метода расширения с именем Range(), который принимает start и count. Это нужно только вызывать с помощью 1 как start и 999 как count, потому что ---- +: = 9 =: + ---- включен, тогда как нам нужно иметь элементы count, чтобы проверить натуральные числа ниже 1..999.

Этот метод 1000 может быть таким образом интегрирован

Range()
ответил Heslacher 1 Jpm1000000pmFri, 01 Jan 2016 17:20:50 +030016 2016, 17:20:50
1

Этот код:

public static IEnumerable<int> GetSequence (this int lowerLimit, int upperLimit)
{
    if (upperLimit < lowerLimit) { throw new ArgumentOutOfRangeException("lowerLimit needs to be less or equal to upperLimit"); }

    for (int i = lowerLimit; i < upperLimit; i++)
    {
        yield return i;
    }
}

Может быть выполнено с помощью:

var range = Enumerable.Range(lowerLimit, upperLimit);

Он даже выбрасывает исключение из диапазона, поэтому вы можете полностью удалить оператор If, проверяющий это в методе Solve ().

Теперь, когда у вас есть IEnumerable, вы можете использовать LINQ:

return range.Where(i => i.IsMultipleOf(multiples)).Sum();

Черт, вы можете сходить с ума и сделать один лайнер:

return Enumerable.Range(lowerLimit, upperLimit).Where(i => i.IsMultipleOf(multiples)).Sum();

Я бы предложил использовать ответ RobH просто вашему методу IsMultipleOf (). Я также переместил бы нулевую проверку для мультипликаторов в метод IsMultipleOf (), и если null просто возвращает false.

При всем этом нам останется:

public static class SolverOfProblemOne
{
    public static int Solve (this int lowerLimit, int upperLimit, params int[] multiples)
    {
        return Enumerable.Range(lowerLimit, upperLimit).Where(i => i.IsMultipleOf(multiples)).Sum();
    }

    private static bool IsMultipleOf (this int value, IEnumerable<int> multiples)
    {
        return multiples != null && multiples.Any(multiple => value % multiple == 0);
    }
}
ответил wentimo 8 Jam1000000amFri, 08 Jan 2016 01:01:27 +030016 2016, 01:01:27

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132