Arrays

1. Arrays

Arrays sind wichtige Datenstrukturen, die auch indirekt in Java auftauchen, etwa bei der erweiterten for-Schleife oder variablen Argumentlisten. Dieses Kapitel enthält Aufgaben zum Aufbau von Arrays, zum Ablaufen von Arrays und Fragen nach Algorithmen, etwa zur Suche von Elementen in einem Array.

Voraussetzungen

Arrays anlegen, abfragen, füllen können
Arrays mit erweiterter for-Schleife ablaufen können
ein- und mehrdimensionale Arrays nutzen können
variable Argumentlisten aufbauen können
Utility-Methoden der Klasse Arrays kennen

Verwendete Datentypen in diesem Kapitel:

Noch mehr Aufgaben findest du im Buch: ›Captain CiaoCiao erobert Java: Das Trainingsbuch für besseres Java. 300 Java-Workshops, Aufgaben und Übungen mit kommentierten Lösungen‹

1.1. Eindimensionale Arrays

Ein Array ist eine Sammlung gleichartiger Elemente. Eindimensionale Arrays enthalten direkt die Elemente und keine weiteren Unter-Arrays.

1.1.1. Arrays ablaufen und Windgeschwindigkeit, Windrichtung ausgeben ⭐

Captain CiaoCiao segelt über das Meer, der Wind bläst von allen Seiten. Er muss die Windgeschwindigkeit und Windrichtung immer im Blick haben.

Aufgabe:

Deklariere zwei Arrays int[] windSpeed und int[] windDirection.
Initialisiere beide Arrays je mit drei ganzzahligen Zufallszahlen (prinzipiell sollte die Anzahl beliebig sein), wobei die Windstärke zwischen 0 und (kleiner) 200 km/h und die Windrichtung zwischen 0 und (kleiner) 360 Grad liegen kann.
Laufe mit einer Schleife über das Array und gib alle Pärchen kommasepariert aus.

Beispiel:

Enthält z. B. das Array windSpeed die Werte {82, 70, 12} und das Array windDirection die Werte {12, 266, 92}, soll die Ausgabe auf dem Bildschirm sein:
```
Wind speed 82 km/h and wind direction 12°, Wind speed 70 km/h and wind direction 266°, Wind speed 12 km/h and wind direction 92°
```

Hinweis: Bedenke, dass die Segmente mit einem Komma getrennt werden und am Ende kein Komma steht.

Lösungsvorschlag

1.1.2. Konstante Umsatzsteigerung feststellen ⭐

Am Ende eines Monats bekommt Captain CiaoCiao die Umsätze gemeldet, die er und seine Crew — sagen wir mal — erwirtschaftet haben. In der monatlichen Liste ist vermerkt, wie der Gewinn an einem Tag ausfiel. Sie hat dieses Format:

//                Tag    1,    2,   3,    4,    5 ... bis maximal 31
int[] dailyGains  = { 1000, 2000, 500, 9000, 9010 };

Captain CiaoCiao ist mit den Zahlen zufrieden, und er möchte eine Belohnung zahlen, wenn Gewinne über 5 % gestiegen sind. Von 1000 auf 2000 ist ein satter Sprung um 100 %, von 500 auf 9000 ebenso, doch definitiv nicht von 2000 auf 500 und auch nicht von 9000 auf 9010.

Aufgabe:

Schreibe eine Methode int count5PercentJumps(int[]), die die Anzahl der Umsatzsprünge liefert. Ein Umsatzsprung ist dann gegeben, wenn der Umsatz 5 % über dem des Vortags lag.
Das übergebene Array darf nicht null sein, andernfalls folgt eine Ausnahme.

Lösungsvorschlag

1.1.3. Punktefelder ⭐

Welche Ausgabe ist zu erwarten?

Point[] points = { null, null, null, null };
Point p = new Point();
p.setLocation( 1, 2 );
points[ 0 ] = p;
p.setLocation( 3, 4 );
points[ 1 ] = p;
Point q = points[ 1 ];
q.setLocation( 5, 6 );
points[ 2 ] = points[ 3 ] = q;
System.out.println( Arrays.toString( points ) );

1.1.4. Aufeinanderfolgende Strings suchen und feststellen, ob Salty Snook kommt ⭐

