Проблема
Для заданного числа n найдите сумму всех чисел, кратных 3 или 5 меньше n.
Пример
Пусть n = 20.
Кратность 3 меньше 20 равна 3,6,9,12,15,18.
Кратность 5 меньше 20 равна 5,10,15.
Сумма всех этих чисел равна 3+6+9+12+15+18+5+10=78.
Обратите внимание, что 15 кратно 3 и 5, и мы добавляем его к нашей сумме только один раз.
Подход 1: Циклы
Мой первый подход к этой проблеме заключался в том, чтобы сохранить переменную суммы, затем посмотреть на каждое число ниже n, проверить, является ли оно кратным 3 или 5, и соответственно добавить его к сумме.
Пример — n = 10
Мы начинаем нашу сумму = 0 и проверяем числа, начиная с 3.
3 кратно 3 -> сумма = 0+3 =3
4
5 кратно 5 -> сумма = 3+5 = 8
6 кратно 3 -> сумма = 8+6 = 14
7
8
9 кратно 3 -> сумма = 14+9 = 23
int sumMultiples(int n) {
int sum = 0;
for (int i = 3; i < n; i++) {
if (i % 3 == 0) sum += i;
if (i % 5 == 0) sum += i;
if (i % 15 == 0) sum -= i;
}
return sum;
}
Приведенное выше решение проверяет каждое число, добавляя его к сумме, а затем заботится о числах, кратных 3 и 5 (кратных 15).
Проблема с этим решением заключается в том, что вычисление все больших значений n займет много времени.
Подход 2: Математика
Поскольку эта задача из Project Euler, я подумал, что должен быть более эффективный способ ее решения с помощью математики. Чтобы попытаться решить эту проблему, я хотел попытаться определить сумму кратных чисел меньше n.
Итак, я решил начать просто с просмотра чисел, кратных 3. Я записываю некоторые числа, кратные 3, вместе с текущей совокупной суммой всех кратных 3, равных или меньше этого кратного:
Я также заметил, что кумулятивные суммы также были кратны 3, поэтому я записал каждую из этих сумм в виде 3 * x, создав третий столбец приведенной выше таблицы.
На данный момент явно существует какая-то закономерность, которая позволила бы нам определить кумулятивную сумму чисел, кратных 3 ниже n. Однако я не знал, откуда взялся второй множитель x в 3 * x = sum.
Я решил поближе взглянуть на эту третью колонку:
Обратите внимание, что операнд x увеличивается на 1 на каждой итерации.
Затем я решил попробовать собрать это вместе, чтобы вычислить сумму кратных 3 меньше n.
Пример — n = 10
Сумма кратных 3 меньше 10 равна 3 + 6 + 9 = 18.
18 можно переписать как 18 = 3 * 6.
6 можно переписать как 1 + 2 + 3. Таким образом, мы имеем 18 = 3 * (1 + 2 + 3).
Но откуда мы знаем, как вычислить (1 + 2 + 3)?
Давайте посмотрим на другие примеры n, чтобы увидеть, как мы получаем это значение.
n = 12, сумма = 30 = 3 * 10 = 3 * (1 + 2 + 3 + 4)
n = 15, сумма = 45 = 3 * 15 = 3 * (1 + 2 + 3 + 4 + 5)
n = 18, сумма = 63 = 3 * 21 = 3 * (1 + 2 + 3 + 4 + 5 + 6)
Следующая закономерность, которую я заметил, — это значение n. Мы можем переписать его как
n = 12 = 3* 4, сумма = 30 = 3 * 10 = 3 * (1 + 2 + 3 + 4)
n = 15 = 3 * 5, сумма = 45 = 3 * 15 = 3 * (1 + 2 + 3 + 4 + 5)
n = 18 = 3 * 6, сумма = 63 = 3 * 21 = 3 * (1 + 2 + 3 + 4 + 5 + 6)
Обратите внимание, что выделенные жирным шрифтом множители, которые мы переписали для n, соответствуют выделенным жирным шрифтом суммам справа. Назовем это число k.
Итак, сумма 1 + 2 + … — это просто сумма чисел от 1 до k. Мы можем использовать существующую формулу (k)(k+1)/2, чтобы вычислить это.
Сумма кратных 3 ниже n
Мы можем собрать все это вместе, чтобы получить уравнение для нахождения суммы всех чисел, кратных 3 ниже n.
int sumMultiples(int n) {
n -=1; // we only want values below n
int n3 = n / 3;
int sum3 = 3 * (n3) * (n3+1) / 2;
}
Решение
Наконец, мы повторяем ту же формулу, чтобы получить все кратные 5 и 15 меньше n, и вычисляем нашу окончательную сумму:
int sumMultiples(int n) {
n -=1; // we only want values below n
long int n3 = n/3;
long int n5 = n/5;
long int n15 = n/15;
long int sum3 = 3 * (n3) * (n3+1) / 2;
long int sum5 = 5 * (n5) * (n5+1) / 2;
long int sum15 = 15 * (n15) * (n15+1) / 2;
return sum3 + sum5 - sum15;
}
Теперь у нас есть хорошее решение, которое намного эффективнее при больших значениях n.
Готово :D
