Java中的项目Euler#1

发布时间：2020-12-14 23:23:11 所属栏目：Java 来源：网络整理

导读：我遇到了这段代码的问题.我不想看别人,所以我想知道我的错是什么. 如果我们列出10以下的所有自然数是3或5的倍数,我们得到3,5,6和9.这些倍数的总和是23. 求出1000以下3或5的所有倍数的总和. public class Multiples { public static void main (String [] arg

我遇到了这段代码的问题.我不想看别人,所以我想知道我的错是什么.

如果我们列出10以下的所有自然数是3或5的倍数,我们得到3,5,6和9.这些倍数的总和是23.

求出1000以下3或5的所有倍数的总和.

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,这是错误的.我的添加错了吗？我在算法上知道,这段代码可能达不到标准,但它应该有用,对吧？

解决方法

解决方案

1)O(n)：

其他答案的一个小改进(我可以从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);
}

在第一种情况下,对于i,我们有大约n(1000)个值,在第二种情况下,我们只有大约n / 3 n / 5 n / 15(600)的值.第二个也更好,因为比较较少(如果涉及则没有).

对于更大的输入数字(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 ms).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!