Project Euler #1 в Java - почему результат правильный, хотя и округленный?

Question

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

У меня возникают проблемы с пониманием того, почему приведенное ниже решение по-прежнему возвращает правильный результат, потому что x3, x5 и x15 используют int после деления. Это означает, что результат деления всегда округляется вниз, а десятичные дроби игнорируются.

Когда я попытался заменить все 3 ints на double, я получил неправильный результат.

Решение основано на следующем наблюдении:

1 + 2 +... + n = n * (n + 1) / 2

public static void main(String[] args) {
    int nr = 1000;
    nr--;
    int x3 = nr/3;
    int x5 = nr/5;
    int x15 = nr/15;

    long sum1 = 3*x3*(x3+1); 
    long sum2 = 5*x5*(x5+1);
    long sum3 = 15*x15*(x15+1);

    long sum = (sum1+sum2-sum3)/2;
    System.out.println(sum)
}

Ссылка

Answer 1

Когда я попытался заменить все 3 ints на double, я получил неправильный результат.

Вы должны сделать настил из целочисленного деления, потому что не существует дробного числа чисел, делимых на делитель: нет 199,8 положительных чисел, меньших, чем 1000 делится на 5, есть 199.

Итак, используя doubleВы перебираете общее количество:

sum2 = floor(5 * 199.8 * 200.8) = floor(200599.2) = 200599
  vs
sum2 = floor(5 * 199   * 200  ) = floor(199000  ) = 199000

Answer 2

Принятие 3 в качестве примера, сумма чисел, которые делятся на 3 и меньше чем 1000 является: (3 + 6 + 9 + 12 + ... + 999)

Вышесказанное можно переписать как 3 * (1 + 2 + 3 + .... + 333), А также 333 = integer part of (999/3), Это также можно записать как floor(999/3),

Сумма (1 + 2 + 3 + .... + 333) = 333 * (333 + 1) / 2 или же floor(999/3) * (floor(999/3) + 1) / 2 = 55611, Это именно то, что делается с помощью кода выше. С помощью int дает вам простой способ сделать floor операция.

Если вы использовали doubleвы бы сделали 333.333 * (333.333 + 1) / 2 который 55722.111, число отличается от 55611, Это вносит несоответствие, которое вы видите.

Answer 3

Целые числа x3, x5 и x15 являются просто ответами на вопрос: "Сколько натуральных чисел, меньших M, кратно N?" Вот таблица, которая демонстрирует это, когда N = 3:

M Count
1 0
2 0
3 0
4 1
5 1
6 1
7 2
...

Как видите, обобщение ответа Count = floor((M - 1) / N), как бывает, как положительное целочисленное деление определяется в Java.

Я сделал вывод, что это округление - то, о чем вы спрашивали, учитывая, что это единственное усекающее целочисленное деление из приведенного выше кода.