Блог

Я знаю, как заставить программу суммировать суммы кратных для каждого из 3, 5 и 7, но я не уверен, как бы я заставил программу использовать каждое число только один раз. Например, я могу заставить программу найти все числа и сложить их до 3, а затем сделать то же самое для 5, но тогда число 15 будет в конечном числе дважды. Я не уверен точно, как бы я заставил его принимать число только один раз. Спасибо за любую помощь.

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

Идея состоит в том, чтобы сначала суммировать слишком много чисел, рассматривая кратные 3, 5 и 7 по отдельности. Затем мы вычитаем те, которые мы посчитали дважды, то есть кратные 3 * 5, 3 * 7 и 5 *7. Но теперь мы вычли слишком много, и нам нужно добавить обратно числа, кратные 3*5*7 еще раз.

Начнем с нахождения суммы всех целых чисел, 1..n которые кратны k . Сначала мы узнаем, сколько их, m = n / k округленных в меньшую сторону, благодаря целочисленному делению. Теперь нам просто нужно суммировать последовательность k 2*k 3*k ... m*k . Мы разлагаем k и получаем k * (1 2 ... m) .

Это хорошо известный арифметический ряд, который, как мы знаем, суммируется с k * m * (m 1)/2 (см. Число треугольника).

 private long n = 9999;
private long multiples(long k) {
    long m = n / k;
    return k * m * (m   1) / 2:
}
  

Теперь мы просто используем включение-исключение, чтобы получить окончательную сумму:

 long sum = multiples(3)   multiples(5)   multiples(7)
         - multiples(3*5) - multiples(3*7) - multiples(5*7)
           multiples(3*5*7);
  

Это будет намного лучше масштабироваться до большего, n чем просто перебирать все значения, но остерегайтесь переполнения и при необходимости измените на BigInteger s.

Самым простым подходом было бы использовать for цикл таким образом:

 int sum = 0;
for(int i=1; i<10000; i  )
{
    if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        sum  = i;
}
  

Используйте Set для хранения уникальных кратных, а затем суммируйте значения набора.

Я бы использовал Set. Таким образом, вы гарантированно не получите никаких дубликатов, если они являются вашей основной проблемой.

Одним из простых решений было бы добавить каждое число, кратное 3,5 или 7, в список ответов. И затем, когда вы работаете с каждым числом, убедитесь, что его еще нет в списке ответов.

(псевдокод)

 List<int> AnswerList;
List<int> MultiplesOfFive;
List<int> MultiplesOfSeven;
List<int> MultiplesOfThree;

for (int i = 0 ; i < 10000; i  )
{
  if ( i % 3 == 0 amp;amp; AnswserList.Contains(i) == false)
  {
    MultiplesOfThree.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 5 == 0 amp;amp; AnswserList.Contains(i) == false)
  {
    MultiplesOfFive.Add(i); 
    AnswerList.Add(i);
  }
  if ( i % 7 == 0 amp;amp; AnswserList.Contains(i) == false)
  {
    MultiplesOfSeven.Add(i); 
    AnswerList.Add(i);
  }
}
  

для решения, которое повторяет цикл от 1 до 1000, используйте i<=10000, иначе оно пропустит само 10000, что кратно 5. Извиняюсь, по какой-то причине я не могу опубликовать это в качестве комментария