Felder, mehrdimensional

4 Mehrdimensionale Felder

Bisher haben wir Felder als "indizierte Variablen" kennengelernt, bei denen mit Hilfe eines Index auf ein bestimmtes Datenelement aus einer Reihe gleichartiger Elemente zugegriffen werden konnte. Die Vorstellung, dass die Datenelemente sozusagen hintereinander aufgereiht sind, wie "auf einer Wäscheleine hängen" ist naheliegend, und sie ist nicht falsch. Allerdings bietet der Datentyp "ARRAY" durchaus noch mehr Möglichkeiten: statt einer linearen Anordnung (wie auf der Wäscheleine!) können sich die Datenelemente auch in zwei Dimensionen verteilen, wie z.B. auf einem Schachbrett:

in Delphi können wir mit

     var Schachbrett : ARRAY [1..8, 1..8] OF Integer;

in Java können wir mit

     int[][] schachBrett = new int[8][8];

ein zweidimansionales Array erstellen, das ein Schachbrett modelliert. Beim Zugriff auf eines der Felder des Schachbretts müssen nun eben zwei Indizes angegeben werden, um genau zu beschreiben, welches Feld wir meinen:

in Delphi könnte "Schachbrett [1, 1]" das Feld links unten meinen, "Schachbrett [8, 1]" das Feld an der rechten unteren Ecke, "Schachbrett [6, 8]" das Feld zwei Stellen links von der rechten oberen Ecke usw.

in Java könnte "schachBrett [1, 1]" das Feld links unten meinen, "schachBrett [8, 1]" das Feld an der rechten unteren Ecke, "schachBrett [6, 8]" das Feld zwei Stellen links von der rechten oberen Ecke usw.

Und warum ganze Zahlen (Integer bzw. int) als Komponententyp? Nun, wir könnten in einem unbesetzten Feld des Schachbretts eine Null speichern und in einem mit einer Spielfigur besetzten Feld eine entsprechende Kennzahl dieser Figur! Dabei könnte der Betrag der Zahl die Art der Spielfigur kodieren und das Vorzeichen der Zahl die Farbe der Figur. (Später werden wir noch elegantere Möglichkeiten kennenlernen, einen passenden Datentyp für Spielfiguren zu definieren.)

Völlig analog lassen sich auch höherdimensionale Felder vereinbaren: die Anzahl der Indizes ist eigentlich nur durch das Hirn des Programmierers begrenzt, der da natürlich nicht den Überblick verlieren darf. Außerdem belegen mehrdimensionale Felder sehr schnell viel Speicher, sodass wir uns vorsichtshalber zunächst auf zwei Dimensionen beschränken wollen.

Mit zweidimensionalen Feldern kann man leicht mathematische Verknüpfungen in sogenannten "Verknüpfungstafeln" darstellen. Wir benutzen endliche Teilmengen der natürlichen Zahlen und verknüpfen diese Zahlen mit den Ganzzahloperatoren DIV und MOD. Diese kommen im Alltag z.B. bei der Zeitrechnung vor, ohne dass sie uns da besonders auffallen: 7 Stunden nach 10 Uhr ist es wegen (10 + 7) MOD 12 = 5 eben wieder 5 Uhr. a MOD b liefert also den Rest, den a bei der Division durch b läßt. a DIV b liefert den Ganzzahlquotienten, also die Anzahl, wie oft b ganz in a enthalten ist.

Bleiben wir beim Zeitrechnungsbeispiel: auf dem Ziffernblatt einer (analogen) Uhr beschränken wir uns auf die Zahlen 1 bis 12. Mathematiker ersetzen die 12 durch die Null und betrachten dann die Menge M = {0, 1, 2, 3, ....., 10, 11} als die Menge der gültigen Stundenangaben. Man redet dann von der "Modulo-Menge zum Modul 12".

Statt der einfachen Modulo-Addition sind natürlich auch andere Operationen denkbar. Im Allgemeinen nehme man irgend einen Term mit 2 Variablen a und b, der für alle Einsetzungen aus M eine (nichtnegative) ganze Zahl e liefert; ist n der Modul von M, dann ist das Ergebnis der Verknüpfung die Zahl e MOD n. Nach so viel abstrakter Mathematik ist es höchste Zeit für ein konkretes

