Project Euler: проблема 1 (возможный рефакторинг и оптимизация времени выполнения)

Question

Я много слышал о Project Euler, поэтому подумал, что решил одну из проблем в C #. Проблема, указанная на сайте, выглядит следующим образом:

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

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

Я написал свой код следующим образом:

  class EulerProblem1
    {
        public static void Main()
        {
            var totalNum = 1000;
            var counter = 1;
            var sum = 0;

            while (counter < totalNum)
            {
                if (DivisibleByThreeOrFive(counter))
                    sum += counter;

                counter++;
            }

            Console.WriteLine("Total Sum: {0}", sum);
            Console.ReadKey();
        }

        private static bool DivisibleByThreeOrFive(int counter)
        {
            return ((counter % 3 == 0) || (counter % 5 == 0));

        }
    } 

Было бы здорово получить некоторые идеи по альтернативным реализациям с меньшим количеством многословия / более чистым синтаксисом и лучшей оптимизацией. Идеи могут варьироваться от быстрого и грязного до выведения пушки, чтобы уничтожить комара. Цель состоит в том, чтобы исследовать глубины компьютерных наук, пытаясь улучшить этот особенно тривиальный фрагмент кода.

Спасибо

Answer 1

Обновлен, чтобы не считать двойные числа, кратные 3 и 5:

int EulerProblem(int totalNum)
{
   int a = (totalNum-1)/3;
   int b = (totalNum-1)/5;
   int c = (totalNum-1)/15;
   int d = a*(a+1)/2;
   int e = b*(b+1)/2;
   int f = c*(c+1)/2;
   return 3*d + 5*e - 15*f;
}

Answer 2

С LINQ (обновлено, как предлагается в комментариях)

static void Main(string[] args)
{
    var total = Enumerable.Range(0,1000)
                    .Where(counter => (counter%3 == 0) || (counter%5 == 0))
                    .Sum();

    Console.WriteLine(total);
    Console.ReadKey();
}

Answer 3

Вот транслитерация моего исходного решения F # в C #. Отредактировано: это в основном решение mbeckish как цикл, а не функция (и я убираю двойной счет). Мне больше нравится mbeckish.

static int Euler1 ()
{
  int sum = 0;

  for (int i=3; i<1000; i+=3) sum+=i;
  for (int i=5; i<1000; i+=5) sum+=i;
  for (int i=15; i<1000; i+=15) sum-=i;

  return sum;
}

Вот оригинал:

let euler1 d0 d1 n =
  (seq {d0..d0..n}       |> Seq.sum) +
  (seq {d1..d1..n}       |> Seq.sum) -
  (seq {d0*d1..d0*d1..n} |> Seq.sum)

let result = euler1 3 5 (1000-1)

Answer 4

Рефакторинг очень умного решения @ mbeckish:

public int eulerProblem(int max) {
    int t1 = f(max, 3);
    int t2 = f(max, 5);
    int t3 = f(max, 3 * 5);
    return t1 + t2 - t3;
}

private int f(int max, int n) {
    int a = (max - 1) / n;
    return n * a * (a + 1) / 2;
}

Answer 5

Я давно не писал ни одной Java, но это должно решить ее за постоянное время с небольшими накладными расходами:

public class EulerProblem1
{
    private static final int EULER1 = 233168;
    // Equal to the sum of all natural numbers less than 1000
    // which are multiples of 3 or 5, inclusive.

    public static void main(String[] args)
    {
        System.out.println(EULER1);
    }
}

РЕДАКТИРОВАТЬ: Вот реализация C, если каждая инструкция имеет значение:

#define STDOUT     1
#define OUT_LENGTH 8

int main (int argc, char **argv)
{
    const char out[OUT_LENGTH] = "233168\n";
    write(STDOUT, out, OUT_LENGTH);
}

Примечания:

• Нет обработки ошибок при вызове write.Если требуется истинная надежность, следует использовать более сложную стратегию обработки ошибок.Вопрос о том, стоит ли добавленная сложность большей надежности, зависит от потребностей пользователя.
• Если у вас есть ограничения памяти, вы можете сохранить байт, используя массив прямых символов, а не строку, заканчивающуюся лишним.нулевой символНа практике, однако, out почти наверняка будет заполнен до 8 байтов в любом случае.
• Хотя объявления переменной out можно избежать, поместив строку в строку в вызове write, любой действительныйкомпилятор уберет декларацию.
• Системный вызов write используется вместо puts или аналогичным, чтобы избежать дополнительных издержек.Теоретически, вы можете вызвать системный вызов напрямую, возможно, сэкономив несколько циклов, но это вызовет значительные проблемы с переносимостью.Ваш пробег может варьироваться в зависимости от того, является ли это приемлемым компромиссом.

