Java中的项目Euler#1

前端之家收集整理的这篇文章主要介绍了Java中的项目Euler#1前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我遇到了这段代码的问题.我不想看别人,所以我想知道我的错是什么.

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

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

  1. public class Multiples {
  2. public static void main (String [] args) {
  3. int temp = 0;
  4. int temp2 = 0;
  5.  
  6. for (int i = 0; i <= 1000; i++) {
  7. if (i % 3 == 0) {
  8. temp = temp + i;
  9. }
  10. }
  11.  
  12. for (int j = 0; j <= 1000; j++) {
  13. if (j % 5 == 0) {
  14. temp2 = temp2 + j;
  15. }
  16. }
  17.  
  18. System.out.println(temp + temp2);
  19. }
  20. }

我得到的值是267333,这是错误的.我的添加错了吗?我在算法上知道,这段代码可能达不到标准,但它应该有用,对吧?

解决方法

解决方

1)O(n):

其他答案的一个小改进(我可以从3开始):

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

对于更大的输入数字(Integer.MAX_VALUE而不是1000),需要:

> 195秒

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

这样更有效,并使用您的初始方法(删除两次拍摄的数字):

  1. public static void main(String[] args) {
  2. long sum = 0 ;
  3. for ( long i = 3 ; i < 1000 ; i+=3 ){
  4. sum+=i;
  5. }
  6. for ( long i = 5 ; i < 1000 ; i+=5 ){
  7. sum+=i;
  8. }
  9. for ( long i = 15 ; i < 1000 ; i+=15 ){
  10. sum-=i;
  11. }
  12. System.out.println(sum);
  13. }

在第一种情况下,对于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

  1. public static void main(String[] args) {
  2. int nr = 1000;
  3. nr--;
  4. int x3 = nr/3;
  5. int x5 = nr/5;
  6. int x15 = nr/15;
  7.  
  8. long sum1 = 3*x3*(x3+1);
  9. long sum2 = 5*x5*(x5+1);
  10. long sum3 = 15*x15*(x15+1);
  11.  
  12. long sum = (sum1+sum2-sum3)/2;
  13. System.out.println(sum);
  14. }

在这种情况下,即使输入为Integer.MAX_VALUE,计算也非常快(小于1 ms).

猜你在找的Java相关文章