Plätze im Kinosaal
AFB I–IIEin Kino verwaltet die Belegung eines Saals mit 8 Reihen zu je 12 Plätzen in einer zweidimensionalen Reihung: boolean[][] belegt = new boolean[8][12]; Der erste Index ist die Reihe (Zeile), der zweite der Platz in der Reihe (Spalte); true bedeutet belegt. Die Abbildung zeigt einen kleinen Testsaal test mit 3 Reihen und 5 Plätzen.
- Beschreiben Sie die Bedeutung von
belegt.length,belegt[0].lengthundbelegt[7][11]im Sachzusammenhang und den Zustand des Saals direkt nach der Erzeugung der Reihung. - Stellen Sie einen Algorithmus
freiInReihe(saal, r)als Struktogramm dar, der die Anzahl der freien Plätze in Reiherzurückgibt. - Wenden Sie
freiInReiheauf alle drei Reihen des Testsaals an. Geben Sie außerdem an, an welcher Position das Elementtest[2][3]stünde, wenn man den Testsaal zeilenweise in eine eindimensionale Reihung abwickelt (Position ab 0). - Implementieren Sie in Java eine Methode
int besteReihe(boolean[][] saal), die den Index der Reihe mit den meisten freien Plätzen zurückgibt; bei Gleichstand die vordere Reihe (kleinerer Index). Sie dürfen eine MethodefreiInReihenach b) verwenden.
Hinweise
Hinweis zu Aufgabe a)
new boolean[8][12] steht für die Reihen? Welchen Standardwert hat boolean?Hinweis zu Aufgabe b)
r genügt; die Anzahl der Plätze ist Länge von saal[r].Hinweis zu Aufgabe c)
test[2][3]?Hinweis zu Aufgabe d)
freiInReihe, gemerkt wird der Index. Echt größer (>) sorgt für die vordere Reihe bei Gleichstand.Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
belegt.length = 8 ist die Anzahl der Reihen, belegt[0].length = 12 die Anzahl der Plätze in einer Reihe (Reihe 0). belegt[7][11] gibt an, ob der letzte Platz (Platz 11) der hintersten Reihe (Reihe 7) belegt ist. Nach new haben alle 96 Elemente den Standardwert false: Der Saal ist leer.
Erwartungshorizont zu Aufgabe b)
Die Zeile r ist fest, nur der Spaltenindex läuft — eine verschachtelte Schleife ist hier nicht nötig.
Erwartungshorizont zu Aufgabe c)
freiInReihe(test, 0) = 2, freiInReihe(test, 1) = 4, freiInReihe(test, 2) = 1. Zeilenweise liegen vor test[2][3] zwei volle Reihen mit je 5 Plätzen und 3 Plätze der Reihe 2: Position \(2\cdot5+3=13\).
Erwartungshorizont zu Aufgabe d)
int besteReihe(boolean[][] saal) {
int beste = 0;
for (int r = 1; r < saal.length; r++) {
if (freiInReihe(saal, r) > freiInReihe(saal, beste)) {
beste = r;
}
}
return beste;
}Gleichwertig: die freien Plätze der besten Reihe in einer Variablen speichern (spart Aufrufe) oder die Zählung mit einer inneren Schleife direkt ausschreiben. Für den Testsaal liefert die Methode 1.
Ein Graustufenbild bearbeiten
AFB II–IIIEin Graustufenbild wird als zweidimensionale Reihung bild ganzer Zahlen gespeichert: Zeile z, Spalte s, Helligkeit von 0 (schwarz) bis 255 (weiß). Zum Testen dient ein Bild mit 2 Zeilen und 3 Spalten:
| bild | s = 0 | s = 1 | s = 2 |
|---|---|---|---|
| z = 0 | 0 | 90 | 255 |
| z = 1 | 200 | 30 | 128 |
Ein Bildbearbeitungsprogramm enthält folgenden Algorithmus:
- Analysieren Sie den Algorithmus: Geben Sie das Testbild nach dem Aufruf an und beschreiben Sie die Wirkung auf ein Foto.
- Verändern Sie den Algorithmus so, dass er das Bild waagerecht spiegelt (links und rechts vertauscht). Begründen Sie, warum die innere Schleife dabei nur bis zur Mitte der Zeile laufen darf.
- Schätzen Sie für ein Foto mit 1920 × 1080 Bildpunkten ab, wie oft der Rumpf der inneren Schleife von
verarbeiteausgeführt wird und wie viel Speicher die Reihung belegt, wenn jede ganze Zahl 4 Byte braucht. Wie ändern sich beide Werte bei einem Bild mit doppelter Breite und doppelter Höhe? - Für eine Belichtungsanzeige soll zu jeder Spalte die mittlere Helligkeit berechnet werden. Entwerfen Sie einen Algorithmus
spaltenMittel(bild)als Struktogramm, der eine eindimensionale Reihung mit den ganzzahligen Mittelwerten aller Spalten zurückgibt, und geben Sie das Ergebnis für das Testbild an.
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
bild[z][s] mit bild[z][spalten − 1 − s] über eine Hilfsvariable. Was passiert, wenn jedes Paar zweimal getauscht wird?Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
Nach dem Aufruf: Zeile 0: 255, 165, 0; Zeile 1: 55, 225, 127. Jeder Wert wird an der Mitte des Bereichs gespiegelt: Schwarz wird Weiß, Weiß wird Schwarz, helle Stellen werden dunkel. Es entsteht das Negativ des Bildes. Die Reihenfolge der Schleifen spielt hier keine Rolle, weil jeder Bildpunkt unabhängig von den anderen berechnet wird.
Erwartungshorizont zu Aufgabe b)
Jeder Tausch bewegt zwei Punkte gleichzeitig. Liefe s über die ganze Zeile, würde jedes Paar zweimal getauscht — das Bild wäre am Ende unverändert. Bei ungerader Spaltenzahl bleibt die mittlere Spalte stehen (Testbild: spalten / 2 = 1, nur Spalte 0 und 2 werden getauscht).
Erwartungshorizont zu Aufgabe c)
Durchläufe: \(1920\cdot1080=2\,073\,600\), also rund 2 Millionen. Speicher: \(2\,073\,600\cdot4\) Byte \(=8\,294\,400\) Byte \(\approx8{,}3\) MB. Bei doppelter Breite und Höhe vervierfachen sich beide Werte (etwa 8,3 Millionen Durchläufe und 33 MB), weil die Zahl der Bildpunkte das Produkt aus Breite und Höhe ist. Eine Speicherung als Byte statt als ganze Zahl würde den Speicher auf ein Viertel senken.
Erwartungshorizont zu Aufgabe d)
Testbild (vor verarbeite): Spalte 0: \((0+200)/2=100\), Spalte 1: \((90+30)/2=60\), Spalte 2: \((255+128)/2=191\) (ganzzahlig, exakt 191,5). Ergebnis {100, 60, 191}. summe muss für jede Spalte neu auf 0 gesetzt werden. Eine Lösung mit einer Reihung summe[s] und anschließender Division ist gleichwertig.