Java中的Euler程序

Question

我刚开始解决Project Eulers问题.尽管这个很简单.我想就最佳解决方案发表意见.

问题:

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

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

这是我编码的方式:

package com.problem.one.ten;
public class NaturalNumber {

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

Answer 1

更好的解决方案是包含 - 排除原则的简单应用.我们感兴趣的所有数字的总和是(1)可被3整除的所有数字的总和加上(2)可被5整除的所有数字的总和,减去(3)可被15整除的所有数字的总和. 3个和是算术级数的总和,相对容易找到.基本上,您不需要循环.

非负整数整除的数Ñ下面Ñ正是[(Ñ - 1)/ Ñ ] + 1的最大数目,例如是Ñ*([(Ñ - 1)/ Ñ ],因此由算术级数总和公式,它们的和是[(N -1)/ n ]*([(N -1)/ n ] + 1)*n/2.

对于我们的案例,我们得到:

1. N = 1000,n = 3,[(N -1)/ n ] = 333,sum = 333*334*3/2.
2. N = 1000,n = 5,[(N -1)/ n ] = 199,sum = 199*200*5/2.
3. N = 1000,n = 15,[(N -1)/ n ] = 66,sum = 66*67*15/2.

最终结果是233168.

也许存在更好的解决方案.

Answer 2

看起来不错,不过我会把它放进sum去.这对一个简单的程序来说并不是什么大不了的事.但一般来说,您应该在尽可能窄的范围内声明变量.

Answer 3

虽然我确信这个问题有一个O(1)解决方案,但考虑到你只被要求提供1000的答案,找出它是不值得的.

我同意Matthew,sum应该是一个局部变量,但除此之外,你的代码对我来说也很好.

没有代码的解决方案(只是为了好玩):

使用sum(1+2+3+...+n)= 的事实n(n+1)/2,我们可以推导出x的倍数之和低于1000 floor(1000/x)*(floor(1000/x)+1)/2*x.

我们需要的答案是低于1000的3的倍数之和加上5的倍数之和减去15的倍数之和(否则将是双倍数).

有999/3 = 333倍数3低于1000,999/5 = 199倍数5低于1000,9和999/15 = 66倍数15低于1000

因此,所有3的倍数之和低于1000 = 333*334/2*3 = 166833,5的倍数之和低于1000 = 199*200/2*5 = 99500,以及15的倍数之和低于1000 = 66*67/2*15 = 33165

回答166833 + 99500 - 33165 = 233168

Answer 4

您的解决方案在逻辑上最简单,因此最容易验证.像弗拉德和卢克这样的分析解决方案效率最高.

但是对于它的价值,当我看到问题时,我的第一个想法是:

public int doit()
{
  int sum=0;
  for (int n=0;n<1000;n+=3)
  {
    sum+=n;
  }
  for (int n=0;n<1000;n+=5)
  {
    if (n%3!=0) // Don't pick up the 3's twice
      sum+=n;
  }
  return sum;
}

这比你的解决方案更有效,因为它会跳过我们知道我们不感兴趣的数字.而且它的工作方式仍然非常直观.

一个无循环的解决方案更好,但我发布这个只是因为我在5分钟内开会,而我已经在这里了.