ubuntuusers.de

Java 2d-Array doppelte Werte suchen

Status: Gelöst | Ubuntu-Version: Kein Ubuntu
Antworten |

snafu1

Avatar von snafu1

Anmeldungsdatum:
5. September 2007

Beiträge: 2133

Wohnort: Gelsenkirchen

@VicariousVirus: Zeig bitte mal ein solches Array mit 4-5 Beispielwerten, damit klar wird, was genau gemeint ist.

VicariousVirus

(Themenstarter)
Avatar von VicariousVirus

Anmeldungsdatum:
7. Mai 2011

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...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
  public static void main(String[] args) {
      int M = 10;
      int N = 10;
	int[][] cubic = new int[M][N];
	for(int i =1; i<M;i++)
	    {
		for(int j = 1;j<N;j++)
		    {
			int[] cub_sum = new int[100];
		     cubic[i][j]=i*i*i+j*j*j;  	
		    System.out.print(cubic[i]+" ");
		    System.out.println()

track

Avatar von track

Anmeldungsdatum:
26. Juni 2008

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

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

Beiträge: 17622

Wohnort: Berlin

snafu1 schrieb:

user unknown schrieb:

Von Performance habe ich nichts gelesen.

Super... 😀

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?

rklm Team-Icon

Projektleitung

Anmeldungsdatum:
16. Oktober 2011

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 a^3 + b^3 liefern.

Das würde ich so angehen: ...

Edit: zu kompliziert gedacht.

VicariousVirus

(Themenstarter)
Avatar von VicariousVirus

Anmeldungsdatum:
7. Mai 2011

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.

rklm Team-Icon

Projektleitung

Anmeldungsdatum:
16. Oktober 2011

Beiträge: 13215

So nochmal:

Das würde ich so angehen: Eine Klasse schreiben, die zwei int oder long - sagen wir x und y - enthält. Dabei sicherstellen, dass immer x <= y gilt.

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

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

Beiträge: 17622

Wohnort: Berlin

VicariousVirus schrieb:

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.

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, ...

snafu1

Avatar von snafu1

Anmeldungsdatum:
5. September 2007

Beiträge: 2133

Wohnort: Gelsenkirchen

Ich glaube, ich verstehe es jetzt: Es ist trivial, dass 1³ + 2³ die selbe Summe ergibt wie 2³ + 1³, und über exakt die gleichen Summanden (z.B. bei 1³ + 1³) brauchen wir gar nicht erst zu sprechen. Solche Erkenntnisse zählen also *nicht* als Treffer, sondern man soll vielmehr Fälle finden, wo a³ + b³ = c³ + d³ gilt und wo alle 4 Variablen auf jeden Fall unterschiedlich voneinander sein müssen, richtig?

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?

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

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.

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

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:

1
2
3
4
5
6
7
8
9
val MAX = 500
val arr = (1L to MAX) map {x => x * x * x}
for (a <- 0 to MAX-4;
  c <- a+1 to MAX-3;
  d <- c+1 to MAX-2;
  b <- d+1 to MAX-1;
  s1 = arr(a) + arr(b);
  s2 = arr(c) + arr(d);
  if (s1 == s2)) println (a + "  " + b  + "  " + c  + "  " + d + " (" + s1  + " ?= " + s2 + ")")

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

1
2
3
4
5
6
302  456  393  395 (123262120 ?= 123262120)
305  491  383  449 (147748104 ?= 147748104)
306  425  362  387 (106243219 ?= 106243219)
311  449  337  435 (121496328 ?= 121496328)
345  470  359  462 (145908847 ?= 145908847)
358  459  407  422 (143604279 ?= 143604279)

VicariousVirus

(Themenstarter)
Avatar von VicariousVirus

Anmeldungsdatum:
7. Mai 2011

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³...

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

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?

snafu1

Avatar von snafu1

Anmeldungsdatum:
5. September 2007

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 a³ + b³ = c³ + d³ gelten soll.

user_unknown

Avatar von user_unknown

Anmeldungsdatum:
10. August 2005

Beiträge: 17622

Wohnort: Berlin

snafu1 schrieb:

Das Scala-Programm liefert falsche Ergebnisse. Ich habe mal stichprobenartig nachgerechnet: Nicht eins der Ergebnisse zeigt korrekte Werte, wenn die Gleichung a³ + b³ = c³ + d³ gelten soll.

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.