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

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

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

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

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

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)
}

Справочник


java algorithm gauss
person lioli    schedule 25.01.2017    source источник
comment
вы знакомы с циклами?   -  person Mohsen_Fatemi    schedule 26.01.2017
comment
@Mohsen_Fatemi Для этого вам не нужны петли.   -  person Dawood ibn Kareem    schedule 26.01.2017
comment
@Mohsen_Fatemi, вы знакомы с историей о том, как учитель Карла Фридриха Гаусса пытался на некоторое время занять класс? (И принцип включения-исключения)   -  person Andy Turner    schedule 26.01.2017
comment
@AndyTurner Вау, это была теорема !!! я не узнал его в первый раз ... это было здорово, спасибо   -  person Mohsen_Fatemi    schedule 26.01.2017
comment
Ваше наблюдение работает, если n является положительным целым числом, но на самом деле ничего не значит, если n имеет дробную часть. Вы можете действительно использовать его, только если вы имеете дело исключительно с целыми числами. Вы действительно ожидали, что сложите кучу целых чисел и получите нецелочисленный ответ?   -  person Dawood ibn Kareem    schedule 26.01.2017

Ответы (3)


arrow_upward
0
arrow_downward

Целые числа 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 определяется положительное целочисленное деление.

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

person Jeff G    schedule 25.01.2017

arrow_upward
0
arrow_downward

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

Вам нужно выполнить настил из целочисленного деления, потому что не существует дробного числа чисел, делящихся на делитель: нет 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
person Andy Turner    schedule 25.01.2017

arrow_upward
0
arrow_downward

Взяв в качестве примера 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. Это приводит к несоответствию, которое вы видите.

person user1952500    schedule 25.01.2017