Решение проблемы Эйлера проекта 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);
Любые предложения по показанному коду приветствуются. Поскольку математика закрыла для меня двери после окончания школы, я не знаю, есть ли какой-либо математический трюк, чтобы сделать это быстрее или легче.
5 ответов
Это не столько ответ кода, сколько математический ответ.
Мы можем прямо вычислить число кратных \ $ 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 $$
Именование GetSequence
Некоторые примеры из scala для вдохновения:
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
, поэтому я предлагаю исключить исключение в этом случае.
Вы можете упростить свой метод IsMultipleOf
, используя Any
из пространства имен System.Linq:
private static bool IsMultipleOf(this int value, IEnumerable<int> multiples)
{
return multiples.Any(multiple => value % multiple == 0);
}
Этот метод расширения GetSequence()
уже существует в Linq
в качестве метода расширения с именем Range()
, который принимает start
и count
. Это нужно только вызывать с помощью 1
как start
и 999
как count
, потому что ---- +: = 9 =: + ---- включен, тогда как нам нужно иметь элементы count
, чтобы проверить натуральные числа ниже 1..999
.
Этот метод 1000
может быть таким образом интегрирован
Range()
Этот код:
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);
}
}