Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
SS16 Aufgabe 5 (ADT) “Langtons Ameise”
Hallo zusammen,
in der o.g. Aufgabe geht es um Langtons Ameise, diese wird auf einem unendlichen Raster aus weissen (false) oder schwarzen (true) Feldern platziert und Fängt an zu krabbeln.
Anfangs sind alle Felder weiss und die Ameise wird auf Feld (x:666, y:666) gesetzte, ab dann befolgt sie die folgenden drei Regeln:
1.) Auf einem weißen Feld drehe 90 Grad nach rechts, d.h. d → (d+3)%4 bzw. auf schwarzem Feld 90 Grad nach links, d.h. d → (d+1)%4
2.) Wechsle die Farbe des Feldes (weiß nach schwarz oder schwarz nach weiss).
3.) Schreite ein Feld in der aktuellen Blickrichtung fort.
Es stehen Datentypen int und boolean wie in Java zur Verfügung
LA
sorts LA, boolean, int
ops
New: int → LA //startet Ameise auf neuem Raster in übergebener Richtung d
Step: LA → LA //Ameise macht einen Schritt nach obigen Regeln
getCol: LA x int x int → boolean //liefert die aktuelle Farbe im übergebenen Feld (x,y)
getDir: LA → int //liefert aktuelle Ausrichtung d der Ameise
getX: LA → int //Liefert die aktuelle x-Koordinate der Ameise
getY: La → int //liefert die aktuelle y-Koordinate der Ameise
a) Ergänzen sie die Axiome für getCol:
FSI_Lösungsvorschlag:
getCol(New(d), x, y) = false
getCol(Step(l), x, y) = NOT(getCol(l,x,y) falls x=l.getX && y=l.getY
getCol(Step(l), x, y) = getCol(l, x, y) sonst
1. darf ich einfach “Not” schreiben in ADTs, wenn eine Negation nicht angegeben ist?
2. Darf ich mit einem Punkt Methodenaufrufen wie bei l.getX?
3. Falls das nicht möglich ist, wie würden korrekte Axiome lauten?
b) Ergänzen Sie die Axiome für getDir:
[i]FSI-Lösungsvorschlag:
getDir(Step(l)) = (d+3)%4 falls getCol(l,x,y) = false
getDir(Step(l)) = (d+1)%4 sonst
Obige Lösung ist mMn falsch, dem Aufruf werden kein d, kein x und kein y mitgegeben. Meine (womöglich immer noch falsche) Lösung:
getDir(Step(l)) = (getDir(l)+3)%4 falls getCol(l, getX(l), getY(l)) == false
getDir(Step(l)) = (getDir(l)+1)%4 sonst[/i]
4. Auch hier, habe ich es in der Aufgabenstellung übersehen, oder warum kann man hier “+” , “=” und “%” verwenden?
5. Wie würden hier die korrekten Axiome lauten?
c) Ergänzen Sie die Axiome für getX:
FSI-Lösungsvorschlag:
getX(New(d)) = 666
getX(Step(l)) = getX(l) + 1 falls getDir(Step(l)) == 1
getX(Step(l)) = getX(l) - 1 falls getDir(Step(l)) == 3
getX(Step(l)) = getX(l) sonst
6. Sollen diese drei Fälle angeben, dass die Ameise entweder Ihren x-Wert verringert, erhöht oder sich nur der Y-Wert verändert? Und sind die angegebenen Axiome korrekt?
d) Folgende Klasse stellt eine zustandsbehaftete Implementierung des ADTs LA in Java dar. Anstatt eines unendlichen Rasters wird hier ein zweidimensionales Feld raster aus boolean verwendet, bei dem raster[x][y] = false einem weißen Feld entspricht.
Sie können davon ausgehen, dass raster groß genug dimensioniert ist, so dass beliebig häufige Anwendungen (…) kein ArrayIndexOutOfBounds.
Ergänzen sie step:
FSI-Lösungsvorschlag:
public class LangtonAntJava{
boolean[][] raster = new boolean[4711][4242];
int x = 666, y = 666, d = 0; // Position und Richtung
void step(){
if(raster[x][y]){
d = (d+1)%4;
} else {
d = (d+3)%4;
}
raster[x][y] = !raster[x][y];
if(d == 0){
y -= 1;
} else if (d == 1){
x += 1;
} else if (d == 2){
y += 1;
} else if (d == 3){
x -= 1;
}
}
}7. Sind hier nicht die Richtungen verwechselt worden? Norden (d=0) sollte doch den y-Wert um eines erhöhen wie in der ersten Abbildung der Aufgabenbeschreibung,etc.,
Mein Vorschlag:
public class LangtonAntJava{
boolean[][] raster = new boolean[4711][4242];
int x = 666, y = 666, d = 0; // Position und Richtung
void step(){
if(raster[x][y]){
d = (d+1)%4;
} else if(raster[x][y] == false) {
d = (d+3)%4;
}
raster[x][y] = !raster[x][y];
switch(d) {
case 0: y += 1; break; //d=0 Norden
case 1: x -= 1; break; //d=1 Westen
case 2: y -= 1; break; //d=2 Süden
case 3: x += 1; break; //d = 3 Osten
default:
}
}
}
Liebe Grüße
Speedy
Hi,
Ja, da in der Angabe die Verwendung von „boolean wie in Java“, also die Verwendung von allen in Java üblichen logischen Operatoren gestattet wird.
Nein, korrekterweise und vollständig müsste es heißen:
LA.getX(l)
La ist das ADT, getX die Operation und l das Argument.
Sollte es in keinem anderen angegebenen ADT die Operation getX geben, darf man sich das Präfix sparen, da der Operationsname eindeutig ist.
Siehe 1., int ist erlaubt.
Deine Axiome sind korrekt.
Wenn im vorherigen Zustand l an der Stelle der Ameise (getX(l) und getY(l)) die Farbe weiß (== false) war, dann hat sie sich von der ursprünglichen Richtung (getDir(l)) aus betrachtet nach rechts gedreht (+3%4).
Sonst eben nach links.
Zuerst wird der Fall unterschieden, ob es sich um ein neues Feld handelt (dann ist die X-Position klar) oder ob es aus einem Step entstanden ist.
Was bei zweiterem Fall eher nochmal abgeprüft wird, ist die Richtung. Aus dieser ergibt sich ja dann die x-Änderung im Vergleich zum Vorgänger. Nachdem aber zwei Richtungen das gleiche Verhalten haben, wurde halt aus vier Fällen (für jede Richtung einen) nur drei.
Ja, deine Lösung sieht mir hier richtiger aus (auch wenn ich persönlich ==true und ==false in Java mehr als überflüssig finde).
1 „Gefällt mir“
Okay, ist “NOT” ein offizieller Java Begriff oder wurde es hier einfach statt “!” verwendet?
Keine Angst “==false” werde ich mir im Laufe der Zeit noch abgewöhnen. Aber im Moment hilft es mir als Anfänger den Überblick zu bewahren, da ich ein “!” schnell übersehe 
Vielen Dank, Orlan!
Es wurde NOT statt ! verwendet, um mehr ADT-Like zu wirken.
Allerdings ist es dann inkonsequent, + statt add(x,y) zu verwenden.
Aber in der Klausur gilt: Sobald es eindeutig ist, was du meinst, sollte es gezählt werden. Und ich denke, sowohl mit ! als auch mit NOT können die Korrektoren etwas anfangen.
1 „Gefällt mir“