Java中的Euler程序
我刚开始解决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); } } 它看起来很好，虽然我会把sum放在主要的。 这个简单的程序并不是什么大不了的事。 但一般来说，您应该在尽可能窄的范围内声明变量。
更好的解决方案是包含 – 排除原则的简单应用。 我们感兴趣的所有数字的总和是（1）可被3整除的所有数字的总和加上（2）可被5整除的所有数字的总和减去（3）可被15整除的所有数字的总和。 3个和是算术级数的总和，相对容易找到。 基本上，您不需要循环。
N可以除以N的非负整数的数量正好是[（ N -1）/ n ] + 1.最大这样的数是n *（[（ N -1）/ n ]，因此通过算术级数和公式，它们的和是[（ N -1）/ n ] *（[（ N -1）/ n ] + 1）* n / 2。
对于我们的案例，我们得到：
- 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。
最终结果是233168。
也许存在更好的解决方案。
虽然我确信这个问题有一个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
您的解决方案在逻辑上最简单，因此最容易validation。 像弗拉德和卢克这样的分析解决方案效率最高。
但是对于它的价值，当我看到问题时，我的第一个想法是：
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分钟内开会，而我已经在这里了。
我使用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); }
对于Project Euler，我有一个建议：去function。
我以前在Java中已经解决了大约100个问题，但是我一直在努力解决许多问题。我不得不编写很多库代码。 我最近开始在Scala中解决它们，再次从问题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 }
弗拉德的解决方案规则。
但这里是另一个沿着Jay发布的内容，但有一个循环
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)
我正在解决这个问题，想出了@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)); } }
测试：
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); } }
您可以使用单个LINQ表达式在.NET中解决此问题
Dim sum = (From num In Enumerable.Range(1, 999) Where num Mod 3 = 0 OrElse num Mod 5 = 0 Select num).Sum()
很明显的算术系列是：
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
我在这里看到了一些suma fors，为什么要找人呢
- 使用分区为suma ???
- 对+ 3i和+ 5i乘数使用+1增量???
试试这个：
int s=0,N=1000; for (int i=0;i
我知道这是微不足道的，但希望能帮助别人意识到如何更好地写东西。
我的第一个JAVA课程的第5周…这就是我将如何解决它;）这是一个真正的凯旋门
import java.util.Scanner; public class Counter { public static void main(String args[]) { System.out.println("Enter an integer, and COUNTER will find the sum of all the multiples of THREE and FIVE:"); int entry; Scanner input = new Scanner(System.in); entry = input.nextInt(); int three = 0; int threeOut = 0; int threeOpTot = (entry / 3); int threeOp = 0; while( threeOp < threeOpTot) { three = three + 3 ; threeOut = three + threeOut ; threeOp += 1; System.out.println(threeOp + " times 3 is " + three + ". "); System.out.println(" " + threeOut + ", is the total sum of " + threeOp + "/" + threeOpTot + " threes"); } int five = 0; int fiveOut = 0; int fiveOpTot = (entry / 5); int fiveOp = 1; while( fiveOp < fiveOpTot) { five = five + 5 ; fiveOut = five + fiveOut ; fiveOp += 1 ; System.out.println(threeOp + " times 3 is " + three + ". "); System.out.println(" " + threeOut + ", is the total sum of " + threeOp + "/" + threeOpTot + " threes"); } int fifteen = 0; int fifteenOut = 0; int fifteenOpTot = (entry / 15); int fifteenOp = 0; while( fifteenOp < fifteenOpTot) { fifteen = fifteen + 15 ; fifteenOut = fifteen + fifteenOut ; fifteenOp += 1 ; System.out.println(fifteenOp + " times fifteen is " + fifteen + "."); System.out.println(" " + fifteenOut + ", is the total sum of " + fifteenOp + "/" + fifteenOpTot + " fifteens"); } System.out.println("The final values of threes' are " + (threeOut) ); System.out.println("The final values of five' are " + (fiveOut) ); System.out.println("The sum of the over-lapping 15 factors are " + (fifteenOut) ); System.out.println("Grand total: " + (fiveOut + threeOut - fifteenOut) ); } }
该算法可以正常工作但你不认为它不是一个最佳算法。
在这里找到n个元素之和的简单逻辑就可以解决这个问题，而且这个算法也适用于大量数据。
这是我的博客CodeForWin程序中的代码片段- Project Euler 1：3和5的倍数
n--; //Since we need to compute sum of multiples below n if(n>=3) { totalElements = n/3; sum += (totalElements * ( 3 + totalElements*3)) / 2; } //Check if n is more than or equal to 5 then compute sum of all elements //divisible by 5 and add to sum. if(n >= 5) { totalElements = n/5; sum += (totalElements * (5 + totalElements * 5)) / 2; } //Check if n is more than or equal to 15 then compute sum of all elements //divisible by 15 and subtract from sum. if(n >= 15) { totalElements = n/15; sum -= (totalElements * (15 + totalElements * 15)) / 2; } System.out.println(sum);
该算法以毫秒为单位计算
n=1000000000000的和。
public static void main(String[] args) { int sum = 0; int i = 0; while (i < 1000) { if (i % 3 == 0 || i % 5 == 0) { sum = sum + i; } i++; } System.out.println("Sum is " + sum); }