Strukturierung – Probleme zerlegen / Algorithmen zusammensetzen
Zielsetzung
Du hast auf der vorangegangenen Seite das Konzept „Teile und Herrsche“ kennengelernt. Dabei geht es darum, ein kompliziertes Problem in mehrere Teilprobleme zu zerlegen. Sobald diese gelöst sind, kann man die einzelnen Lösungen zusammensetzen. Damit ist dann auch das große Problem gelöst. Wir übertragen dieses Vorgehen jetzt auf das Programmieren von Kara.
Das Problem: Ein Fußballfeld mit Kleeblättern auslegen
Kara will ein Fußballfeld mit Kleeblättern auslegen. Die Eckpfosten stehen schon.
Das Problem in Teilprobleme zerlegen
Das Problem ist recht komplex. In solch einer Situation ist es meist günstig, das Problem in geeignete Teilprobleme zu zerlegen. Eventuell kann man Teilprobleme wiederum in weitere Teilprobleme aufteilen.
Aufgabe 1
Teile das Problem in geeignete Teilprobleme auf. Beschreibe sie möglichst genau (am besten durch Anfangs- und Endzustand). Du musst hier noch nichts programmieren.
Fussballfeld mit Kleeblättern auslegen 1. zur Ausgangsposition laufen 2. den Spielfeldrand mit Kleeblättern auslegen a) eine Kleeblattreihe bis zum nächsten Baum legen b) um einen Baum laufen 3. das Innere des Spielfelds mit Kleeblättern auslegen a) ... 4. zur Endposition laufen
Die Teilprobleme lösen
Ist das komplexe Problem zerlegt, so müssen die Teilprobleme gelöst werden. Es ist dabei möglich, dass man hierbei die Teilprobleme noch weiter zerlegt. Oft kommen dabei Unterprogramme zum Einsatz; das ist aber nicht zwingend nötig.
Aufgabe 2
Entwickle für jedes entstandene Teilproblem ein PythonKara-Programm und teste es.
Die folgenden Tipps beziehen sich auf die Teilprobleme, die oben im Tipp genannt worden sind:
- Das Teilproblem 1 ist relativ einfach; es genügt eine kurze Anweisungssequenz. Gleiches gilt für das Teilproblem 4.
- Das Teilproblem 2 hast du bereits im Abschnitt Erkundung – Kara lernt neue Befehle gelöst. Du kannst die Lösung von damals kopieren, sofern du sie dir jetzt noch einmal anschaust. Du hattest hierbei Unterprogramme genutzt, wodurch das Problem noch einmal unterteilt worden ist.
-
Es bietet sich an, auch das Teilproblem 3 weiter zu zerlegen. Das geht dann ganz ähnlich zu Teilproblem 2. Statt bis zum nächsten Baum legst du aber immer eine Kleeblattreihe bis zum nächsten Kleeblatt (Spielfeldrand). Und statt um einen Baum zu laufen, musst du dann wieder zum Anfang zurückkehren.
Teillösungen zusammensetzen
Sind alle Teilprobleme gelöst, musst du die Lösungen noch zusammensetzen. Achte darauf, das Programm entsprechend zu kommentieren, damit man versteht, was wo geschieht. Auch Unterprogramme können hier zur Übersichtlichkeit beitragen.
Aufgabe 3
Setze deine Teillösungen zusammen. Teste dein Programm.
# Unterprogramme
...
# Hauptprogramm
zurAusgangpositionLaufen()
spielfeldrandAuslegen()
spielfeldinnereAuslegen()
zurEndpositionLaufen()
Das Wichtigste notieren
Das Vorgehen „Teile und Herrsche“ ist sehr wichtig – in vielen Bereichen der Informatik und auch darüber hinaus. Es ist eine allgemeine Strategie zum Lösen von Problemen.
Aufgabe 4
Im Abschnitt zum Algorithmischen Problemlösen wurde bereits ein mehrschrittiges Vorgehen zum Problemlösen notiert. Ergänze in deiner Mitschrift (eventuell ist das ein Wissensspeicher) zum dritten Schritt (Algorithmus entwickeln und formalisieren) in Farbe „Teile und Herrsche“. Wenn du das sinnvoll findest und dafür genügend Platz hast, erkläre auch kurz, was das bedeutet.
