@VicariousVirus: Zeig bitte mal ein solches Array mit 4-5 Beispielwerten, damit klar wird, was genau gemeint ist.
Java 2d-Array doppelte Werte suchen
![]() Anmeldungsdatum: Beiträge: 2133 Wohnort: Gelsenkirchen |
|
||||
(Themenstarter)
![]() Anmeldungsdatum: Beiträge: Zähle... Wohnort: Berlin |
Konkret geht es um die Darstellung von Kubikzahlen (n^3) aus zwein verschiedenen int/long Werten welche als Summe von i*i*i+j*j*j (1^3+1^3=2; etc.) hervorgehen. Und es sollen also die Summen heraugefischt werden, welche sich sich aus zwei verschiedenen Summanden zur selben Summe bilden. Und das nicht per bruteforce...
|
||||
![]() Anmeldungsdatum: Beiträge: 7174 Wohnort: Wolfen (S-A) |
Ok, also seien jetzt mal Deine i-Werte die 1. Koordinate Deines Arrays, und die j-Werte die 2. Koordinate Deines Arrays, und die Berechnungsformel lautet: ergebnis= i^3 + j^3 Dann würde es doch völlig reichen, wenn Du dann das Ergebnisarray genau umgekehrt bildest mit der Formel: ergebnis[i^3 + j^3]= (i,j) wobei der Index dieses Arrays einfach der berechnete (Long-)Integer-Wert ist. So meinte ich das mit dem assoziativen Array ... track |
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
Es mag Dich überraschen, aber die meisten Programmierer zeigen ein sehr hohes Interesse an schnellen Lösungen und ein geringes an korrekten. Dabei ist eine schnelle, aber inkorrekte Lösung eigentlich keine Lösung, und langsame Lösung findet das Ergebnis schneller als die schnellste falsche. Ich habe jetzt aber auch nicht verstanden - stehen in den Zellen des Arrays Zahlenpaare? |
||||
Projektleitung
Anmeldungsdatum: Beiträge: 13215 |
Wenn ich die Aufgabenstellung richtig verstanden habe, geht es darum aus einer Menge von 2-Tupeln diejenigen zu finden, die dasselbe Ergebnis von Das würde ich so angehen: ... Edit: zu kompliziert gedacht. |
||||
(Themenstarter)
![]() Anmeldungsdatum: Beiträge: 27 Wohnort: Berlin |
Leider habe ich keinen Plan von Hashes, das ist die erste Aufgabe die wir für Java bekommen haben... Wenn ich wüsste, dass es man alle Werte auch in einen 1d Array bekommt, könnte man den sortieren und sich einfach die Werte rausgebenlassen, welche vier mal hintereinander gleich groß sind. Allerdings weiß ich nicht, wie ich so einen Array bauen kann. |
||||
Projektleitung
Anmeldungsdatum: Beiträge: 13215 |
So nochmal: Das würde ich so angehen: Eine Klasse schreiben, die zwei Der Algorithmus sähe dann in Pseudocode so aus: Map<Long, Set<Paar>> map = new HashMap<Long, Set<Paar>>() for(int i = 1; i < M; ++i) { for (int j = 1; j < N; ++j) { Paar p = new Paar(i, j) Long key = p.calculate() Set<Paar> s = map.get(key) if ( s == null ) { s = new HashSet<Paar>() map.put(key, s) } s.add(p) } } for (Set<Paar> s : map.values() ) { if (s.size() > 1) { System.out.println(s); } } track hat ja schon in die Richtung gedeutet. Man kann noch ein bisschen optimieren. Z.B. wenn man dafür sorgt, dass N ⇐ M, kann man j bis i laufen lassen. Das ändert nichts am Suchraum, vermindert aber die Schleifendurchläufe. Ciao robert |
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
Das ist Deine erste Javaaufgabe überhaupt, und ist Java auch Deine erste Programmiersprache? Wo ist das Aufgabe - Schule, Uni, ...? Was habt Ihr schon behandelt, was ist das Thema der Stunde gewesen? Wenn Umgang mit Arrays das Thema ist, dann sieht die Lösung anders aus als bei Performanceoptimierung, beim Thema Speicheroptimierung, Algorithmen, ... |
||||
![]() Anmeldungsdatum: Beiträge: 2133 Wohnort: Gelsenkirchen |
Ich glaube, ich verstehe es jetzt: Es ist trivial, dass Ich denke dann mal, dass der Ansatz, mit einer Schleife über alle Möglichkeiten zu gehen, eher unter Brute Force fällt. Man soll vermutlich systematischer an die Aufgabe rangehen und einen klugen Algorithmus zur korrekten Berechnung ermitteln. Also würde ich jetzt zumindest so sehen. Vielleicht deute ich auch zuviel in die Aufgabenstellung hinein... EDIT: Mag blöd klingen, aber gibt es dafür überhaupt eine Lösung? |
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
Oh, irgendwie habe ich das entscheidende Posting auf Seite 2 übersehen, dass es um i³ + j³ = k³ + l³ geht. Das ist in der Tat eine Aufgabe, bei der Performance eine Rolle spielen könnte. Aber wenn i < j und k < l gilt, und wir für ein 2 Paare (i,j) (k,l) diese immer so sortieren, dass auch i < k gilt (wenn i == k wäre dann wäre j == l und die Bed. verletzt) - also wenn i < k gilt muss auch j > l gelten. Die Werte für x³ mit x in {i, j, k, l} lassen sich puffern, bzw. man kann ein großes Array machen, wo x³ in den Feldern des Arrays steht, und das Array so groß wie es in den Speicher passt bei long Werten oder BigInt. So ad hoc fällt mir noch ein, dass die Summe 2er gerader Zahlen wieder gerade ist, die 2er ungerader auch, die 2er gemischter Zahlen immer ungerade. Die 3. Potenz einer ungeraden Zahl ist immer ungerade. Das kann man beim Summieren wohl berücksichtigen.
|
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
Desweiteren kann man noch festhalten, dass dann auch i < k < l < j gelten muss, denn wenn i und j < k wären, und l > k, dann ist die rechte Summe immer größer als die linke. Auch gilt, dass wenn a < b dass dann auch a³ < b³ für positive a, b ist. Wenn a also der kleinste Wert ist, dann muss b der größte sein. In Scala wäre ein leicht optimierter Brute-force-Code so:
Mit dem Output: 0 11 8 9 (1729 ?= 1729) 0 102 63 93 (1092728 ?= 1092728) 0 149 72 143 (3375001 ?= 3375001) 0 248 134 234 (15438250 ?= 15438250) 0 494 333 437 (121287376 ?= 121287376) 1 15 8 14 (4104 ?= 4104) 1 33 14 32 (39312 ?= 39312) 1 23 17 19 (13832 ?= 13832) 1 88 40 85 (704977 ?= 704977) 1 149 82 140 (3375008 ?= 3375008) 1 126 94 105 (2048391 ?= 2048391) 1 205 127 187 (8741824 ?= 8741824) 1 299 145 287 (27000008 ?= 27000008) 1 465 164 458 (101194704 ?= 101194704) 1 384 251 344 (57066633 ?= 57066633) 1 497 269 469 (123506000 ?= 123506000) 2 59 21 58 (216027 ?= 216027) 2 35 26 29 (46683 ?= 46683) 2 185 58 183 (6434883 ?= 6434883) 2 357 114 353 (45882739 ?= 45882739) 2 308 191 281 (29503656 ?= 29503656) 2 449 218 431 (91125027 ?= 91125027) 2 413 322 333 (70957971 ?= 70957971) 3 31 17 29 (32832 ?= 32832) 3 67 29 65 (314496 ?= 314496) 3 47 35 39 (110656 ?= 110656) 3 151 40 150 (3511872 ?= 3511872) 3 109 66 100 (1331064 ?= 1331064) 3 177 81 171 (5639816 ?= 5639816) 3 299 165 281 (27000064 ?= 27000064) 3 253 189 211 (16387128 ?= 16387128) 3 411 255 375 (69934592 ?= 69934592) 3 392 281 336 (60698521 ?= 60698521) 4 59 44 49 (216125 ?= 216125) 4 75 47 68 (439101 ?= 439101) 4 309 65 308 (29791125 ?= 29791125) und so weiter. Je nach dem bis zu welcher Größe das laufen soll... - bei mir
|
||||
(Themenstarter)
![]() Anmeldungsdatum: Beiträge: 27 Wohnort: Berlin |
Sanfu1: Du hast es erfasst, die Triviallösungen interessieren eigentlich nicht. Auch wenn sie als Lösung enthalten sein sollten. Es handelt sich dabei Programmierung 1 an einer Uni, Arrays hatten wir bis dato noch gar nicht, außer, dass gesagt wurde, es ist kein primitiver Datentyp sondern ein strukturierter^^ Was nicht gerade hilfreich war. Weiterhin gibt es ein Zeitlimit von max. 5 min in zwei Varianten. Einmal in einer Zzweier-Form und einmal als Dreier (sprich i³+j³+k³<=>sum<=>l³+m³+n³... |
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
5 Minuten kann aber auch, je nach Rechner, mehr oder weniger sein. Insbes. an einem Unirechner. Ich schätze mein Heimlaptop hat ca. 5 Min. für die Zahlen bis 500 gebraucht (model name : Intel(R) Core(TM) Duo CPU T2400 @ 1.83GHz) Kannst Du den Scalacode entschlüsseln? |
||||
![]() Anmeldungsdatum: Beiträge: 2133 Wohnort: Gelsenkirchen |
Das Scala-Programm liefert falsche Ergebnisse. Ich habe mal stichprobenartig nachgerechnet: Nicht eins der Ergebnisse zeigt korrekte Werte, wenn die Gleichung |
||||
![]() Anmeldungsdatum: Beiträge: 17622 Wohnort: Berlin |
Ich habe auch mal eins nachgerechnet, und komme auch auf ein falsches Ergebnis (1 15 8 14). Ah - ich glaube ich habe den Fehler: Im Array speichere ich x³ von 1 beginnend an Pos. 0, statt an 0 beginnend. |