Beispiel:

Wir betrachten die Menge M = {0, 1, 2, 3, 4, 5} zum Modul 6 mit der Verknüpfung a § b, wobei

         a § b := (a * b) MOD 6

bedeuten soll. Die folgende Tabelle stellt die zugehörige Verknüpfungstafel dar und gibt damit einen Überblick über alle möglichen §-Rechnungen in der Menge M. Die obere grüne Zeile zeigt die möglichen Werte für a, die vordere grüne Spalte die möglichen Werte für b; an den entsprechenden Stellen im Körper der Tabelle ist das zugehörige Ergebnis für a § b eingetragen:

§	1	2	3	4	5
0	0	0	0	0	0
1	1	2	3	4	5
2	2	4	0	2	4
3	3	0	3	0	3
4	4	2	0	4	2
5	5	4	3	2	1

Bei dieser Tabelle fallen mehrere Symmetrien auf, die bestimmte Rechengesetze für die Verknüpfung § darstellen, z.B.:

eine Achsensymmetrie zur Hauptdiagonalen; diese visualisiert das Kommutativ-Gesetz:
```
     a § b = b § a 
```
eine Achsensymmetrie zu einer Nebendiagonalen; diese visualisiert ein Gesetz, für das es bei den natürlichen Zahlen keine direkte Entsprechung gibt:
```
     a § b = ( 6 - b) § (6 - a)
```
Mit ein wenig gutem Willen könnte man aber dieses Gesetz als verwandt zu
```
     a * b = (-b) * (-a) = (-a) * (-b)
```
erkennen, was dann im wesentlichen auf "Minus mal Minus gibt Plus" hinausläuft.
Außerdem gibt es in den Zeilen (und den Spalten!) mit geraden Nummern noch eine Translations-Symmetrie:
```
     a § b = a § ( b +/- 3 )  für gerades a
```
Dafür läßt sich aber selbst mit viel gutem Willen kein Analogon bei den natürlichen Zahlen finden.

Es gibt auch noch eine Punktsymmetrie in dieser Tabelle. Finden Sie das Zentrum? Wie lautet das zugehörige Rechengesetz?
Im folgenden sollen solche Modulo-Mengen mit entsprechenden Verknüpfungen studiert werden.
Bearbeiten Sie dazu die folgenden

Aufgaben:

Die Modulo-Tafel:

Schreiben Sie ein Programm, das die Eingabe eines Moduls n gestattet und eine selbstdefinierte Funktion enthält, mit der das Ergebnis einer Modulo-Multiplikation für eine entsprechende Modulo-Menge berechnet werden kann. Auf Knopfdruck soll die Verknüpfungstafel dieser Funktion erstellt werden.

In Delphi verwenden Sie dazu eine StringGrid-Komponente sowie einen Button, in dessen Klick-Prozedur zwei ineinandergeschachtelte FOR-Schleifen die Daten-Felder des StringGrid füllen. Sinnvollerweise sollte das Eingabefeld für den Modul sowie der Button auf ein Panel gesetzt werden. Setzen Sie die Align-Eigenschaften der verwendeten Komponenten so ein, dass der Platz im Fenster stets optimal genutzt wird. Verwenden Sie die OnExit-Prozedur des Eingabefeldes für die automatische Neudimensionierung des StringGrid! Füllen Sie dabei schon die Kopfzeile und die Frontspalte aus!

In Java verwenden Sie dazu eine JTable-Komponente sowie einen JButton, in dessen Klick-Prozedur zwei ineinandergeschachtelte FOR-Schleifen die Daten-Felder des StringGrid füllen. Sinnvollerweise sollte das Eingabefeld für den Modul sowie der JButton auf ein JPanel gesetzt werden. Da die Redimensionierung einer Tabelle in Java nicht ganz einfach zu erledigen ist, können Sie mit einer fest-dimensionierten Tabelle (z.B. der Größe "15x15") arbeiten, bei der eben die nicht-benutzten Felder leer bleiben.

