ich schreibe gerade an einem Programm, das die 5 kleinsten natürlichen Zahlen ausrechnet, auf 3 unterschiedliche Wege durch die Kombination 2er Kubikzahlen gebildet werden können.
Mein Programm sieht folgendermaßen aus:
Ich habe 4 For-Schleifen ineinander verknüpft und berechne so, wann zwei Summen zweier Kubikzahlen Identisch sind, setze dann die Variable zweimal[] auf true, bzw. wenn das schon einmal geschehen ist, dreimal[] auf true. Mit zwei verschiedenen Kombinationen zweier Kubikzahlen ist mir das mit einem ähnlichen Programm bereits gelungen, hier komme ich jedoch zu keinem Ergebnis und er rechnet jetzt schon bestimmt 10 Minuten an der ersten Zahl.
Habe ich einen logikfehler oder ist mein Ansatz einfach nicht so schlau gewählt? Das ist das erste Programm das ich in Java schreibe und ich fühle mich leicht überfordert
public class dreier {
public static void main(String[] args){
int num=1;
int lauf = 1000;
int unsort[] = new int [1000000];
boolean zweimal[] = new boolean [999999999];
boolean dreimal[] = new boolean [999999999];
for (int l1=1; l1<lauf; l1++){
for (int l2=1; l2<lauf; l2++){
for (int r1=1; r1<lauf; r1++){
for (int r2=1; r2<lauf; r2++){
int links = dr(l1) + dr(l2);
int rechts = dr(r1) + dr(r2);
if ( (links == rechts) && (r1!=l1)&(r1!=l2) && (dreimal[links]=false) ){
if (zweimal[links]==true){
dreimal[links] = true;
unsort[num] = links;
System.out.println(unsort[num]);
num++;
}
zweimal[links]=true;
}
}
}
}
}
}
public static int dr(int n){
return n*n*n;
}
}
Als erstes fällt auf, dass die Verschachtelungstiefe extrem groß ist. Da solltest du noch einiges in weitere Methoden auslagern.
Hast du schon einen vernünftigen Algorithmus vorgegeben bekommen, oder sollst du dir selbst einen ausdenken?
Der von dir implementierte Algorithmus ist wahrscheinlich so ineffizient, dass er sich totrechnet.
[QUOTE=cmrudolph]Als erstes fällt auf, dass die Verschachtelungstiefe extrem groß ist. Da solltest du noch einiges in weitere Methoden auslagern.
[/quote]
Verringert das den Rechenaufwand? Also wenn ich die Variable lauf auf 300 setze, dann prüft er ja die kombinationen bis zur zahl 300^3 und kommt auch in vertretbarer Zeit zu Ende, jedoch zu keiner Lösung.
[QUOTE=cmrudolph;75304]
Hast du schon einen vernünftigen Algorithmus vorgegeben bekommen, oder sollst du dir selbst einen ausdenken?
Der von dir implementierte Algorithmus ist wahrscheinlich so ineffizient, dass er sich totrechnet.[/QUOTE]
Wir haben da nichts vorgegeben bekommen. Und ja, mein Algorithmus ist relativ banal, mir fällt nur auch nix besseres ein. Wenn ihr Ideen habt, nur zu Wie gesagt, mit 2 Kombinationen war das kein Ding.
Nein, aber es erhöht die Übersicht, sodass man besser versteht, was der Algorithmus macht
Das meinte ich mit Verschachtelungstiefe auch nicht, falls du das so verstanden haben solltest. Ich meinte mit Verschachtelungstiefe die Anzahl ineinander verschachtelter for-Schleifen.
Beim Drüberschauen fällt zumindest schonmal dreimal[links]=false
ins Auge. Das ist keine Abfrage, sondern eine Zuweisung. Es müßte dreimal[links]==false
bzw. besser gleich !dreimal[links]
heißen.
Damit gibt er zwar etwas aus, genaugenommen http://oeis.org/A050794 , aber … den Ansatz habe ich nicht direkt nachvollzogen - dieses ‘links’ und ‘rechts’ und “(r1!=l1)&(r1!=l2)” sieht etwas unübersichtich aus, und die riesen-Arrays sind ziemlich suspekt. Vielleicht eher sowas wie
import java.util.HashSet;
import java.util.Set;
public class Dreier {
public static void main(String[] args){
int lauf = 1000;
Set<Integer> unsort = new HashSet<Integer>();
Set<Integer> zweimal = new HashSet<Integer>();
Set<Integer> dreimal = new HashSet<Integer>();
for (int l1=1; l1<lauf; l1++){
for (int l2=1; l2<lauf; l2++){
for (int r1=1; r1<lauf; r1++){
for (int r2=1; r2<lauf; r2++){
int links = dr(l1) + dr(l2);
int rechts = dr(r1) + dr(r2);
if ( (links == rechts) && (r1!=l1)&(r1!=l2) && (!dreimal.contains(links)) ){
if (zweimal.contains(links)){
dreimal.add(links);
unsort.add(links);
System.out.println(links);
}
zweimal.add(links);
}
}
}
}
}
}
public static int dr(int n){
return n*n*n;
}
}
verwenden…
*** Edit ***
Hab nochmal geschaut: In der aktuellen Version rechtfertigt er die “1729” wenn ich das richtig sehe durch die Summen der Kubikzahlen von 1,12 und 9,10 und 10,9 - aber vermutlich sollten 9,10 und 10,9 NICHT als “unterschiedlich” angesehen werden. Ich komme mit einem anderen Test auf
result : 87539319 from [[255, 414], [228, 423], [436, 167]]
als erstes Ergebnis. Kann mich aber auch täuschen.
Ich habe grad mal einen Algorithmus durchimplementiert, der mir die Zahlen ausgibt. Er hat bei mir eine Laufzeit von ca. 100ms. Ich beschreibe ihn dir mal, sodass du ihn dann vielleicht selbst umsetzen kannst.
- gehe in einer Schleife alle Kubikzahlen durch, bis 5 Lösungen gefunden wurden, nenne die aktuelle Kubikzahl "kandidat"
- gehe in einer Schleife durch alle anderen bisher gefundenen Kubikzahlen, nenne diese jeweils "kubikzahl"
- bilde die Summe aus kandidat und kubikzahl und zähle für den gefundenen Wert einen Zähler hoch
- ist dieser Zähler >= 3, ist der gefundene Wert ein Lösungseintrag
Um die Vorkommen zu zählen, bietet sich ein Multiset aus der guava Bibliothek an.
Alternativ funktioniert auch Map<Integer, Integer>
wobei der Schlüssel die aufsummierte Zahl ist und der Wert die Anzahl der Vorkommnisse.
Einmal mit ganz elementaren Mitteln - keine Collections, keine Objekte, nur ein paar Arrays und Schleifen:
Fülle ein “genügend langes” Array mit den Kubikzahlen
Fülle ein zweites Array mit den Summen aus zwei Kubikzahlen, wobei der erste Summand immer kleiner gleich dem zweiten ist (Knobelfrage: wie lang ist dann dieses Array?)
Sortiere das zweite Array
Gehe das zweite Array einmal durch und gib alle Werte aus, die dreimal hintereinander stehen
Das sind vier einfache Schritte, für die du jeweils eigene Methoden schreiben kannst - das wird so wesentlich übersichtlicher. Außerdem brauchst du nur an einer Stelle eine geschachtelte Schleife, und die Java-Bibliotheken können dir das Sortieren abnehmen.
Bitte versuche es selbst, bevor du die “Lösung” durchliest.
public class TripleCubeSum {
private static long[] cubes;
private static long[] cubeSums;
public static void main(String[] args) {
fillCubes(10000);
fillCubeSums();
java.util.Arrays.sort(cubeSums);
findTriples();
}
public static void fillCubes(int maximum) {
cubes = new long[maximum];
for (int i = 0; i < maximum; i++ ) {
cubes** = 1L * i * i * i;
}
}
private static void fillCubeSums() {
int maximum = cubes.length;
cubeSums = new long[maximum * (maximum + 1) / 2];
int k = 0;
for(int i = 0; i < cubes.length; i++) {
for(int j = 0; j <= i; j++) {
cubeSums[k++] = cubes** + cubes[j];
}
}
}
private static void findTriples() {
for(int i = 0; i < cubeSums.length - 3; i++) {
if (cubeSums** == cubeSums[i+1] && cubeSums** == cubeSums[i+2]) {
System.out.println(cubeSums**);
}
}
}
}
[ot]Wer schreibt denn solche Folgen auf? :eek:[/ot]
Kleines Fehlerchen noch in Zeile 34: das muss for(int i = 0; i < cubeSums.length - 2; i++) { heißen, ansonsten wird ein Tripel, das per Zufall ganz am Ende des Arrays liegt, nicht ausgegeben.
*** Edit ***
Die kleine „Optimierung“ im verlinkten Algorithmus find ich geschickt, da wird Zeile 35 zu: if (cubeSums** == cubeSums[i+2]) {
Wie gesagt, mit 2 Kombinationen war das kein Ding.