Bonny Brain beobachtet die Flaggen der vorbeiziehenden Schiffe, denn sie wartet auf Salty Snook. Sie schaut sich jede Flagge an und weiß, dass Salty Snook nie alleine kommt, sondern sich in einem Konvoi von vier Schiffen bewegt. Die Flaggen selbst kennt sie nicht, nur weiß sie, dass alle die gleiche Aufschrift haben.

Search consecutive strings and determine if Salty Snook is coming

Aufgabe:

Schreibe eine neue Methode isProbablyApproaching(String[] signs), die dann true zurückliefert, wenn es im Array vier gleiche Kürzel hintereinander gibt. Bedenke, dass man Strings mit equals(…) vergleicht.
Das übergebene Array darf nicht null sein, und kein Element im Array darf null sein.

Beispiel:

String[] signs1 = { "F", "DO", "MOS", "MOS", "MOS", "MOS", "WES" };
System.out.println( isProbablyApproaching( signs1 ) );   // true

String[] signs2 = { "F", "DO", "MOS", "MOS", "WES", "MOS", "MOS" };
System.out.println( isProbablyApproaching( signs2 ) );  // false

Lösungsvorschlag

1.1.5. Array umdrehen ⭐

Charlie Creevey macht für Captain CiaoCiao die Finanzen. Doch statt die Einnahmen aufsteigend zu sortieren, hat er sie absteigend sortiert. Daher muss die Liste umgedreht werden.

Ein Array umzudrehen bedeutet, dass das erste Element mit dem letzten Element vertauscht wird, das zweite mit dem zweitletzten usw.

Aufgabe:

Schreibe eine neue statische Methode reverse(…), die ein gegebenes Array umdreht:
```
public static void reverse( double[] numbers ) {
  // TODO
}
```
Die Operation soll in place sein, also das übergebene Array ändern. Die Methode reverse(…) soll kein neues Array anlegen.
Die Übergabe null führt zu einer Ausnahme.

Beispiel:

{ } → { }
{ 1 } → { 1 }
{ 1, 2 } → { 2, 1 }
{ 1, 2, 3 } → { 3, 2, 1 }

Die Darstellung in den geschweiften Klammen ist nur symbolisch.

Lösungsvorschlag

1.1.6. Das nächste Kino finden ⭐⭐

Die Klasse java.awt.Point repräsentiert Punkte mit x/y-Koordinaten. Diese lassen sich gut für Positionen einsetzen.

Im Kino läuft die Neuverfilmung »Unter der Flagge der Freibeuter« an, die Captain CiaoCiao unbedingt sehen muss. Doch wo befindet sich das nächste Kino?

Aufgabe:

Gegeben ist eine Menge von Point-Objekten in einem Array points für die Kinopositionen.
```
Point[] points = { new Point(10, 20), new Point(12, 2), new Point(44, 4) };
```
Schreibe eine Methode double minDistance(Point[] points, int size), die den Abstand des Punktes zurückliefert, der die geringste Distanz zum Nullpunkt besitzt. Mit size können wir bestimmen, wie viele Elemente des Arrays betrachtet werden sollen, damit das Array auch prinzipiell größer sein kann.
null als Übergabe ist nicht erlaubt, auch dürfen die Punkte nicht null sein; es muss eine Ausnahme ausgelöst werden.
Was müssen wir ändern, wenn der Rückgabetyp Point ist, also der Punkt selbst mit dem kleinsten Abstand zurückgegeben werden soll?

Studiere die Javadoc zu java.awt.Point, um herauszufinden, ob der Punkt selbst Abstände zu anderen Koordinaten berechnen kann.

Lösungsvorschlag

1.1.7. Süßigkeitenladen überfallen und fair aufteilen ⭐⭐

Captain CiaoCiao überfällt mit seinen Kindern Junior und Jackie einen Süßigkeitenladen. Die Süßigkeiten stehen in einem langen Regal, und jedes Produkt hat ein Gewicht. Die Daten liegen als Array vor:

int[] values = { 10, 20, 30, 40, 40, 50 };

Junior und Jackie stellen sich links und rechts an entgegengesetzten Enden des Regals auf, und da Captain CiaoCiao beide Kinder gleich lieb hat, sollen sie am Ende auch gleich viel mit nach Hause nehmen. Captain CiaoCiao zeigt im Regal auf eine Süßigkeit, sodass alle Produkte links davon zu Junior gehen und alle Produkte rechts von der Position (inklusive dem gezeigten) für Jackie sind.

