Project Euler: проблема 1 (возможный рефакторинг и оптимизация времени выполнения) - PullRequest
4 голосов
/ 30 июля 2010

Я много слышал о 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));

        }
    } 

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

Спасибо

Ответы [ 13 ]

0 голосов
/ 26 января 2015
new List<int>{3,5}.SelectMany(n =>Enumerable.Range(1,999/n).Select(i=>i*n))
                  .Distinct()
                  .Sum()

[Обновить] (В ответ на комментарий с просьбой объяснить этот алгоритм) Это создает сплюснутый список кратных для каждого базового значения (в данном случае 3 и 5), затем удаляет дубликаты (например, где кратноделится, в этом случае, на 3 * 5 = 15) и затем суммирует оставшиеся значения.(Также это легко обобщить, если иметь более двух базовых значений IMHO по сравнению с любыми другими решениями, которые я видел здесь.)

0 голосов
/ 11 декабря 2014
Your approach is brute force apprach, The time complexity of the following approach is O(1), Here we     
are dividing the given (number-1) by 3, 5 and 15, and store in countNumOf3,countNumOf5, countNumOf15.
Now we can say that 3 will make AP, within the range of given (number-1) with difference of 3. 
suppose you are given number is 16, then 
3=> 3, 6, 9, 12, 15= sum1=>45
5=> 5, 10, 15  sum2=> 30
15=> 15 =>   sum3=15  
Add sum= sum1 and sum2


Here 15 is multiple of 3 and 5  so remove sum3 form sum, this will be your answer. **sum=sum-    
sum3** please check link of my solution on http://ideone.com/beXsam]

import java.util.*;
class Multiplesof3And5 {        
        public static void main(String [] args){
            Scanner scan=new Scanner(System.in);
            int num=scan.nextInt();
            System.out.println(getSum(num));
        }    
        public static  long getSum(int n){
            int countNumOf3=(n-1)/3;//             
            int countNumOf5=(n-1)/5;           
            int countNumOf15=(n-1)/15;            
            long sum=0;           
            sum=sumOfAP(3,countNumOf3,3)+sumOfAP(5,countNumOf5,5)-sumOfAP(15,countNumOf15,15);
            return sum;
        }
        public static int sumOfAP(int a, int n, int d){
            return (n*(2*a +(n -1)*d))/2;
        }
}
0 голосов
/ 31 июля 2010

Мне нравится идея technielogys, вот моя идея модификации

static int Euler1 () 
{ 
  int sum = 0; 

  for (int i=3; i<1000; i+=3) 
  {
    if (i % 5 == 0) continue;
    sum+=i; 
  }
  for (int i=5; i<1000; i+=5) sum+=i; 

  return sum; 
} 

Хотя также приходит на ум, может быть, небольшая эвристика, это улучшает?

static int Euler1 () 
{ 
  int sum = 0; 

  for (int i=3; i<1000; i+=3) 
  {
    if (i % 5 == 0) continue;
    sum+=i; 
  }
  for (int i=5; i<250; i+=5)
  {
    sum+=i;
  }
  for (int i=250; i<500; i+=5)
  {
    sum+=i;
    sum+=i*2;
    sum+=(i*2)+5;
  }

  return sum; 
} 
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...