Проект Euler #1 на Java

Question

Проект Euler #1 на Java

У меня проблемы с этим кодом. Я не хочу смотреть на других, поэтому мне интересно, что не так с моей.

Если мы перечислим все натуральные числа ниже 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих кратных равна 23.

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

public class Multiples {
    public static void main (String [] args) {
        int temp = 0;
        int temp2 = 0; 

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

        for (int j = 0; j <= 1000; j++) {
            if (j % 5 == 0) {
                temp2 = temp2 + j;
            }
        }

        System.out.println(temp + temp2);
    }
}

Я получаю значение 267333, что неверно. Мое добавление неправильно? Я знаю, алгоритмически, этот код может быть не на высоте, но он должен работать, верно?

6

java

Источник

user3014496 28 янв '14 в 09:02

8 ответов

Другие вопросы по тегам java

user3885376 09 ноя '14 в 12:36 2014-11-09 12:36 · Answer 1 · 2014-11-09 12:36

Решения

1) O(n):

Небольшое улучшение для других ответов (i можно начать с 3):

public static void main(String[] args) {
    int sum = 0;
    for (int i = 3; i < 1000; i++) {
        if (i % 3 == 0 || i % 5 == 0) {
            sum += i;
        }
    }
    System.out.println(sum);
}

Для большего числа ввода (Integer.MAX_VALUE вместо 1000) занимает:

195 секунд

2) O(n) = O(n/3) + O(n/5) + O(n/15):

Это более эффективно и использует ваш первоначальный подход (удалите числа, которые были взяты дважды):

public static void main(String[] args) {
    long sum = 0 ;
    for ( long i = 3 ; i < 1000 ; i+=3 ){
        sum+=i;
    }
    for ( long i = 5 ; i < 1000 ; i+=5 ){
        sum+=i;
    }       
    for ( long i = 15 ; i < 1000 ; i+=15 ){
        sum-=i;
    }
    System.out.println(sum);
}

В первом случае мы имеем около n (1000) значения для iво втором случае мы имеем только около n/3 + n/5 + n/15 (600) значения для i, Второй также лучше, потому что меньше сравнений (нет if участвует).

Для большего числа ввода (Integer.MAX_VALUE вместо 1000) занимает:

9 секунд

3) O(1):

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

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

В этом случае, даже если вход Integer.MAX_VALUEвычисление выполняется очень быстро (менее 1 мс).

user1735406 28 янв '14 в 09:06 2014-01-28 09:06 · Answer 2 · 2014-01-28 09:06

Ты должен сделать:

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

Это добавит каждый номер только один раз. В своем коде вы добавите 15 дважды, поскольку в обоих циклах это будет выполнено в обоих условиях.

Также обратите внимание, что в соответствии с требованиями, вы должны вернуться к < 1000не <=,

user2422776 28 янв '14 в 09:08 2014-01-28 09:08 · Answer 3 · 2014-01-28 09:08

Если число является множителем как 3, так и 5 (например, 15, 30, 45 и т. Д.), Вы будете считать его дважды. Так что вместо двух for петли, вы должны иметь один, со сложным условием:

public class Multiples {
    public static void main (String [] args) {
    int temp = 0;

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

    }

    System.out.println (temp);
   }
}

user7948520 16 май '17 в 20:09 2017-05-16 20:09 · Answer 4 · 2017-05-16 20:09

Некоторые определенные условия возникают, когда оба условия удовлетворяют как для 3, так и для 5. например, когда i=15 удовлетворяет как для 15%3==0, так и для 15%5==0. так что, вероятно, ваш ответ больше, чем ожидалось, потому что вы пробовали 3 и 5 отдельно. делая это во время этих определенных условий, вы добавляете повторяющиеся значения. Следовательно, лучше проверить в одном цикле. как это -

    for(int i=0 ; i<1000 ; i++)
    {
        if(i%3==0 || i%5==0)
        {
            temp = temp + i;
        }
        System.out.println(temp);
    }

user3457026 25 мар '14 в 18:08 2014-03-25 18:08 · Answer 5 · 2014-03-25 18:08

Ваш код неверен из-за простой проблемы: есть числа, которые можно разделить на 3 и 5. В вашем коде вы учитываете их дважды: один раз в первом цикле и во втором во втором цикле. Что вы должны сделать, это один из вариантов ниже:

О. Просто запустите один цикл и используйте два условия вместо одного: проверьте, можно ли разделить число на 3, а также можно разделить на 5 - и только затем добавьте его к общей сумме.

Б. Я создал код Python, используя тот же метод, что и вы, но с дополнительным условием. Это абсолютно не рекомендуется и не эффективно, но может помочь вам лучше понять.

numlist = []

for i in range (1, 1000):
    if i % 3 == 0:
        numlist.append(i)


for j in range (1, 1000):
    if j % 5 == 0:
        if not j in numlist:
            numlist.append(j)


counter = 0
for a in numlist:
    counter += a


print counter

user9817963 20 май '18 в 05:58 2018-05-20 05:58 · Answer 6 · 2018-05-20 05:58

Просто напишите этот простой код Java.

 public static void main(String[] args)
{
int i,sum=0;
for ( i = 3; i <1000; i++)
 {
 if ((i % 3 == 0)||(i%5==0) )
 sum=sum+i;
 }
System.out.print(sum);
}

Вы получите вывод как 233168

0

Источник

user9817963 20 май '18 в 05:58

user1572906 08 фев '14 в 06:18 2014-02-08 06:18 · Answer 7 · 2014-02-08 06:18

Вы добавили все кратные 15 дважды. Используя ваш алгоритм, запустите третий цикл и проверьте, делится ли число на 15, а затем удалите его из общей суммы.

0

Источник

user1572906 08 фев '14 в 06:18

user567328 08 июл '14 в 08:37 2014-07-08 08:37 · Answer 8 · 2014-07-08 08:37

public static int sumOfMultiples(int i, int j, int limit){
    int s = --limit / i, t = limit / j, u = limit / (i * j);
    return (i*(s*(s+1)/2)) + (j*(t*(t+1)/2)) - ((i*j)*(u*(u+1)/2));
}

Тестовое задание

actual = Prob1.sumOfMultiples(3, 5, 1000);
assertEquals(233168, actual);

-1

Источник

user567328 08 июл '14 в 08:37