Der Captain weiß zwar, was im Regal steht, aber nicht, ab welcher Position links und rechts die gleiche Summe entsteht. Abweichungen von 10 % sind für die Kinder in Ordnung. Für den Unterschied wollen wir auf folgende Formel für die relative Differenz zurückgreifen:

private static int relativeDifference( int a, int b ) {
  if ( a == b ) return 0;
  int absoluteDifference = Math.abs( a - b );
  return (int) (100. * absoluteDifference / Math.max( a, b ));
}

Aufgabe:

Schreibe eine Methode int findSplitPoint(int[]), die den Index im Array findet, bei dem links und rechts fair geteilt werden kann. Irgendeine Lösung reicht, es sind nicht alle Lösungen nötig.
Falls es keine faire Teilung gibt, soll eine Methode -1 liefern.

Beispiele:

10 + 20 + 30 + 40 ≈ 40 + 50, denn 100 ≈ 90, und der Index für die Rückgabe ist 4
10 20 30 40 40 100 führt zu -1, denn es gibt keine gültige Partitionierung

Lösungsvorschlag

1.2. Erweiterte for-Schleife

Sollen Arrays ab dem ersten Element abgelaufen werden, so lässt sich dafür gut eine erweiterte for-Schleife mit unsichtbarem Schleifenzähler nutzen. Das spart Code ein.

In den folgenden Aufgaben können stellenweise erweiterte for-Schleifen eingesetzt werden.

1.2.1. Zahlen gut geschüttelt ⭐⭐

In Würfelbecher vom Bonny Brain befinden sich fünf Spielwürfel mit den Ziffern 1 bis 6. Nach ausgiebigem Schütteln purzeln die Würfel auf den Tisch und offenbaren ihre Augenzahlen.

Aufgabe:

Schreibe eine Methode int[] shuffleDice(), die ein int-Array mit 5 zufälligen Zahlen liefert, die zwischen 1 und 6 liegen.
Schreibe eine Methode isHomogeneous(int[] values), die testet, ob alle Werte im Array gleich sind. (Das englische Wort homogeneous kann man mit einheitlich/gleichartig/gleichwertig übersetzen.) Prinzipiell darf das Array beliebig groß sein.
Schreibe eine Methode int[] occurrences(int[] values), die ein neues Array der Größe 6 liefert, das anzeigt, welche Augenzahl wie oft vorkommt.
Schreibe eine Methode isFullHouse(int[] values), die prüft, ob drei Würfel den gleichen Wert und zwei andere Würfel einen anderen gleichen Wert haben. Bei {1, 1, 1, 2, 2} liegt ein solcher Fall zum Beispiel vor.
Schreibe eine Methode void printDiceValues(int[] points), die die Augenzahlen wie folgt auf den Bildschirm schreibt:
- die Zahlen werden aufsteigend sortiert
- die Zahlen werden in Gruppen zusammengefasst
- statt der Augen als einfache Zahlen auf dem Bildschirm, nutze die Unicode-Symbole ⚀ (Unicode-Zeichen U+2680), ⚁ (U+2681), ⚂ (U+2682), ⚃ (U+2683), ⚄ (U+2684), ⚅ (U+2685).

Wir können annehmen, dass die Methoden immer mit korrekten Werten aufgerufen werden, also das Array nie null ist, die Anzahl Elemente immer korrekt ist und die Werte immer in den Wertebereichen liegen.

Beispiele:

isHomogeneous(new int[]{ 1, 1, 1, 1, 1 }) liefert true.
isHomogeneous( new int[]{ 1, 1, 1, 2, 2 } ) liefert false.
occurrences( new int[]{ 1, 1, 2, 4, 3 }) liefert ein Array mit den Werten { 2, 1, 1, 1, 0, 0 }.
isFullHouse(new int[]{ 1, 1, 1, 2, 2 }) liefert true.
isFullHouse(new int[]{ 1, 1, 1, 1, 1 }) liefert false.
printDiceValues(shuffleDice()) liefert die Ausgabe 2 × ⚁, 2 × ⚃, ⚅

Lösungsvorschlag

1.2.2. Berge zeichnen ⭐⭐

