java Java中的欧拉程序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4137350/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Euler program in Java
提问by t0mcat
I just started with solving Project Eulers problems. Even though this one is very simple. I want to take your opinion on the best solution.
我刚开始解决 Project Eulers 问题。虽然这个很简单。我想听取您对最佳解决方案的意见。
问题：
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
如果我们列出所有 10 以下的自然数是 3 或 5 的倍数，我们会得到 3、5、6 和 9。这些倍数之和是 23。
找出 1000 以下所有 3 或 5 的倍数之和。
This is how I coded it:
这是我编码的方式：
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);
}
}
回答by Vlad
A better solution is a simple application of inclusion-exclusion principle. The sum of all numbers we are interested in is (1) the sum of all numbers divisible by 3, plus (2) the sum of all numbers divisible by 5, minus (3) the sum of all numbers divisible by 15. Each of the 3 sums is a sum of an arithmetic progression, which is relatively easy to find. Basically, you don't need a loop.
更好的解决方案是简单地应用包含-排除原则。我们感兴趣的所有数的和是 (1) 所有能被 3 整除的数之和，加上 (2) 所有能被 5 整除的数之和，减去 (3) 所有能被 15 整除的数之和。这3个和是一个等差数列的和，比较容易找到。基本上，您不需要循环。
The number of non-negative integers divisible by nbelow Nis exactly [(N- 1) / n] + 1. The maximal such number is n* ([(N- 1) / n], therefore by the arithmetic progression sum formula, their sum is [(N- 1) / n] * ([(N- 1) / n] + 1) * n/ 2.
在N之下可被n整除的非负整数的数量正好是 [( N- 1) / n] + 1。这样的最大数量是n* ([( N- 1) / n]，因此由等差数列和公式，它们的总和是 [( N- 1) / n] * ([( N- 1) / n] + 1) * n/ 2。
For our case, we have got:
对于我们的案例，我们有：
- N= 1000, n= 3, [(N- 1) / n] = 333, sum = 333*334*3/2.
- N= 1000, n= 5, [(N- 1) / n] = 199, sum = 199*200*5/2.
- N= 1000, n= 15, [(N- 1) / n] = 66, sum = 66*67*15/2.
- N= 1000，n= 3，[( N- 1) / n] = 333，总和 = 333*334*3/2。
- N= 1000，n= 5，[( N- 1) / n] = 199，总和 = 199*200*5/2。
- N= 1000, n= 15, [( N- 1) / n] = 66, sum = 66*67*15/2。
The final result is 233168.
最终结果是 233168。
Perhaps an even better solution exists.
也许存在更好的解决方案。
回答by Matthew Flaschen
It looks fine, though I would put sumin main. It's not a big deal on such a simple program. But in general, you should declare variables in the narrowest possible scope.
看起来不错，虽然我会放在sum主要的。这么简单的程序没什么大不了的。但一般来说，您应该在尽可能窄的范围内声明变量。
回答by Luke Hutteman
While I'm sure there is an O(1) solution to this problem, figuring it out would not be worth the effort considering you're only asked to provide the answer for 1000.
虽然我确信这个问题有一个 O(1) 的解决方案，但考虑到你只被要求提供 1000 的答案，弄清楚它是不值得的。
I agree with Matthew that sum should be a local variable, but otherwise, your code looks fine to me as well.
我同意 Matthew 的观点，sum 应该是一个局部变量，但除此之外，您的代码对我来说也很好。
solution without code (just for fun):
没有代码的解决方案（只是为了好玩）：
Using the fact that sum(1+2+3+...+n)= n(n+1)/2, we can derive that the sum of multiples of x below 1000 is floor(1000/x)*(floor(1000/x)+1)/2*x.
使用sum(1+2+3+...+n)=的事实n(n+1)/2，我们可以推导出 x 小于 1000 的倍数之和为floor(1000/x)*(floor(1000/x)+1)/2*x。
The answer we need is the sum of multiples of 3 below 1000, plus the sum of multiples of 5, minus the sum of multiples of 15 (which would otherwise be doublecounted).
我们需要的答案是 1000 以下 3 的倍数之和，加上 5 的倍数之和，减去 15 的倍数之和（否则会被重复计算）。
There are 999/3 = 333 multiples of 3 below 1000, 999/5 = 199 multiples of 5 below 1000, and 999/15 = 66 multiples of 15 below 1000
1000以下有999/3=3的333个倍数，1000以下有999/5=5的199个倍数，1000以下有999/15=15的66个倍数
So the sum of all multiples of 3 below 1000 = 333*334/2*3 = 166833, the sum of multiples of 5 below 1000 = 199*200/2*5 = 99500, and the sum of multiples of 15 below 1000 = 66*67/2*15 = 33165
所以1000以下所有3的倍数之和=333*334/2*3=166833，1000以下5的倍数之和=199*200/2*5=99500，1000以下15的倍数之和= 66*67/2*15 = 33165
Making the answer 166833 + 99500 - 33165 = 233168
做出答案 166833 + 99500 - 33165 = 233168
回答by Jay
Your solution is the logically simplest and thus easiest to verify. Analytical solutions like Vlad's and Luke's are most efficient.
您的解决方案在逻辑上是最简单的，因此也最容易验证。像 Vlad 和 Luke 的分析解决方案是最有效的。
But for what it's worth, my first thought when I saw the problem was:
但无论如何，当我看到这个问题时，我的第一个想法是：
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;
}
This would be more efficient than your solution as it would skip over numbers we know we're not interested in. And it's still intuitively pretty obvious how it works.
这将比您的解决方案更有效，因为它会跳过我们知道我们不感兴趣的数字。而且它的工作原理仍然很直观。
A no-loop solution is better, but I post this just because I have a meeting in 5 minutes and I was already here.
无循环解决方案更好，但我发布这个只是因为我在 5 分钟后有一个会议并且我已经在这里了。
回答by Sachithra Sewwandi
I did that using the arithmetic progression with O(1). Here's my solution and it worked for values more that 1000 too till 10^9 like
我使用 O(1) 的算术级数做到了这一点。这是我的解决方案，它也适用于 1000 以上的值，直到 10^9 之类
long sum1=0,sum2=0,sum3=0,sum=0;
long no3=0,no5=0,no15=0;
//find the no of terms
no3=(array[i]-1)/3;
no5=(array[i]-1)/5;
no15=(array[i]-1)/15;
//find the sum of the terms
sum1=no3*(6+(no3-1)*3)/2 ;
sum2=no5*(10+(no5-1)*5)/2;
sum3=no15*(30+(no15-1)*15)/2;
sum=sum1+sum2-sum3;
System.out.println(sum);
}
回答by djjeck
For Project Euler I have this one advice: go functional.
对于 Euler 项目，我有一个建议：去功能化。
I had previously solved about 100 problems in Java, but I had struggled with many along the road, and I had to write a lot of library code. I recently started solving them in Scala, starting from Problem 1 again, and it feels much more natural.
我之前用 Java 解决了大约 100 个问题，但我在路上遇到了很多问题，我不得不编写大量的库代码。我最近开始在 Scala 中解决它们，再次从问题 1 开始，感觉自然多了。
Besides the fact that you can solve the first few problems with just pen and paper, as pointed out on other answers, solving this one using a functional language is very simple and easy to come up with. This is my solution from problem 1:
除了您可以仅用笔和纸解决前几个问题这一事实之外，正如其他答案所指出的那样，使用函数式语言解决这个问题非常简单且易于想出。这是我对问题 1 的解决方案：
object Problem001 {
def main(args: Array[String]) = println(find(1000))
def find(max:Int) =
Stream.from(1) filter (n => n % 3 == 0 || n % 5 == 0) takeWhile (_ < max) sum
}
回答by yash
Vlad's solution rules.
But here' another along the lines of what Jay posted, but with 1 loop
弗拉德的解决方案规则。
但是这里有另一个与 Jay 发布的内容相同的内容，但有 1 个循环
def ProjectEuler1(upper_limit):
num_3mult = (upper_limit-1)//3 # total multiples of 3, less than upper_limit
num_5mult = (upper_limit-1)//5 # total multiples of 5, less than upper_limit
sum_multiples = 0
for i in range(1,num_3mult+1):
sum_multiples += i*3
if i <= num_5mult and i%3!=0: # only add the multiples of 5 which are not multiple of 3 (to avoid adding duplicates)
sum_multiples += i*5
print('Sum of all multiples of 3 and 5 below 1000 = ', sum_multiples, end='\n')
ProjectEuler1(1000)
回答by ChrisOdney
I was solving the problem and came up with the solution that @vlad has mentioned. Quite thrilled about it(never heard of the inclusion-exclusion principle). Here is my code:
我正在解决问题并提出了@vlad 提到的解决方案。对此感到非常兴奋（从未听说过包含-排除原则）。这是我的代码：
public class Prob1 {
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));
}
}
Test:
测试：
public class TestProb1 {
@Test
public void testSumOfMultiples(){
int actual = Prob1.sumOfMultiples(3, 5, 10);
assertEquals(23, actual);
actual = Prob1.sumOfMultiples(3, 5, 30);
assertEquals(195, actual);
actual = Prob1.sumOfMultiples(3, 5, 1000);
assertEquals(233168, actual);
}
}
回答by Shawn
You can solve this in .NET with a single LINQ expression
您可以在 .NET 中使用单个 LINQ 表达式解决此问题
Dim sum = (From num In Enumerable.Range(1, 999)
Where num Mod 3 = 0 OrElse num Mod 5 = 0
Select num).Sum()
回答by Spektre
well the obvious arithmetic series sumation is:
那么明显的算术级数总和是：
int s=0,n,N=1000;
n=(N-1)/ 3; s+= 3*n*(n+1);
n=(N-1)/ 5; s+= 5*n*(n+1);
n=(N-1)/15; s-=15*n*(n+1); s>>=1;
// can further optimize by precomputing N-1, n+1 to some temp vars
// also multiplication can be shift added instead
I saw some suma fors here and why to heck are you people
我在这里看到了一些苏马，为什么你们是人
- use division for suma ???
- use +1 increment for +3i and +5i multiplicants ???
- 对 suma 使用除法？？？
- 对 +3i 和 +5i 乘数使用 +1 增量？？？
try this instead:
试试这个：
int s=0,N=1000;
for (int i=0;i<N;i+=5) s+=i;
for (int i=0,j=0;i<N;i+=3,j++) if (j==5) j=0; else s+=i;
I know is trivial but hopefully helps someone to realize how to write things better.
我知道这是微不足道的，但希望能帮助某人意识到如何写得更好。