Answer 6

Вы можете сделать что-то вроде этого:

Func<int,int> Euler = total=> 
    new List<int>() {3,5}
        .Select(m => ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2)
        .Aggregate( (T, m) => T+=m);

У вас все еще есть проблема двойного счета. Я подумаю об этом немного больше.

Edit:

Вот рабочее (хотя и несколько не элегантное) решение в LINQ:

        var li = new List<int>() { 3, 5 };
        Func<int, int, int> Summation = (total, m) => 
           ((int) (total-1) / m) * m * (((int) (total-1) / m) + 1) / 2;

        Func<int,int> Euler = total=> 
            li
                .Select(m => Summation(total, m))
                .Aggregate((T, m) => T+=m)
            - Summation(total, li.Aggregate((T, m) => T*=m));

Кто-нибудь из вас, ребята, может улучшить это?

Пояснение:

Помните, что формула суммирования для линейной прогрессии равна n (n + 1) / 2. В первом случае, когда у вас есть кратные 3,5 <10, вы хотите Сумма (3 + 6 + 9,5). Установив total = 10, вы делаете последовательность из целых чисел 1 .. (int) (total-1) / 3, а затем суммируете последовательность и умножаете на 3. Вы можете легко увидеть, что мы просто устанавливаем n = (int ) (total-1) / 3, затем с помощью формулы суммирования и умножения на 3. Маленькая алгебра дает нам формулу для функтора суммирования. </p>

Answer 7

Попробуйте это в Си. Это постоянное время, и есть только одно деление (два, если компилятор не оптимизирует div / mod, как должно).Я уверен, что можно сделать это немного более очевидным, но это должно сработать.

По сути, это делит сумму на две части.Большая часть (для N> = 15) представляет собой простую квадратичную функцию, которая делит N на точные блоки по 15. Меньшая часть - это последний бит, который не помещается в блок.Последний бит более сложный, но есть только несколько возможностей, поэтому LUT решит его в кратчайшие сроки.

const unsigned long N = 1000 - 1;
const unsigned long q = N / 15;
const unsigned long r = N % 15;
const unsigned long rc = N - r;

unsigned long sum = ((q * 105 + 15) * q) >> 1;

switch (r) {
    case 3  : sum += 3  + 1*rc ; break;
    case 4  : sum += 3  + 1*rc ; break;
    case 5  : sum += 8  + 2*rc ; break;
    case 6  : sum += 14 + 3*rc ; break;
    case 7  : sum += 14 + 3*rc ; break;
    case 8  : sum += 14 + 3*rc ; break;
    case 9  : sum += 23 + 4*rc ; break;
    case 10 : sum += 33 + 5*rc ; break;
    case 11 : sum += 33 + 5*rc ; break;
    case 12 : sum += 45 + 6*rc ; break;
    case 13 : sum += 45 + 6*rc ; break;
    case 14 : sum += 45 + 6*rc ; break;
}

Answer 8

Для этого можно придумать решение в закрытой форме. Хитрость заключается в том, чтобы искать шаблоны. Попробуйте перечислить термины в сумме, скажем, десять или двадцать, а затем с помощью алгебры сгруппировать их. Делая соответствующие замены, вы можете обобщить это число, отличное от десяти. Просто будьте осторожны с крайними случаями.

Answer 9

Код в DivisibleByThreeOrFive будет немного быстрее, если вы сформулируете его следующим образом:

return ((counter % 3 == 0) || (counter % 5 == 0));

И если вы не хотите полагаться на то, что компилятор встроит вызов функции, вы можете сделать это самостоятельно, вставив этот код в процедуру Main.

Answer 10

Это в основном так же, как я сделал эту проблему. Я знаю, что были и другие решения (возможно, более эффективные) на форумах для Project-Euler.

Как только вы введете свой ответ, возвращаясь к вопросу, вы сможете перейти на форум по этой проблеме. Вы можете посмотреть туда!