Für die nächste Schatzsuche müssen Bonny Brain und die Crew über Berge und Hügel gehen. Sie bekommt vorher die Höhenmeter mitgeteilt und möchte sich vorher einen Eindruck vom Profil machen.

Aufgabe:

Schreibe ein Programm mit einer Methode printMountain(int[] altitudes), die ein Array mit Höhenmetern in eine ASCII-Darstellung umsetzt.
Die Höhe soll darstellt werden über ein Multiplikationszeichen * in genau dieser Höhe von einer Grundlinie. Die Höhen können beliebig sein, aber nicht negativ.

Beispiel:

Das Array { 0, 1, 1, 2, 2, 3, 3, 3, 4, 5, 4, 3, 2, 2, 1, 0 } soll darstellt werden als:
```
5          *
4         * *
3      ***   *
2    **       **
1  **           *
0 *              *
```
Die erste Spalte dient der Verdeutlichung und muss nicht umgesetzt werden.

Optionale Erweiterung:

Deute statt mit * mit den Symbolen /, \, - und ^ an, ob wir aufsteigen, absteigen, auf einem Plateau sind oder an der Spitze stehen.
```
5          ^
4         / \
3      --/   \
2    -/       -\
1  -/           \
0 /              \
```

Lösungsvorschlag, Lösungsvorschlag mit Ergänzung

1.3. Zwei- und mehrdimensionale Arrays

Ein Array kann in Java Verweise auf andere Arrays enthalten, und so definiert man in Java mehrdimensionale Arrays. In Java gibt es keine echten zweidimensionalen Arrays; zweidimensionale Arrays sind nichts anderes als Arrays, die Unter-Arrays referenzieren, und die Unter-Arrays könnten unterschiedlich lang sein.

1.3.1. Mini-Sudoku auf gültige Lösung prüfen ⭐⭐

Da Überfälle ziemlich anstrengend sind, braucht Bonny Brain einen Ausgleich und beschäftigt sich mit Sudoku. Ein Sudoku-Spiel besteht aus 81 Feldern in einem 9-×-9-Gitter. Das Gitter lässt sich in neun Blöcke zerlegen, jeder Block ist ein zweidimensionales Array der Größe 3 × 3. In jedem dieser Blöcke muss jede Zahl von 1 bis 9 genau einmal vorkommen — keine darf fehlen.

Aufgabe:

Schreibe ein Programm, das ein zweidimensionales Array mit neun Elementen daraufhin testet, ob alle Zahlen von 1 bis 9 vorkommen.
Fehlende Elemente sollen gemeldet werden.

Beispiel:

Das folgende Array ist eine gültige Sudoku-Belegung:

int[][] array = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 }
};

Das folgende Array ist keine gültige Sudoku-Belegung:
```
int[][] array = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 8 } };
```
Der Fehler könnte etwa gemeldet werden mit: Missing 9.

Lösungsvorschlag

1.3.2. Bild vergrößern ⭐⭐

Captain CiaoCiao ist auf der Suche nach dem Schatz des einäugigen Billy. Die Schatzkarte ist recht klein und seine Augen sind mittlerweile schlecht. Hilf ihm die Karte zu vergrößern und den Schatz zu finden.

Bilder werden im Speicher oft als Tripel von Rot-Grün-Blau-Werten gespeichert, wobei die einzelnen Werte sich zwischen 0 und 255 bewegen können. Da es bei Graustufenbildern keine Farben gibt, ist statt drei Werten nur ein Wert nötig.

Aufgabe:

Gegeben ist ein zweidimensionales Ganzzahl-Array mit Werten von 0 bis 255; das Array stellt gedanklich ein Graustufenbild dar.
Schreibe eine Methode int[][] magnify(int[][] array, int factor), die ein neues Array zurückgibt und das Bild um den gegebenen Faktor skaliert. Aus einem Bild der Größe 2 × 3 und dem Faktor 2 wird also ein Bild der Größe 4 × 6. Bildpunkte werden einfach verdoppelt, eine Interpolation der Werte ist nicht gewünscht.

Beispiel:

Nehmen wir folgendes Array an:

{ {1, 2, 3},
  {4, 5, 6} }

Dann folgt nach einer Verdoppelung:

{ {1, 1, 2, 2, 3, 3},
  {1, 1, 2, 2, 3, 3},
  {4, 4, 5, 5, 6, 6},
  {4, 4, 5, 5, 6, 6} }

Lösungsvorschlag