Achten Sie auf eine ordentliche Strukturierung Ihres Programms, indem Sie Teilaufgaben in selbstdefinierte Funktionen und Prozeduren packen: neben der eigenen Funktion, die das Verknüpfungsergebnis berechnet, sollte es mindestens noch eine eigene Prozedur geben, die den Inhalt der Tabelle löscht und die Felder mit Leer-Strings füllt!

Untersuchen Sie dann mit Ihrem Programm mehrere Modulo-Mengen auf Symmetrien; versuchen Sie, die damit verbundenen Rechengesetze zu formulieren!
Es gibt für die Modulo-Multiplikation einen wesentlichen Unterschied zwischen Primzahl-Modulen und Nicht-Primzahl-Modulen. Finden Sie ihn?
(Ein Tip dazu: Wo stehen Nullen in der Verknüpfungstafel? Warum sollten Sie sich über manche der Nullen wundern?)

Lösungsvorschlag [Delphi] [Java]

Das Modulo-Bild:

Für große Module (n > 20) wird die obige Darstellung der Verknüpfungstafel unhandlich. Sie können dann zur Veranschaulichung der Struktur auf eine grafische Darstellung ausweichen: das Ergebnis e der Verknüpfung der Elemente a und b der Modulo-Menge wird an der Stelle (a, b) in ein Quadrat der Seitenlänge n eingetragen, und zwar als Punkt, dessen Farbe durch e bestimmt wird. Beginnen Sie z.B. mit einer Schwarz-Weiß-Darstellung: der Punkt wird schwarz, wenn e > (n Div 2) ist, andernfalls bleibt er weiß.

Schreiben Sie ein entsprechendes Programm, in dem Sie die Verknüpfungstafel direkt in dem Programmfenster darstellen.

In Delphi können Sie dazu direkt die Eigenschaft "Pixels[x,y]" der Canvas-Komponente des Formulars verwenden: diese ist ein 2-dimensionales Array, das es gestattet, die Farbe eines bestimmten Pixels im Fenster zu ermitteln bzw. zu setzen. Mit

    Pixels[3,4] := clGreen;

färben Sie das vierte Pixel in der 5.Pixelzeile in grüner Farbe ein.

In Java erzeugen Sie als Ausgabe-Bereich eine quadratische JPanel-Komponente; deren Methode "getGraphics()" liefert Ihnen eine Zeichenfläche zurück, die über die nötigen Grafikbefehle verfügt. Sie brauchen hier eigentlich nur den Befehl

    drawRect(int x, int y, int width, int height)

Dieses Kommando zeichnet in der aktuell eingestellten Farbe ein Rechteck der Breite "width" und der Höhe "height", dessen linke obere Ecke an der Stelle (x|y) liegt. Wenn Sie die Breite und die Höhe des Rechtecks auf Null setzen, dann wird nur das Pixel an der Stelle (x|y) entsprechend eingefärbt.

Später können Sie dann zu mehrfarbiger Darstellung übergehen, indem Sie den Ergebnisbereich 0...(n-1) in mehrere Abschnitte teilen und jedem Abschnitt eine eigene Farbe zuweisen. Führen Sie dazu die zu verwendenden Farben in einem eigenen Array auf. Implementieren Sie eine eigene Funktion, die das aktuelle Verknüpfungsergebnis als Parameter übergeben bekommt, und dann mit Hilfe des Modul-Wertes aus den zur Verfügung stehenden Farben die passende auswählt und zurückgibt. Verschiedene Farbanzahlen können dabei übrigens durchaus unterschiedliche Strukturen derselben Modulo-Menge zum Vorschein bringen!

Und schließlich können Sie statt der nun schon sattsam bekannten Modulo-Multiplikation auch andere Verknüpfungen untersuchen, z.B.:

die Modulo-Subtraktion (a - b) MOD n,
(Vorsicht! Hier taucht das Problem der negativen Zahlen auf, die unbedingt vermieden werden müssen!),
die Modulo-Potenzierung (a^b) MOD n,
(Vorsicht! Hier müssen Sie darauf achten, dass während der Berechnung kein Integer-Überlauf passiert!)
die "Hypothenusen-Verknüpfung" (a²+b²) MOD n, die besonders schöne Bilder liefert,

und ähnliches mehr.

Lösungsvorschlag [Delphi] [Java]