Übungen

Aufgabe 1: Labyrinth

Die Spinne spider hat sich in einem Labyrinth verirrt. Wie soll sie da wieder rauskommen?

Labyrinth mit Spinne
Programm: labyrinth0.sb

(a) Problembeschreibung:

Das Labyrinth-Problem soll in der folgenden verallgemeinerten Form gelöst werden: Die Spinne soll zum Ausgang des Labyrinths laufen - egal, wie das Labyrinth aussieht und egal, wo die Spinne sich zu Beginn befindet. Beschreibe dieses Problem mit vorher/nachher-Problemsituationen. Skizziere verschiedene mögliche Ausgangssituationen und die jeweils zu erreichende Endsituation.

(b) Eine Lösungsidee:

Wie gelangt man systematisch aus einem Labyrinth? Kennst du die Linke-Hand-Strategie (Rechte-Hand-Strategie)? Man läuft so weiter, dass die linke (rechte) Hand immer die Labyrinthwand berührt.

(b1) Probiere die Linke-Hand-Strategie selbst einmal aus.

(b2) Welchen Weg würde die Spinne im oben gezeigten Labyrinth laufen, wenn sie zunächst geradeaus zur nächsten Wand läuft, sich dann nach rechts dreht und anschließend die Linke-Hand-Strategie verfolgt?

(c) Ein Algorithmus zur Lösung des Problems:

(c1) Stelle dir vor, dass die Spinne nur vorne fühlen kann, ob sie die Wand berührt. Wie kann sie trotzdem überprüfen, ob sich links von ihr eine Wand befindet?

Um dieses Teilproblem zu lösen, schreibe zunächst ein kleines Programm, so dass die Spinne so lange geradeaus weiterläuft, bis links von ihr keine Wand mehr ist. Dabei darf sie aber nur vorne fühlen. Eine Lösung der Art "solange 'grün' berührt wird, laufe geradeaus" ist also nicht zulässig.

(c2) Mache dir nun klar, in welchen Situationen sich die Spinne befinden kann. Die folgende Abbildung hilft dir dabei. Wie soll die Spinne sich jeweils verhalten?

Labyrinth mit Spinne

(c3) Formuliere jetzt den Algorithmus in einer Grobversion.

wiederhole bis vor einer Wand oder am Ausgang:
    laufe einen Schritt vorwärts
wenn nicht am Ausgang:
    drehe dich um 90° nach rechts
wiederhole bis am Ausgang:
    wenn vor einer Wand:
        ...
    sonst:
        wenn links nahe einer Wand:
            ...
        sonst:
            ...

(c4) Jetzt müssen noch weitere Details geklärt werden: Wie merkt die Spinne, ob sie am Ausgang angelangt ist? Wie merkt die Spinne, ob sie vor einer Wand steht? Überlege dir geeignete Verfahren zur Lösung dieser Teilprobleme.

(d) Ein Programm zur Lösung des Problems:

Entwickle jetzt passend zum Algorithmus ein Scratch-Programm. Teste das Programm mit verschiedenen Ausgangssituationen.

Als Hintergründe für die Bühne kannst du die folgenden Bilder benutzen: labyrinth1.png, labyrinth2.png. Du kannst aber auch gerne eigene Labyrinthe erstellen.

Für die Spinne solltest du ein quadratisches Bild benutzen, dessen Hintergrund nicht transparent ist, z.B.: spinne.png.

X

Fehler melden

X

Suche