1.4. Variable Argumentlisten

Java erlaubt Methoden, der man eine beliebige Anzahl Argumente übergeben kann. Sie nennen sich Vararg-Methoden. Ein Vararg-Parameter darf nur zum Schluss einer Parameterliste stehen und ist ein Array. Beim Aufruf mit variablen Argumenten erzeugt der Compiler automatisch ein neues anonymes Array und übergibt es an die Methode.

1.4.1. SVG-Polygone mit variabler Koordinatenanzahl erzeugen ⭐

Bonny Brain möchte für ihren nächsten Arbeitsort eine Karte zeichnen, und die soll gedruckt und auf jeder Auflösung immer gut aussehen, weil es auf jedes Detail ankommt. Die beste Technologie dafür ist SVG.

In SVG gibt es verschiedene Primitive, etwa für Linien, Kreise oder Rechtecke. Auch für Linienzüge gibt es ein XML-Element. Ein Beispiel:

<polygon points="200,10 250,190 160,210" />

Aufgabe:

Deklariere eine Java-Methode printSvgPolygon(…), der wir beliebig viele Koordinaten-Paare übergeben können. Welche Fehler könnte es bei der Übergabe geben?
Die Methode soll zu den übergebenen Paaren eine passende SVG-Ausgabe auf dem Bildschirm ausgeben.

Beispiel:

In printSvgPolygon( 200, 10, 250, 190, 160, 210 ) ist 200,10 ein Koordinatenpaar, 250,190 ebenso, genauso wie 160, 210. Die Bildschirmausgabe soll sein: <polygon points="200,10 250,190 160,210" />.

Optional: Studiere das Beispiel unter https://tutego.de/go/trysvgpolygon. Kopiere das selbstgenerierte SVG in die Weboberfläche.

Lösungsvorschlag

1.4.2. Auf Zustimmung prüfen ⭐

Captain CiaoCiao holt sich von seinen Crewmitgliedern eine Rückmeldung über einen Auftrag. Sämtliche Mitglieder können Ja oder Nein stimmen.

Aufgabe:

Gesucht ist eine Vararg-Methode allTrue(…), der man eine beliebige Anzahl von boolean-Werten übergeben kann, aber mindestens ein Argument übergeben muss.
Sind alle Argumente true, ist auch die Rückgabe true; ist einer der boolean-Werte false, soll die Methode false zurückgeben.
Da ein Vararg intern ein Array darstellt, kann null übergeben werden — das muss zu einer Ausnahme führen.

Beispiel:

allTrue(true, true, true) liefert true.
allTrue(true) liefert true.
allTrue(true, false) liefert false.
allTrue(true, null) liefert eine Ausnahme.
allTrue() lässt sich nicht compilieren und muss einen Compilerfehler geben.

Lösungsvorschlag

1.4.3. Hilfe, Tetraphobie! Alle Vieren nach hinten setzen ⭐⭐

Bonny Brain trifft befreundete Freibeuter in Hongkong und stellt fest, dass viele an Tetraphobie leiden und abergläubische Angst vor der Zahl 4 haben. Die Buchhalterin muss nun alle Zahlen mit einer 4 nach hinten setzen.

Aufgabe:

Schreibe eine Methode fourLast(int... numbers), die alle Zahlen, die eine 4 enthalten, hinter die Zahlen stellt, die keine 4 haben. Die Reihenfolge der Zahlen ohne 4 darf sich nicht ändern, die Zahlen mit einer 4 können irgendwo am Ende stehen.
fourLast(…) soll das übergebene Array als Rückgabe haben.
null in der Übergabe muss zu einer Ausnahme führen.

Beispiel:

int[] numbers = {1, 44, 2, 4, 43}; fourLast(numbers); verändert das Array numbers so, dass 1 und 2 im Array vor 44, 4 und 43 stehen. Die 2 darf später nicht vor der 1 stehen.
fourLast( 4, 4, 44, 1234 ) liefert das vom Compiler automatisch generierte Array mit den Einträgen zum Beispiel in der Reihenfolge 4, 4, 44, 1234 zurück.

Lösungsvorschlag

Noch mehr Aufgaben findest du im Buch: ›Captain CiaoCiao erobert Java: Das Trainingsbuch für besseres Java. 300 Java-Workshops, Aufgaben und Übungen mit kommentierten Lösungen‹