Ich habe gerade damit begonnen, Project Eulers Probleme zu lösen. Auch wenn dieser sehr einfach ist. Ich möchte Ihre Meinung über die beste Lösung sagen.
Wenn wir alle natürlichen Zahlen auflisten unter 10, die ein Vielfaches von 3 oder 5 sind, wir bekommen 3, 5, 6 und 9. Die Summe von diesen Vielfache ist 23.
Finde die Summe aller Vielfachen von 3 oder 5 unter 1000.
So habe ich es codiert:
%Vor% Es sieht gut aus, obwohl ich sum in main setzen würde. Das ist bei einem so einfachen Programm keine große Sache. Aber im Allgemeinen sollten Sie Variablen im engstmöglichen Umfang deklarieren.
Eine bessere Lösung ist eine einfache Anwendung des Einschluss-Ausschluss-Prinzips. Die Summe aller Zahlen, an denen wir interessiert sind, ist (1) die Summe aller durch 3 teilbaren Zahlen, plus (2) die Summe aller durch 5 teilbaren Zahlen, minus (3) die Summe aller durch 15 teilbaren Zahlen Die 3 Summen sind eine Summe einer arithmetischen Progression, die relativ leicht zu finden ist. Im Grunde brauchen Sie keine Schleife.
Die Anzahl der nicht negativen Ganzzahlen, die durch n unter N teilbar sind, ist genau [( N - 1) / n ] + 1. Die maximale Anzahl ist n * ([( N - 1) / n ], also durch die Arithmetik Progressions-Summenformel, ihre Summe ist [( N - 1) / n * * ([( N - 1) / n] ] + 1) * n / 2.
Für unseren Fall haben wir:
Das Endergebnis ist 233168.
Vielleicht gibt es eine noch bessere Lösung.
Obwohl ich sicher bin, dass es eine O (1) -Lösung für dieses Problem gibt, wäre es nicht die Mühe wert herauszufinden, wenn man nur die Antwort für 1000 geben möchte.
Ich stimme Matthew zu, dass die Summe eine lokale Variable sein sollte, aber ansonsten sieht dein Code auch für mich gut aus.
Lösung ohne Code (nur zum Spaß):
Mit der Tatsache, dass sum(1+2+3+...+n) = n(n+1)/2 ist, können wir ableiten, dass die Summe der Vielfachen von x unter 1000 floor(1000/x)*(floor(1000/x)+1)/2*x ist.
Die Antwort, die wir brauchen, ist die Summe der Vielfachen von 3 unter 1000 plus die Summe der Vielfachen von 5 minus der Summe der Vielfachen von 15 (die sonst doppelt gezählt werden würden).
Es gibt 999/3 = 333 Vielfache von 3 unter 1000, 999/5 = 199 Vielfache von 5 unter 1000 und 999/15 = 66 Vielfache von 15 unter 1000
Also die Summe aller Vielfachen von 3 unter 1000 = 333 * 334/2 * 3 = 166833, die Summe der Vielfachen von 5 unter 1000 = 199 * 200/2 * 5 = 99500, und die Summe der Vielfachen von 15 unter 1000 = 66 * 67/2 * 15 = 33165
Antwort machen 166833 + 99500 - 33165 = 233168
Ihre Lösung ist logisch am einfachsten und somit am einfachsten zu überprüfen. Analytische Lösungen wie Vlad's und Luke's sind am effizientesten.
Aber für was es wert ist, war mein erster Gedanke, als ich das Problem sah:
%Vor%Dies wäre effizienter als Ihre Lösung, da es Zahlen überspringen würde, von denen wir wissen, dass sie uns nicht interessieren. Und es ist immer noch intuitiv ziemlich offensichtlich, wie es funktioniert.
Eine No-Loop-Lösung ist besser, aber ich poste dies, nur weil ich ein Meeting in 5 Minuten habe und ich schon hier war.
Ich habe das mit der arithmetischen Progression mit O (1) gemacht. Hier ist meine Lösung und es funktioniert für Werte mehr als 1000 zu 10 ^ 9 wie
%Vor%Für Project Euler habe ich diesen einen Ratschlag: Geh funktional.
Ich hatte zuvor etwa 100 Probleme in Java gelöst, aber ich hatte mit vielen unterwegs gekämpft, und ich musste viel Bibliothekscode schreiben. Ich habe vor kurzem begonnen, sie in Scala zu lösen, angefangen mit Problem 1, und es fühlt sich viel natürlicher an.
Neben der Tatsache, dass Sie die ersten Probleme mit nur Stift und Papier lösen können, wie in anderen Antworten erwähnt, ist es sehr einfach und leicht, dieses mit einer funktionalen Sprache zu lösen. Dies ist meine Lösung von Problem 1:
%Vor%Ich habe das Problem gelöst und die Lösung gefunden, die @vlad erwähnt hat. Ziemlich begeistert davon (noch nie vom Inklusion-Exklusion-Prinzip gehört). Hier ist mein Code:
%Vor%Test:
%Vor%Nun ist die naheliegende arithmetische Reihenzusammenfassung:
%Vor%Ich habe hier einige Suma Fors gesehen und warum sind Sie Leute?
versuche dies stattdessen:
%Vor%Ich weiß, es ist trivial, aber hoffentlich hilft jemandem zu erkennen, wie man Dinge besser schreibt.
Dieser Algorithmus würde gut funktionieren, aber denken Sie nicht, dass es kein optimaler Algorithmus ist.
Hier würde eine einfache Logik des Findens von Summe von n Elementen ausreichen und dieser Algorithmus würde auch mit riesigen Daten arbeiten.
Hier ist ein Code-Ausschnitt aus meinem Programm in meinem Blog CodeForWin - Projekt Euler 1: Multiples von 3 und 5
%Vor%Dieser Algorithmus berechnet
sumvonn=1000000000000im Bruchteil von Millisekunden.
Tags und Links java