Übungen
Aufgabe 1: Ein einfaches Problem lösen
In dieser Aufgabe geht es darum, ein recht einfaches Problem zu lösen. Eine mögliche Lösungsidee wird dabei vorgegeben.
Kara soll einmal um einen Baum laufen. Beachte, dass Kara danach in derselben Position am Baum steht. Achte dabei darauf, dass du nicht einfach nur eine lange Anweisungssequenz nutzt, sondern etwas cleverer vorgehst.
Die Problemstellung ist hier eindeutig vorgegeben. Es verbleiben drei Schritte zur Problemlösung: Suche Ideen, entwickle einen Algorithmus, implementiere und teste ein Programm.
Eine clevere Idee lässt sich so beschreiben: Zuerst die Ausgangsposition mit einem Kleeblatt markieren und einen Schritt weitergehen. Solange man sich nicht auf einem Kleeblatt befindet, einen weiteren Schritt „um den Baum herum“ gehen. (Wie genau man „um den Baum herum“ geht, musst du dir noch überlegen!) Abschließend das Kleeblatt wieder entfernen.
Aufgabe 2: Ein schwieriges Problem lösen
In dieser Aufgabe geht es darum, ein Problem zu lösen, das zwar noch nicht sehr komplex ist, dessen Lösung aber dennoch etwas knifflig ist.
Kara merkt sich die Uhrzeit mit einem Pilz, der schrittweise um einen Baum geschoben wird. Es sind also acht Pilz-Positionen möglich. Kara soll hier den Pilz - egal, wo er sich zunächst befindet - um einen Schritt weiterverschieben.
(a) Um dir die Problemstellung komplett klar zu machen, solltest du noch mindestens eine weitere Vorher-Nachher-Situation skizzieren. Funktioniert hier das Pilz-Weiterschieben genau gleich oder gibt es Unterschiede je nach Position des Pilzes?
(b) Entwickle eine Lösungsidee für dieses Problem.
Mögliche Lösungsidee (muss noch verfeinert werden!):
- Kara geht zuerst zum Baum. Achtung: Wenn der Pilz direkt zwischen Kara und dem Baum steht, dann wird das komplizierter. Ggf. lässt du diesen Sonderfall erst einmal weg und betrachtest ihn später.
- Dann geht Kara so lange um den Baum herum, bis er/sie am Pilz steht. Hier hilft ggf. Aufgabe 1.
- Nun wird der Pilz weitergeschoben. Wie genau das geht, hängt aber davon ab, an welcher Position der Pilz sich befindet. Man muss hier zwei Fälle unterscheiden.
(c) Entwickle aus deiner Lösungsidee einen Algorithmus in Struktogramm-Form.
(d) Implementiere ein Python-Programm und teste es.
(e) Noch schwieriger: Löse dasselbe Problem, aber Kara soll am Ende wieder zurück zur Ausgangsposition laufen.
Aufgabe 3: Fehler suchen
In dieser Aufgabe geht es darum, sich mit den Fehlern beim algorithmischen Problemlösen auseinanderzusetzen. Gleichzeitig wird das Erstellen von Sturktogrammen geübt.
Kara soll die Kleeblätter, die als Rechteck ausgelegt sind, alle einsammeln.
T. hat das folgende Programm zur Lösung des Problems entwickelt.
while kara.onLeaf():
kara.removeleaf()
kara.move()
kara.turnRight()
while kara.onLeaf():
kara.removeleaf()
kara.move()
kara.turnRight()
while kara.onLeaf():
kara.removeleaf()
kara.move()
kara.turnRight()
while kara.onLeaf():
kara.removeleaf()
kara.move()
kara.turnRight()
(a) Teste erst einmal das Programm. Es erscheint direkt eine Fehlermeldung. Welchen syntaktischen Fehler hat T. gemacht?
(b) Korrigiere den Fehler und teste erneut das Programm. Es leistet noch nicht das Gewünschte. Irgendetwas stimmt mit den Einrückungen noch nicht. Kannst du diesen Fehler auch noch beheben?
(c) Wenn du den Einrückfehler verbessert hast, dann leistet das Programm immer noch nicht das Gewünschte. Der Algorithmus, der dem Programm zu Grunde liegt, ist noch nicht in Ordnung. Kannst du das auch noch korrigieren?
(d) Wenn du ein korrekt arbeitendes Programm hast, dann stelle den zu Grunde liegenden Algorithmus in Struktogrammform dar.
Aufgabe 4: Ein schwieriges Problem lösen
In dieser Aufgabe geht es darum, ein schwieriges und komplexes Problem zu lösen.
Kara soll Bäume mit Kleeblättern auslegen.
Zu Beginn befindet sich Kara unten im Baumstamm. Kara soll anschließend ein mit Bäumen umrandetes Gebiet (das die Form eines Baumes hat) mit Kleeblättern auslegen. Es sind auch andere Bäume möglich als unten abgebildet. Wir gehen dabei davon aus, dass alle Felder direkt vom Baumstamm aus erreichbar sind.
(a) Entwickle zunächst eine Lösungsidee. Beschreibe sie in Worten.
Ein möglicher Ansatz besteht darin, zeilenweise vorzugehen und den Baum Ebene für Ebene mit Blättern auszulegen. Ein wichtiger Punkt ist hierbei aber, wie Kara von einer Ebene zur nächsten kommt. Dafür muss Kara beim Auslegen einer Ebene immer in der Lage sein, den Stamm wiederzufinden ...
(b) Formuliere anschließend einen Algorithmus in Struktogramm-Form.
(c) Entwickle und teste dann ein zum Algorithmus passendes Programm.
